source: ip/src/main/java/geniusweb/ip/ipSolver/IPSolver.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 46.2 KB
Line 
1package geniusweb.ip.ipSolver;
2
3import geniusweb.ip.general.Combinations;
4import geniusweb.ip.general.ElementOfMultiset;
5import geniusweb.ip.general.General;
6import geniusweb.ip.general.IntegerPartition;
7import geniusweb.ip.general.SubsetsOfMultiset;
8import geniusweb.ip.inputOutput.Input;
9import geniusweb.ip.inputOutput.Output;
10import geniusweb.ip.inputOutput.SolverNames;
11import geniusweb.ip.mainSolver.Result;
12
13public class IPSolver {
14 /**
15 * the IP algorithm.
16 */
17 public void solve(Input input, Output output, Result result) {
18 // Initialization
19 int numOfAgents = input.numOfAgents;
20 result.initialize();
21
22 // Find the best CS in the first & last Levels of the Integer Partition
23 // Graph
24 searchFirstAndLastLevel(input, result);
25
26 // Calculate the average of the values of coalitions of size:
27 // s=1,2,...,numOfAgents.
28 // While doing this, search the second level of the integer partition
29 // graph. Also, if required,
30 // search the side subspaces of levels 3,4,...,numOfAgents-1 (e.g. the
31 // subspace [5,1,1,...,1])
32 double[] avgValueForEachSize = new double[numOfAgents];
33 MethodsForScanningTheInput.scanTheInputAndComputeAverage(input, output,
34 result, avgValueForEachSize);
35
36 // Calculate the highest value, 2nd highest, 3rd highest, and so on, as
37 // long as this is useful
38 // (e.g. given 15 agents, for the coalitions of size 4, we only need to
39 // calculate the highest
40 // 3 values since it is not possible to have more than 3 fours in a
41 // single integer partition
42 double[][] maxValueForEachSize = setMaxValueForEachSize(input);
43
44 // Create the integer partition graph
45 Subspace[][] subspaces = initSubspaces(avgValueForEachSize,
46 maxValueForEachSize, input);
47 if (input.solverName == SolverNames.ODPIP)
48 result.ipIntegerPartitionGraph = new IntegerPartitionGraph(
49 subspaces, input.numOfAgents, 1);
50 else
51 result.ipIntegerPartitionGraph = new IntegerPartitionGraph(
52 subspaces, input.numOfAgents,
53 ((int) Math.floor(2 * input.numOfAgents / (double) 3)));
54
55 result.totalNumOfExpansions = computeTotalNumOfExpansions(result);
56
57 // create subspaces, and calculate their bounds, average values, and
58 // size. Also compute
59 // the overall upper and lower bounds on the value of the optimal
60 // coalition structure
61 long numOfRemainingSubspaces = IntegerPartition
62 .getNumOfIntegerPartitions(numOfAgents);
63 numOfRemainingSubspaces -= disableSubspacesThatWereSearchedWhileScanningTheInput(
64 result, input);
65
66 // Set the upper and lower bounds on the value of the optimal coalition
67 // structure
68 setUpperAndLowerBoundsOnOptimalValue(input, result);
69
70 // Disable subspaces based on their bounds
71 numOfRemainingSubspaces -= disableSubspacesWithUBLowerThanTheHighestLB(
72 input, output, result);
73
74 // Print the size, upperBound, and lowerBound for each subspace
75 output.printDetailsOfSubspaces(input, result);
76
77 // If there are no more subspaces to be searched, then...
78 if (numOfRemainingSubspaces == 0) {
79 finalize(result, input, output);
80 return;
81 }
82 // Initialize the table used in the technique called: "Branch and bound
83 // in opposite direction"
84 result.idpSolver_whenRunning_ODPIP = null;
85 if (input.solverName == SolverNames.ODPIP) {
86 result.idpSolver_whenRunning_ODPIP = new IDPSolver_whenRunning_ODPIP(
87 input, result);
88 result.idpSolver_whenRunning_ODPIP
89 .initValueOfBestPartitionFound(input, maxValueForEachSize);
90 result.idpSolver_whenRunning_ODPIP.start();
91 }
92 // Calculate the value which, if found, causes the search to stop:
93 double acceptableValue = result.ipUpperBoundOnOptimalValue
94 * input.acceptableRatio / 100;
95
96 if (input.pruneSubspaces == false)
97 acceptableValue = Double.MAX_VALUE;
98
99 // Assign to each subspace a priority based on the subspace-selection
100 // function, and then sort them based on priorities
101 Node[] sortedNodes = getListOfSortedNodes(subspaces, input, result);
102
103 // Check whether the current LB of the optimal is within the acceptable
104 // bound...
105 while ((result.ipLowerBoundOnOptimalValue) < acceptableValue) {
106 // Update the integer partition graph based on the max size that was
107 // completed by IDP so far
108 if (input.solverName == SolverNames.ODPIP)
109 result.ipIntegerPartitionGraph.updateEdges(input.numOfAgents,
110 result.get_dpMaxSizeThatWasComputedSoFar());
111
112 // disable any subspaces that are reachable from the bottom node
113 if (input.solverName == SolverNames.ODPIP)
114 numOfRemainingSubspaces -= disableSubspacesReachableFromBottomNode(
115 input, result);
116
117 // Select the subspace to be searched:
118 Node nodeToBeSearched = getFirstEnabledNode(sortedNodes);
119 if (nodeToBeSearched == null)
120 break;
121
122 // if IP is helping DP, then we need to group certain integers
123 // (depending on the size for which DP has finished computing)\
124 ElementOfMultiset[] subsetToBePutAtTheBeginning = getRelevantNodes(
125 nodeToBeSearched, input, result, 1);
126
127 // Place the best subset at the beginning of the node's
128 // subspace.integers.
129 putSubsetAtTheBeginning(nodeToBeSearched,
130 subsetToBePutAtTheBeginning, input);
131
132 // Compute the upper bounds that are used in the branch-and-bound
133 // formula\
134 double[] sumOfMax = computeSumOfMax_splitOneInteger(
135 nodeToBeSearched, maxValueForEachSize, input, result);
136
137 // search the subspace
138 int numOfIntegersToSplit = 0;
139 if ((input.solverName == SolverNames.ODPIP)
140 && (subsetToBePutAtTheBeginning != null))
141 numOfIntegersToSplit = nodeToBeSearched.subspace.integers.length
142 - General.getCardinalityOfMultiset(
143 subsetToBePutAtTheBeginning);
144 numOfRemainingSubspaces -= nodeToBeSearched.subspace.search(input,
145 output, result, acceptableValue, avgValueForEachSize,
146 sumOfMax, numOfIntegersToSplit);
147
148 // update the upper bound on the optimal CS, as well as the
149 // acceptable value
150 setUpperAndLowerBoundsOnOptimalValue(input, result);
151 acceptableValue = result.ipUpperBoundOnOptimalValue
152 * input.acceptableRatio / 100;
153 if (input.pruneSubspaces == false)
154 acceptableValue = Double.MAX_VALUE;
155
156 // update the lower bound on the optimal CS
157 if (result.ipLowerBoundOnOptimalValue < result
158 .get_ipValueOfBestCSFound()) {
159 result.ipLowerBoundOnOptimalValue = result
160 .get_ipValueOfBestCSFound();
161 numOfRemainingSubspaces -= disableSubspacesWithUBLowerThanTheHighestLB(
162 input, output, result);
163 }
164 // If there are no more subspaces to be searched, or if we found a
165 // good enough value, then...
166 if ((numOfRemainingSubspaces == 0)
167 || ((input.solverName == SolverNames.ODPIP) && (result
168 .get_dpMaxSizeThatWasComputedSoFar() >= ((int) Math
169 .floor(2 * input.numOfAgents
170 / (double) 3))))) {
171 break;
172 }
173 }
174 // prepare final result of IP before terminating
175 finalize(result, input, output);
176 if (result.idpSolver_whenRunning_ODPIP != null)
177 result.idpSolver_whenRunning_ODPIP.setStop(true);
178 }
179
180 // *****************************************************************************************************
181
182 /**
183 * Disable any subspaces that are reachable from the bottom node, using only
184 * the movements that have been evaluated by IDP so far.
185 *
186 * Returns the number of subspaces that it pruned.
187 */
188 private long disableSubspacesReachableFromBottomNode(Input input,
189 Result result) {
190 Node bottomNode = result.ipIntegerPartitionGraph.nodes[0][0];
191
192 // get the list of nodes that are reachable from the bottom node.
193 Node[] reachableNodes = result.ipIntegerPartitionGraph
194 .getReachableNodes(bottomNode);
195
196 // disable all those nodes
197 int numOfDisabledNodes = 0;
198 if (reachableNodes != null)
199 for (int i = 0; i < reachableNodes.length; i++)
200 if (reachableNodes[i].subspace.enabled) {
201 reachableNodes[i].subspace.enabled = false;
202 // System.out.println(input.problemID+" - &&&&&& IDP pruned
203 // the subspace
204 // "+General.convertArrayToString(reachableNodes[i].subspace.integersSortedAscendingly));
205 numOfDisabledNodes++;
206 }
207 return (numOfDisabledNodes);
208 }
209
210 // *****************************************************************************************************
211
212 /**
213 * Prepare the final result of IP before terminating
214 */
215 private void finalize(Result result, Input input, Output output) {
216 if (input.solverName == SolverNames.ODPIP) {
217 if (result.get_dpBestCSFound() != null)
218 result.updateIPSolution(result.get_dpBestCSFound(),
219 result.get_dpValueOfBestCSFound());
220 }
221 result.ipTime = System.currentTimeMillis() - result.ipStartTime;
222 output.emptyStringBufferContentsIntoOutputFiles(input);
223 output.printFinalResultsOfIPToFiles(input, result);
224 }
225
226 // *****************************************************************************************************
227
228 /**
229 * Finds the best out of the first and the last level of the Integer
230 * partition graph
231 */
232 private void searchFirstAndLastLevel(Input input, Result result) {
233 int numOfAgents = input.numOfAgents;
234 boolean CS1IsFeasible = true;
235 boolean CS2IsFeasible = true;
236
237 // Calculate the value of the coalition structure that is made of
238 // singletons
239 int[][] CS1 = new int[numOfAgents][1];
240 for (int i = 0; i <= numOfAgents - 1; i++)
241 CS1[i][0] = i + 1;
242
243 // Calculate the value of the coalition structure that contains the
244 // grand coalition
245 int[][] CS2 = new int[1][numOfAgents];
246 for (int i = 0; i <= numOfAgents - 1; i++)
247 CS2[0][i] = i + 1;
248
249 if (input.feasibleCoalitions != null) {
250 // Check whether CS1 is feasible
251 for (int i = 0; i < CS1.length; i++) {
252 int curCoalitionInBitFormat = Combinations
253 .convertCombinationFromByteToBitFormat(CS1[i]);
254 if (input.feasibleCoalitions
255 .contains(curCoalitionInBitFormat) == false) {
256 CS1IsFeasible = false;
257 break;
258 }
259 }
260 // Check whether CS2 is feasible
261 for (int i = 0; i < CS2.length; i++) {
262 int curCoalitionInBitFormat = Combinations
263 .convertCombinationFromByteToBitFormat(CS2[i]);
264 if (input.feasibleCoalitions
265 .contains(curCoalitionInBitFormat) == false) {
266 CS2IsFeasible = false;
267 break;
268 }
269 }
270 }
271 // Compute the values of CS1 and CS2
272 double valueOfCS1 = input.getCoalitionStructureValue(CS1);
273 double valueOfCS2 = input.getCoalitionStructureValue(CS2);
274
275 // Compare the two values
276 if (((CS1IsFeasible) && (CS2IsFeasible == false)) || ((CS1IsFeasible)
277 && (CS2IsFeasible) && (valueOfCS1 >= valueOfCS2))) {
278 result.updateIPSolution(CS1, valueOfCS1);
279 }
280 if (((CS2IsFeasible) && (CS1IsFeasible == false)) || ((CS2IsFeasible)
281 && (CS1IsFeasible) && (valueOfCS2 >= valueOfCS1))) {
282 result.updateIPSolution(CS2, valueOfCS2);
283 }
284 }
285
286 // ******************************************************************************************************
287
288 /**
289 * create subspaces, and calculate their bounds, average values, and size.
290 * Also compute the overall upper and lower bounds on the value of the
291 * optimal coalition structure
292 */
293 private Subspace[][] initSubspaces(double[] avgValueForEachSize,
294 double[][] maxValueForEachSize, Input input) {
295 // Generate all integer partitions
296 int[][][] integers = IntegerPartition.getIntegerPartitions(
297 input.numOfAgents, input.orderIntegerPartitionsAscendingly);
298
299 // Initialize all subspaces and compute the upper and lower bounds on
300 // the optimal value
301 Subspace[][] subspaces = new Subspace[integers.length][];
302 for (int level = 0; level < input.numOfAgents; level++) {
303 subspaces[level] = new Subspace[integers[level].length];
304 for (int i = 0; i < integers[level].length; i++) {
305 subspaces[level][i] = new Subspace(integers[level][i],
306 avgValueForEachSize, maxValueForEachSize, input);
307 }
308 }
309 return (subspaces);
310 }
311
312 // ******************************************************************************************************
313
314 /**
315 * For any subspace "S", set "S.enabled" to "false" if it has been searched
316 * while scanning the input
317 */
318 private long disableSubspacesThatWereSearchedWhileScanningTheInput(
319 Result result, Input input) {
320 Node[][] nodes = result.ipIntegerPartitionGraph.nodes;
321 long numOfSubspacesThatThisMethodHasDisabled = 0;
322 for (int level = 0; level < nodes.length; level++) {
323 for (int i = 0; i < nodes[level].length; i++) {
324 Subspace curSubspace = nodes[level][i].subspace;
325 // identify whether the current integer partition is of size "1"
326 // or "2" or "numOfAgents"
327 if ((level == 0) || (level == 1)
328 || (level == (input.numOfAgents - 1))) {
329 if (curSubspace.enabled) {
330 curSubspace.enabled = false;
331 numOfSubspacesThatThisMethodHasDisabled++;
332 }
333 }
334 }
335 }
336 return (numOfSubspacesThatThisMethodHasDisabled);
337 }
338
339 // ******************************************************************************************************
340
341 /**
342 * Calculate the highest value, 2nd highest, 3rd highest, and so on, as long
343 * as this is useful (e.g. given 15 agents, for the coalitions of size 4, we
344 * only need to calculate the highest 3 values since it is not possible to
345 * have more than 3 fours in a single integer partition
346 */
347 private double[][] setMaxValueForEachSize(Input input) {
348 // Initialization
349 int numOfAgents = input.numOfAgents;
350 int[] numOfRequiredMaxValues = new int[numOfAgents];
351 long[] numOfCoalitions = new long[numOfAgents];
352 double[][] maxValue = new double[numOfAgents][];
353 for (int size = 1; size <= numOfAgents; size++) {
354 numOfRequiredMaxValues[size - 1] = (int) Math
355 .floor(numOfAgents / (double) size);
356 numOfCoalitions[size - 1] = Combinations
357 .binomialCoefficient(numOfAgents, size);
358 maxValue[size - 1] = new double[numOfRequiredMaxValues[size - 1]];
359 for (int i = 0; i < maxValue[size - 1].length; i++)
360 maxValue[size - 1][i] = 0;
361 }
362 final boolean constraintsExist;
363 if (input.feasibleCoalitions == null)
364 constraintsExist = false;
365 else
366 constraintsExist = true;
367
368 for (int coalitionInBitFormat = (int) Math.pow(2, numOfAgents)
369 - 1; coalitionInBitFormat > 0; coalitionInBitFormat--)
370 if ((constraintsExist == false) || (input.feasibleCoalitions
371 .contains(coalitionInBitFormat)))
372 // if a coalition is feasible, and it's upperBound is greater than
373 // the smallest element in "curMax" then update "curMax"
374 {
375 int size = Combinations.getSizeOfCombinationInBitFormat(
376 coalitionInBitFormat, numOfAgents);
377 double[] curMaxValue = maxValue[size - 1];
378 int j = numOfRequiredMaxValues[size - 1] - 1;
379 if (input.getCoalitionValue(
380 coalitionInBitFormat) > curMaxValue[j]) {
381 while ((j > 0) && (input.getCoalitionValue(
382 coalitionInBitFormat) > curMaxValue[j - 1])) {
383 curMaxValue[j] = curMaxValue[j - 1];
384 j--;
385 }
386 curMaxValue[j] = input
387 .getCoalitionValue(coalitionInBitFormat);
388 }
389 }
390 return (maxValue);
391 }
392
393 // ******************************************************************************************************
394
395 /**
396 * This method disables any subspaces with a UB lower that the value of the
397 * current best solution (i.e. lower than LB*), and returns the number of
398 * subspaces that this method has disabled
399 */
400 private long disableSubspacesWithUBLowerThanTheHighestLB(Input input,
401 Output output, Result result) {
402 Node[][] nodes = result.ipIntegerPartitionGraph.nodes;
403 if (input.pruneSubspaces == false)
404 return (0);
405
406 long numOfSubspacesThatThisMethodHasDisabled = 0;
407
408 for (int level = 0; level < nodes.length; level++) {
409 for (int i = 0; i < nodes[level].length; i++) {
410 Subspace curSubspace = nodes[level][i].subspace;
411 if (curSubspace.enabled == true) {
412 // if( curSubspace.UB < result.ipLowerBoundOnOptimalValue )
413 if (curSubspace.UB
414 - result.ipLowerBoundOnOptimalValue < -0.00000000005) {
415 curSubspace.enabled = false;
416 numOfSubspacesThatThisMethodHasDisabled += 1;
417 }
418 }
419 }
420 }
421 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
422 input, result);
423 return (numOfSubspacesThatThisMethodHasDisabled);
424 }
425
426 // ******************************************************************************************************
427
428 /**
429 * Assign to each node a priority based on the subspace-selection function,
430 * and then sort the nodes based on their priorities.
431 */
432 private Node[] getListOfSortedNodes(Subspace[][] subspaces, Input input,
433 Result result) {
434 Node[][] nodes = result.ipIntegerPartitionGraph.nodes;
435
436 // *******************************************
437 // *** ***
438 // *** Assign priorities to nodes ***
439 // *** ***
440 // *******************************************
441
442 for (int level = 0; level < nodes.length; level++) { // For each level
443 for (int i = 0; i < nodes[level].length; i++) // For each subspace
444 // in the current
445 // level
446 {
447 Subspace curSubspace = nodes[level][i].subspace;
448 curSubspace.priority = curSubspace.UB;
449 // curSubspace.priority = -1 * curSubspace.sizeOfSubspace;
450 // curSubspace.priority = curSubspace.LB;
451 }
452 }
453
454 // ********************************************************
455 // *** ***
456 // *** Sort subspaces based on their priorities ***
457 // *** ***
458 // ********************************************************
459
460 // Initialization
461 Node[] sortedNodes = new Node[IntegerPartition
462 .getNumOfIntegerPartitions(input.numOfAgents)];
463 int k = 0;
464 for (int level = 0; level < nodes.length; level++) { // For each level
465 for (int i = 0; i < nodes[level].length; i++) { // For each subspace
466 // in the current
467 // level
468 sortedNodes[k] = nodes[level][i];
469 k++;
470 }
471 }
472 // Sorting
473 for (int i = sortedNodes.length - 1; i >= 0; i--) // start at the end of
474 // the array
475 {
476 int indexOfSmallestElement = i; // (1) default value of the index
477 // the of smallest element.
478 for (int j = i; j >= 0; j--) // (2) loop from the end of unsorted
479 // zone to the beginning of the
480 // array.
481 {
482 // compare current element to smallest one
483 if ((sortedNodes[j].subspace.priority < sortedNodes[indexOfSmallestElement].subspace.priority)
484 || ((sortedNodes[j].subspace.priority == sortedNodes[indexOfSmallestElement].subspace.priority)
485 && (sortedNodes[j].subspace.UB < sortedNodes[indexOfSmallestElement].subspace.UB)))
486 indexOfSmallestElement = j; // if it's smaller, it becomes
487 // the new smallest
488 }
489 // swap the two values
490 Node temp = sortedNodes[i];
491 sortedNodes[i] = sortedNodes[indexOfSmallestElement];
492 sortedNodes[indexOfSmallestElement] = temp;
493 }
494 return (sortedNodes);
495 }
496
497 // ******************************************************************************************************
498
499 /**
500 * Returns the first enabled subspace in the given list of subspaces
501 */
502 private Node getFirstEnabledNode(Node[] sortedNodes) {
503 for (int i = 0; i < sortedNodes.length; i++) {
504 if (sortedNodes[i].subspace.enabled)
505 return (sortedNodes[i]);
506 }
507 return (null);
508 }
509
510 // ******************************************************************************************************
511
512 /**
513 * This method sets "result.ipUpperBoundOnOptimalValue" to the
514 * "initialValue", and searches through the upper bounds of the "enabled"
515 * subspaces to see if there is one that is greater than that value
516 */
517 private void setUpperAndLowerBoundsOnOptimalValue(Input input,
518 Result result) {
519 result.ipUpperBoundOnOptimalValue = result.get_ipValueOfBestCSFound();
520 result.ipLowerBoundOnOptimalValue = result.get_ipValueOfBestCSFound();
521
522 Node[][] nodes = result.ipIntegerPartitionGraph.nodes;
523 for (int level = 0; level < nodes.length; level++) {
524 for (int i = 0; i < nodes[level].length; i++) {
525 Subspace curSubspace = nodes[level][i].subspace;
526 if (curSubspace.enabled) {
527 if (result.ipUpperBoundOnOptimalValue < curSubspace.UB)
528 result.ipUpperBoundOnOptimalValue = curSubspace.UB;
529
530 if (result.ipLowerBoundOnOptimalValue < curSubspace.LB)
531 result.ipLowerBoundOnOptimalValue = curSubspace.LB;
532 }
533 }
534 }
535 }
536
537 // ******************************************************************************************************
538
539 /**
540 * This method initializes sumOfMax, which is used in
541 * "Subspace.search_useBranchAndBound". Here, none of the values in f are
542 * used.
543 */
544 private double[] computeSumOfMax_splitNoIntegers(int[] integers,
545 double[][] maxValueForEachSize) {
546 // Initialization
547 double[] sumOfMax = new double[integers.length + 1];
548
549 // Compute the upper bounds of the last list
550 sumOfMax[integers.length] = maxValueForEachSize[integers[integers.length
551 - 1] - 1][0];
552
553 // Compute the upper bounds of the remaining lists
554 int j = 0;
555 for (int i = integers.length - 1; i > 0; i--) {
556 if (integers[i - 1] == integers[i])
557 j++;
558 else
559 j = 0;
560 sumOfMax[i] = sumOfMax[i + 1]
561 + maxValueForEachSize[integers[i - 1] - 1][j];
562 }
563 return (sumOfMax);
564 }
565
566 // ******************************************************************************************************
567
568 /**
569 * This method initializes sumOfMax, which is used in
570 * "Subspace.search_useBranchAndBound". Here, none of the values in f are
571 * used.
572 */
573 private double[] computeSumOfMax_usefInsteadOfv(int[] integers,
574 double[][] maxValueForEachSize, Result result) {
575 // Initialization
576 double[] sumOfMax = new double[integers.length + 1];
577
578 // Compute the upper bounds of the last list
579 sumOfMax[integers.length] = result
580 .get_max_f(integers[integers.length - 1] - 1);
581 for (int i = integers.length - 1; i > 0; i--)
582 sumOfMax[i] = sumOfMax[i + 1]
583 + result.get_max_f(integers[i - 1] - 1);
584
585 return (sumOfMax);
586 }
587
588 // ******************************************************************************************************
589
590 /**
591 * This method initializes sumOfMax, which is used in
592 * "Subspace.search_useBranchAndBound". Here, none of the values in f are
593 * used.
594 */
595 private double computeUpperBound(ElementOfMultiset[] integers,
596 double[][] maxValueForEachSize) {
597 double upperBound = 0;
598 for (int i = 0; i < integers.length; i++) {
599 int j = 0;
600 for (int k = 0; k < integers[i].repetition; k++) {
601 upperBound += maxValueForEachSize[integers[i].element - 1][j];
602 j++;
603 }
604 }
605 return (upperBound);
606 }
607
608 // ******************************************************************************************************
609
610 /**
611 * This method initializes sumOfMax, which is used in
612 * "Subspace.search_useBranchAndBound"
613 */
614 private double[] computeSumOfMax_splitManyIntegers(Node node,
615 double[][] maxValueForEachSize, Input input,
616 ElementOfMultiset[] subsetToBePutAtTheBeginning, Result result) {
617 if ((input.solverName == SolverNames.IP)
618 || (node.subspace.relevantNodes == null))
619 return (computeSumOfMax_splitNoIntegers(node.subspace.integers,
620 maxValueForEachSize));
621
622 // Initialization
623 int[] integers = node.subspace.integers;
624 Node[] relevantNodes = node.subspace.relevantNodes;
625 double[] sumOfMax = new double[integers.length + 1];
626
627 // Count the number of integers in the subset that will be put at the
628 // beginning, i.e., the subset containing the
629 // integers that are common between this node, and every relevant node
630 // (i.e., the integers that will not be split)
631 int numOfIntegersToBePutAtTheBeginning = 0;
632 if (subsetToBePutAtTheBeginning != null)
633 for (int i = 0; i < subsetToBePutAtTheBeginning.length; i++)
634 numOfIntegersToBePutAtTheBeginning += subsetToBePutAtTheBeginning[i].repetition;
635
636 // For this node, and every relevant node, we are going to keep a copy
637 // of its integer partition
638 int[][] tempIntegers = new int[relevantNodes.length + 1][];
639 int[][] tempIntegerRoots = new int[relevantNodes.length + 1][];
640 tempIntegers[0] = General
641 .copyArray(node.integerPartition.partsSortedAscendingly);
642 tempIntegerRoots[0] = General.copyArray(node.tempIntegerRoots);
643 for (int i = 1; i < tempIntegers.length; i++) {
644 tempIntegers[i] = General.copyArray(relevantNodes[i
645 - 1].integerPartition.partsSortedAscendingly);
646 tempIntegerRoots[i] = General
647 .copyArray(relevantNodes[i - 1].tempIntegerRoots);
648 }
649 // Compute sumOfMax[1]...
650 double maxUB = node.subspace.UB;
651 for (int i = 0; i < relevantNodes.length; i++) {
652 if (maxUB < relevantNodes[i].subspace.UB) {
653 maxUB = relevantNodes[i].subspace.UB;
654 }
655 }
656 sumOfMax[1] = maxUB;
657 int index = 1;
658
659 // Compute sumOfMax[i] : i>1
660 while (index < integers.length) {
661 sumOfMax[index + 1] = Integer.MIN_VALUE;
662 int curInteger = integers[index - 1];
663 for (int i = 0; i < tempIntegers.length; i++) {
664 ElementOfMultiset[] set = null;
665 ElementOfMultiset[] subset = null;
666 if (index <= numOfIntegersToBePutAtTheBeginning) {
667 subset = new ElementOfMultiset[1];
668 subset[0] = new ElementOfMultiset(curInteger, 1);
669 } else {
670 set = getSetOfIntegersGivenTheirRoot(tempIntegers[i],
671 tempIntegerRoots[i], curInteger);
672 subset = getSubsetOfIntegersGivenTheirSum(set, curInteger);
673 if (subset == null) {
674 subset = new ElementOfMultiset[1];
675 subset[0] = new ElementOfMultiset(curInteger, 1);
676 }
677 }
678 if (i == 0) {
679 removeSubset(node, subset, tempIntegers, tempIntegerRoots,
680 i);
681 } else {
682 removeSubset(relevantNodes[i - 1], subset, tempIntegers,
683 tempIntegerRoots, i);
684 }
685 double[] tempSumOfMax = computeSumOfMax_splitNoIntegers(
686 tempIntegers[i], maxValueForEachSize);
687 if (sumOfMax[index + 1] < tempSumOfMax[1])
688 sumOfMax[index + 1] = tempSumOfMax[1];
689 }
690 // Compute the bounds using f, and see if this improves things...
691 double[] sumOfMaxUsingf = computeSumOfMax_usefInsteadOfv(
692 tempIntegers[0], maxValueForEachSize, result);
693 if (sumOfMax[index + 1] > sumOfMaxUsingf[1])
694 sumOfMax[index + 1] = sumOfMaxUsingf[1];
695
696 index++;
697 }
698 return (sumOfMax);
699 }
700
701 // ******************************************************************************************************
702
703 /**
704 * This method initializes sumOfMax, which is used in
705 * "Subspace.search_useBranchAndBound" IMPORTANT: this version assumes that
706 * there is ONLY ONE integer that will be split at the end
707 */
708 private double[] computeSumOfMax_splitOneInteger(Node node,
709 double[][] maxValueForEachSize, Input input, Result result) {
710 if ((input.solverName == SolverNames.IP)
711 || (node.subspace.relevantNodes == null))
712 return (computeSumOfMax_splitNoIntegers(node.subspace.integers,
713 maxValueForEachSize));
714
715 int[] integers = node.subspace.integers;
716 double[] sumOfMax = new double[integers.length + 1];
717
718 // compute the maximum upper bound of this node and all relevant nodes
719 double maxUB = node.subspace.UB;
720 for (int i = 0; i < node.subspace.relevantNodes.length; i++)
721 if (maxUB < node.subspace.relevantNodes[i].subspace.UB)
722 maxUB = node.subspace.relevantNodes[i].subspace.UB;
723
724 // Compute the upper bound of the last list
725 sumOfMax[integers.length] = maxValueForEachSize[integers[integers.length
726 - 1] - 1][0] + (maxUB - node.subspace.UB);
727 double max_f = result.get_max_f(integers[integers.length - 1] - 1);
728 if ((max_f != 0) && (sumOfMax[integers.length] > max_f))
729 sumOfMax[integers.length] = max_f;
730
731 sumOfMax[integers.length - 1] = sumOfMax[integers.length]
732 + maxValueForEachSize[integers[integers.length - 2] - 1][0];
733 int k = 2;
734
735 // Compute the upper bounds of the remaining lists
736 int x = integers.length - k;
737 int j = 0;
738 for (int i = x; i > 0; i--) {
739 if (integers[i - 1] == integers[i])
740 j++;
741 else
742 j = 0;
743 sumOfMax[i] = sumOfMax[i + 1]
744 + maxValueForEachSize[integers[i - 1] - 1][j];
745 k++;
746 }
747 return (sumOfMax);
748 }
749
750 // ******************************************************************************************************
751
752 /**
753 * This method initializes sumOfMax, which is used in
754 * "Subspace.search_useBranchAndBound"
755 */
756 private double[] computeSumOfMax_splitOneInteger_improveUsingf(Node node,
757 double[][] maxValueForEachSize, Input input, Result result) {
758 if ((input.solverName == SolverNames.IP)
759 || (node.subspace.relevantNodes == null))
760 return (computeSumOfMax_splitNoIntegers(node.subspace.integers,
761 maxValueForEachSize));
762
763 // Initialization
764 int[] integers = node.subspace.integers;
765 double[] sumOfMax = new double[integers.length + 1];
766
767 // Basically, "sumOfMax[i] = arrayOfMax[i][0] + arrayOfMax[i][1] + ... "
768 double[][] arrayOfMax = new double[integers.length + 1][];
769 for (int i = 1; i < arrayOfMax.length; i++) {
770 arrayOfMax[i] = new double[arrayOfMax.length - i];
771 }
772 // compute the maximum upper bound of this node and all relevant nodes
773 double maxUB = node.subspace.UB;
774 for (int i = 0; i < node.subspace.relevantNodes.length; i++)
775 if (maxUB < node.subspace.relevantNodes[i].subspace.UB)
776 maxUB = node.subspace.relevantNodes[i].subspace.UB;
777
778 // Compute the upper bound of the last list
779 sumOfMax[integers.length] = maxValueForEachSize[integers[integers.length
780 - 1] - 1][0] + (maxUB - node.subspace.UB);
781 double max_f = result.get_max_f(integers[integers.length - 1] - 1);
782 if ((max_f != 0) && (sumOfMax[integers.length] > max_f))
783 sumOfMax[integers.length] = max_f;
784 sumOfMax[integers.length - 1] = sumOfMax[integers.length]
785 + maxValueForEachSize[integers[integers.length - 2] - 1][0];
786
787 // Update arrayOfMax
788 for (int i = 1; i < arrayOfMax.length; i++)
789 arrayOfMax[i][arrayOfMax[i].length
790 - 1] = maxValueForEachSize[integers[integers.length - 1]
791 - 1][0] + (maxUB - node.subspace.UB);
792 for (int i = 1; i < arrayOfMax.length - 1; i++)
793 arrayOfMax[i][arrayOfMax[i].length
794 - 2] = maxValueForEachSize[integers[integers.length - 2]
795 - 1][0];
796
797 // Compute the upper bounds of the remaining lists
798 int k = 2;
799 int x = integers.length - k;
800 int j = 0;
801 for (int i = x; i > 0; i--) {
802 if (integers[i - 1] == integers[i])
803 j++;
804 else
805 j = 0;
806 sumOfMax[i] = sumOfMax[i + 1]
807 + maxValueForEachSize[integers[i - 1] - 1][j];
808
809 // Update arrayOfMax
810 for (int w = 1; w < arrayOfMax.length - k; w++)
811 arrayOfMax[w][arrayOfMax[w].length
812 - (k + 1)] = maxValueForEachSize[integers[i - 1]
813 - 1][j];
814 k++;
815 }
816 // the technique below did not make any difference in performace, so, to
817 // be safe, I disabled it
818 if (input.solverName == SolverNames.ODPIP)
819 improveUpperBoundUsingf(input.numOfAgents, sumOfMax, arrayOfMax,
820 maxValueForEachSize, integers, result);
821
822 return (sumOfMax);
823 }
824
825 // ******************************************************************************************************
826
827 /**
828 * Try to reduce the upper bound using f. Example: Given [1,1,2,3],
829 * max_v1+max_v1+max_v2 can be replaced with: max_f4.
830 */
831 private void improveUpperBoundUsingf(int numOfAgents, double[] sumOfMax,
832 double[][] arrayOfMax, double[][] maxValueForEachSize,
833 int[] integers, Result result) {
834 // ******************************************************************************
835 // **** ****
836 // **** try to start from the first list, and head towards the last list
837 // ****
838 // **** ****
839 // ******************************************************************************
840
841 // for each list "i"...
842 for (int i = 1; i < sumOfMax.length; i++) // try to reduce "sumOfMax[i]"
843 {
844 // Initialization
845 int start = i;
846 double newSumOfMax = 0;
847 int[] numOfTimesWeComputedASizeRegularly = new int[numOfAgents + 1];
848 for (int size = 0; size <= numOfAgents; size++)
849 numOfTimesWeComputedASizeRegularly[size] = 0;
850
851 /*
852 * In the 1st loop, we group a few integers (from "start" to "end"),
853 * where "start" equals "i" In the 2nd loop, we group a few integers
854 * (from "start" to "end"), where "start" equals the. previous "end"
855 * plus 1. This is repeated until we reach the last integer...
856 */
857 do {
858 // every time we enter this loop, we have the same "i", but a
859 // new "start"
860 int sumOfIntegers = 0;
861 int bestSumOfIntegers = -1;
862 double bestSavings = 0;
863 int bestEnd = 0;
864 boolean exitLoop = false;
865 // Given the current "start", we want to find the best "end"
866 for (int end = start; end < sumOfMax.length; end++) {
867 sumOfIntegers += integers[end - 1];
868 if (sumOfIntegers > result
869 .get_dpMaxSizeThatWasComputedSoFar()) {
870 exitLoop = true;
871 break;
872 }
873 // Compute the savings if we use: "result.max_f[
874 // sumOfIntegers-1 ]" instead
875 // of: "arrayOfMax[i][start]+...+arrayOfMax[i][end]"
876 double savings = -1 * result.get_max_f(sumOfIntegers - 1);
877 for (int j = start; j <= end; j++)
878 savings += arrayOfMax[i][j - i];
879
880 if (bestSavings < savings) {
881 bestSavings = savings;
882 bestSumOfIntegers = sumOfIntegers;
883 bestEnd = end;
884 }
885 }
886 // if even the best savings are 0, then the current start is
887 // useless...
888 if (bestSavings < 0.0000000001) {
889 int curSize = integers[start - 1];
890 newSumOfMax += maxValueForEachSize[curSize
891 - 1][numOfTimesWeComputedASizeRegularly[curSize]];
892 numOfTimesWeComputedASizeRegularly[curSize]++;
893 start++;
894 } else {
895 newSumOfMax += result.get_max_f(bestSumOfIntegers - 1);
896 start = bestEnd + 1;
897 }
898 } while (start < sumOfMax.length);
899
900 if (sumOfMax[i] > newSumOfMax)
901 sumOfMax[i] = newSumOfMax;
902 }
903 }
904
905 // ******************************************************************************************************
906
907 /**
908 * select the subset of integers that will be put at the beginning. The
909 * remaining integers will be put at the end and will be searched using the
910 * f table, not the v table.
911 *
912 * Here, you explicitly specify the number of integers to be placed at the
913 * end.
914 *
915 * Returns the subset of integers that is common between the node and all
916 * reachable nodes.
917 */
918 private ElementOfMultiset[] getRelevantNodes(Node node, Input input,
919 Result result, int numOfIntegersToSplitAtTheEnd) {
920 if (input.solverName == SolverNames.IP) {
921 node.subspace.relevantNodes = null;
922 return (null);
923 }
924 int numOfIntegersInNode = node.integerPartition.partsSortedAscendingly.length;
925
926 // get the list of nodes that are reachable from the original node.
927 Node[] reachableNodes = result.ipIntegerPartitionGraph
928 .getReachableNodes(node);
929 if (reachableNodes == null) {
930 node.subspace.relevantNodes = null;
931 return (null);
932 }
933 // create an iterator that will iterate over subsets of the original
934 // integer partition
935 SubsetsOfMultiset[] subsetIterators = new SubsetsOfMultiset[numOfIntegersToSplitAtTheEnd];
936 for (int s = 0; s < numOfIntegersToSplitAtTheEnd; s++)
937 subsetIterators[s] = new SubsetsOfMultiset(
938 node.integerPartition.sortedMultiset,
939 numOfIntegersInNode - (s + 1), false);
940
941 // Initialization
942 ElementOfMultiset[] bestSubset = null;
943 long bestSavings = 0;
944 int bestNumOfRelevantNodes = 0;
945
946 for (int s = 0; s < numOfIntegersToSplitAtTheEnd; s++) {
947 // Iterate over all subsets of size: s+1
948 ElementOfMultiset[] subset = subsetIterators[s].getNextSubset();
949 while (subset != null) {
950 long savings = 0;
951 int numOfRelevantSubspaces = 0;
952 // out of all nodes reachable from "node", find the ones that
953 // contain "subset"
954 for (int i = 0; i < reachableNodes.length; i++) {
955 if ((reachableNodes[i].integerPartition.contains(subset))
956 && (reachableNodes[i].subspace.enabled)) {
957 savings += reachableNodes[i].subspace.totalNumOfExpansionsInSubspace;
958 numOfRelevantSubspaces++;
959 }
960 }
961 // update the best subset
962 if (bestSavings < savings) {
963 bestSavings = savings;
964 bestSubset = General.copyMultiset(subset);
965 bestNumOfRelevantNodes = numOfRelevantSubspaces;
966 }
967 // Get the next subset
968 subset = subsetIterators[s].getNextSubset();
969 }
970 }
971 // get the list of relevant subspaces, based on the best subset
972 int index = 0;
973 if (bestNumOfRelevantNodes == 0) {
974 node.subspace.relevantNodes = null;
975 return (null);
976 } else {
977 node.subspace.relevantNodes = new Node[bestNumOfRelevantNodes];
978 for (int i = 0; i < reachableNodes.length; i++) {
979 if ((reachableNodes[i].integerPartition.contains(bestSubset))
980 && (reachableNodes[i].subspace.enabled)) {
981 node.subspace.relevantNodes[index] = reachableNodes[i];
982 index++;
983 }
984 }
985 return (bestSubset);
986 }
987 }
988
989 // ******************************************************************************************************
990
991 /**
992 * select the subset of integers that will be put at the beginning. The
993 * remaining integers will be put at the end and will be searched using the
994 * f table, not the v table.
995 *
996 * Here, the number of integers to be put at the end is not limited; it can
997 * be as large as needed
998 *
999 * Returns the subset of integers that is common between the node and all
1000 * reachable nodes.
1001 */
1002 private ElementOfMultiset[] getRelevantNodes(Node node, Input input,
1003 Result result) {
1004 if (input.solverName == SolverNames.IP) {
1005 node.subspace.relevantNodes = null;
1006 return (null);
1007 }
1008 // get the list of nodes that are reachable from the original node.
1009 Node[] reachableNodes = result.ipIntegerPartitionGraph
1010 .getReachableNodes(node);
1011 if (reachableNodes == null) {
1012 node.subspace.relevantNodes = null;
1013 return (null);
1014 }
1015 // Count how many of those nodes are actually enabled
1016 int numOfEnabledReachableNodes = 0;
1017 for (int j = 0; j < reachableNodes.length; j++)
1018 if (reachableNodes[j].subspace.enabled)
1019 numOfEnabledReachableNodes++;
1020
1021 // Put all reachable, enabled, nodes in the list of relevant nodes
1022 if (numOfEnabledReachableNodes == 0) {
1023 node.subspace.relevantNodes = null;
1024 return (null);
1025 } else {
1026 node.subspace.relevantNodes = new Node[numOfEnabledReachableNodes];
1027 int index = 0;
1028 for (int j = 0; j < reachableNodes.length; j++) {
1029 if (reachableNodes[j].subspace.enabled) {
1030 node.subspace.relevantNodes[index] = reachableNodes[j];
1031 index++;
1032 }
1033 }
1034 }
1035 Node[] relevantNodes = node.subspace.relevantNodes;
1036
1037 // Create a copy of the multiset representation of the integer partition
1038 // of the node
1039 ElementOfMultiset[] copyOfMultiset = General
1040 .copyMultiset(node.integerPartition.sortedMultiset);
1041
1042 // For every element in the multiset
1043 for (int i = 0; i < copyOfMultiset.length; i++) {
1044 // count the minimum number of times this element appears in a
1045 // reachable node
1046 int curElement = copyOfMultiset[i].element;
1047 int minNumOfRepetitions = copyOfMultiset[i].repetition;
1048 for (int j = 0; j < relevantNodes.length; j++) {
1049 boolean foundElement = false;
1050 ElementOfMultiset[] multiset = relevantNodes[j].integerPartition.sortedMultiset;
1051 for (int k = 0; k < multiset.length; k++)
1052 if (multiset[k].element == curElement) {
1053 foundElement = true;
1054 if (minNumOfRepetitions > multiset[k].repetition)
1055 minNumOfRepetitions = multiset[k].repetition;
1056 break;
1057 }
1058 if (foundElement == false) {
1059 minNumOfRepetitions = 0;
1060 break;
1061 }
1062 }
1063 // set the number of repetitions to be the minimum
1064 copyOfMultiset[i].repetition = minNumOfRepetitions;
1065 }
1066 // Get rid of any elements that are repeated 0 times, and return the
1067 // remaining
1068 int counter = 0;
1069 for (int i = 0; i < copyOfMultiset.length; i++) {
1070 if (copyOfMultiset[i].repetition > 0) {
1071 counter++;
1072 }
1073 }
1074 if (counter == 0) {
1075 return (null);
1076 } else {
1077 ElementOfMultiset[] subset = new ElementOfMultiset[counter];
1078 int index = 0;
1079 for (int i = 0; i < copyOfMultiset.length; i++)
1080 if (copyOfMultiset[i].repetition > 0) {
1081 subset[index] = new ElementOfMultiset(
1082 copyOfMultiset[i].element,
1083 copyOfMultiset[i].repetition);
1084 index++;
1085 }
1086 return (subset);
1087 }
1088 }
1089
1090 // ******************************************************************************************************
1091
1092 /**
1093 * Place the best subset at the beginning of the node's subspace.integers.
1094 * Also, place it at the beginning of every relevant node's
1095 * subspace.integers.
1096 */
1097 private void putSubsetAtTheBeginning(Node node, ElementOfMultiset[] subset,
1098 Input input) {
1099 if ((subset == null) || (input.solverName == SolverNames.IP))
1100 return;
1101
1102 // Put all remaining integers (i.e., those not in the subset) in a set
1103 // represented as a MULTISET
1104 ElementOfMultiset[] remainingIntegers_multiset = General
1105 .copyMultiset(node.integerPartition.sortedMultiset);
1106 for (int i = 0; i < subset.length; i++)
1107 for (int j = 0; j < remainingIntegers_multiset.length; j++)
1108 if (remainingIntegers_multiset[j].element == subset[i].element) {
1109 remainingIntegers_multiset[j].repetition -= subset[i].repetition;
1110 break;
1111 }
1112 // Count the total number of remaining integers (i.e., those that are
1113 // not in the subset)
1114 int counter = 0;
1115 for (int i = 0; i < remainingIntegers_multiset.length; i++)
1116 counter += remainingIntegers_multiset[i].repetition;
1117
1118 // Put all remaining integers (i.e., those not in the subset) in a set
1119 // represented as an ARRAY.
1120 int[] remainingIntegers_array = new int[counter];
1121 int index = 0;
1122 for (int i = 0; i < remainingIntegers_multiset.length; i++)
1123 for (int j = 0; j < remainingIntegers_multiset[i].repetition; j++) {
1124 remainingIntegers_array[index] = remainingIntegers_multiset[i].element;
1125 index++;
1126 }
1127 // place the subset at the beginning, and the remaining integers at the
1128 // end
1129 int[] newIntegers = new int[node.subspace.integers.length];
1130 int index1 = 0;
1131 int index2 = newIntegers.length - counter;
1132 for (int i = 0; i < node.subspace.integers.length; i++) {
1133 boolean found = false;
1134 for (int j = 0; j < remainingIntegers_array.length; j++) {
1135 if (remainingIntegers_array[j] == node.subspace.integers[i]) {
1136 newIntegers[index2] = node.subspace.integers[i];
1137 index2++;
1138 remainingIntegers_array[j] = -1;
1139 found = true;
1140 break;
1141 }
1142 }
1143 if (found == false) {
1144 newIntegers[index1] = node.subspace.integers[i];
1145 index1++;
1146 }
1147 }
1148 node.subspace.integers = newIntegers;
1149 }
1150
1151 // ******************************************************************************************************
1152
1153 /**
1154 * Returns the maximum multiplicity of the integer in the node, and in every
1155 * relevant node
1156 */
1157 private int getMaximumMultiplicity(int integer, Node node) {
1158 // initialize by setting the maximum multiplicity to be within the node
1159 // itself
1160 int maximumMultiplicity = 0;
1161 for (int i = 0; i < node.integerPartition.sortedMultiset.length; i++)
1162 if (integer == node.integerPartition.sortedMultiset[i].element)
1163 maximumMultiplicity = node.integerPartition.sortedMultiset[i].repetition;
1164
1165 // Now, consider the relevant nodes
1166 for (int k = 0; k < node.subspace.relevantNodes.length; k++) {
1167 Node curNode = node.subspace.relevantNodes[k];
1168 for (int i = 0; i < curNode.integerPartition.sortedMultiset.length; i++)
1169 if (integer == curNode.integerPartition.sortedMultiset[i].element)
1170 if (maximumMultiplicity < curNode.integerPartition.sortedMultiset[i].repetition)
1171 maximumMultiplicity = curNode.integerPartition.sortedMultiset[i].repetition;
1172 }
1173 return (maximumMultiplicity);
1174 }
1175
1176 // ******************************************************************************************************
1177
1178 /**
1179 * Given "sumOfIntegers", this method returns a subset of "mutliset" of
1180 * which the sum equals "sumOfIntegers"
1181 */
1182 private ElementOfMultiset[] getSubsetOfIntegersGivenTheirSum(
1183 ElementOfMultiset[] multiset, int sumOfIntegers) {
1184 if (multiset == null)
1185 return (null);
1186
1187 int maxSize = Math.min(sumOfIntegers,
1188 General.getCardinalityOfMultiset(multiset));
1189
1190 ElementOfMultiset[] subset;
1191 for (int size = 1; size <= maxSize; size++) {
1192 SubsetsOfMultiset subsetsOfMultiset = new SubsetsOfMultiset(
1193 multiset, size, false);
1194 subset = subsetsOfMultiset.getNextSubset();
1195 while (subset != null) {
1196 int sum = 0;
1197 for (int i = 0; i < subset.length; i++)
1198 sum += subset[i].element * subset[i].repetition;
1199
1200 if (sum == sumOfIntegers)
1201 return (subset);
1202 else
1203 subset = subsetsOfMultiset.getNextSubset();
1204 }
1205 }
1206 return (null);
1207 }
1208
1209 // ************************************************************************************************
1210
1211 /**
1212 * Given "sumOfIntegers", this method returns a subset of "mutliset" of
1213 * which the sum equals "sumOfIntegers"
1214 */
1215 private ElementOfMultiset[] getSetOfIntegersGivenTheirRoot(
1216 int[] tempIntegers, int[] tempIntegerRoots, int root) {
1217 if (tempIntegerRoots == null)
1218 return (null);
1219
1220 // count the integer that whose root equals "root"
1221 int counter = 0;
1222 for (int i = 0; i < tempIntegerRoots.length; i++) {
1223 if (tempIntegerRoots[i] == root) {
1224 counter++;
1225 }
1226 }
1227 // keep only those integers
1228 if (counter == 0) {
1229 return (null);
1230 } else {
1231 int[] resultAsArray = new int[counter];
1232 int index = 0;
1233 for (int i = 0; i < tempIntegerRoots.length; i++) {
1234 if (tempIntegerRoots[i] == root) {
1235 resultAsArray[index] = tempIntegers[i];
1236 index++;
1237 }
1238 }
1239 return (General.convertArrayToMultiset(resultAsArray));
1240 }
1241 }
1242
1243 // ************************************************************************************************
1244
1245 /**
1246 * remove the subset of integers from the node
1247 */
1248 public static void removeSubset(Node node, ElementOfMultiset[] subset,
1249 int[][] tempIntegers, int[][] tempIntegerRoots, int e) {
1250 if (subset == null)
1251 return;
1252
1253 int[] integers = General.copyArray(tempIntegers[e]);
1254 int[] integerRoots = General.copyArray(tempIntegerRoots[e]);
1255 ElementOfMultiset[] tempSubset = General.copyMultiset(subset);
1256
1257 for (int i = 0; i < integers.length; i++) {
1258 for (int j = 0; j < tempSubset.length; j++) {
1259 if ((integers[i] == tempSubset[j].element)
1260 && (tempSubset[j].repetition > 0)) {
1261 integers[i] = -1;
1262 tempSubset[j].repetition--;
1263 break;
1264 }
1265 }
1266 }
1267 // count the elements that have not been deleted
1268 int counter = 0;
1269 for (int i = 0; i < integers.length; i++) {
1270 if (integers[i] > -1) {
1271 counter++;
1272 }
1273 }
1274 // Get rid of any elements that have been deleted
1275 if (counter == 0) {
1276 tempIntegers[e] = integers;
1277 tempIntegerRoots[e] = integerRoots;
1278 } else {
1279 tempIntegers[e] = new int[counter];
1280 if (integerRoots != null)
1281 tempIntegerRoots[e] = new int[counter];
1282 else
1283 tempIntegerRoots[e] = null;
1284 int index = 0;
1285 for (int i = 0; i < integers.length; i++)
1286 if (integers[i] > -1) {
1287 tempIntegers[e][index] = integers[i];
1288 if (integerRoots != null)
1289 tempIntegerRoots[e][index] = integerRoots[i];
1290 index++;
1291 }
1292 }
1293 }
1294
1295 // ************************************************************************************************
1296
1297 /**
1298 * Returns the total number of expansions in the search space, given the
1299 * tree-like representation of different integer-partition-based subspaces
1300 */
1301 public long computeTotalNumOfExpansions(Result result) {
1302 long totalNumOfExpansions = 0;
1303 Node[][] nodes = result.ipIntegerPartitionGraph.nodes;
1304 for (int level = 0; level < nodes.length; level++) {
1305 for (int i = 0; i < nodes[level].length; i++) {
1306 Subspace curSubspace = nodes[level][i].subspace;
1307 totalNumOfExpansions += curSubspace.totalNumOfExpansionsInSubspace;
1308 }
1309 }
1310 return totalNumOfExpansions;
1311 }
1312}
Note: See TracBrowser for help on using the repository browser.