source: ip/src/main/java/geniusweb/ip/ipSolver/Subspace.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: 66.4 KB
Line 
1package geniusweb.ip.ipSolver;
2
3import java.util.Arrays;
4import java.util.TreeSet;
5
6import geniusweb.ip.general.Combinations;
7import geniusweb.ip.general.General;
8import geniusweb.ip.general.RandomPermutation;
9import geniusweb.ip.general.RandomSubsetOfGivenSet;
10import geniusweb.ip.inputOutput.Input;
11import geniusweb.ip.inputOutput.Output;
12import geniusweb.ip.inputOutput.SolverNames;
13import geniusweb.ip.mainSolver.Result;
14
15public class Subspace {
16 public long sizeOfSubspace;
17 public long totalNumOfExpansionsInSubspace;
18 public int[] integers;
19 public int[] integersSortedAscendingly;
20 public double UB, Avg, LB;
21 public boolean enabled;
22 public double priority;
23 public long timeToSearchThisSubspace;
24 public long numOfSearchedCoalitionsInThisSubspace;
25 public double numOfSearchedCoalitionsInThisSubspace_confidenceInterval;
26 public Node[] relevantNodes;
27 public boolean isReachableFromBottomNode;
28
29 // ******************************************************************************************************
30
31 /**
32 * the constructors
33 */
34 public Subspace(int[] integers) {
35 this.integers = integers;
36 this.integersSortedAscendingly = General.sortArray(integers, true);
37 this.sizeOfSubspace = computeNumOfCSInSubspace(this.integers);
38 }
39
40 // ******************************************************************************************************
41
42 public Subspace(int[] integers, double[] avgValueForEachSize,
43 double[][] maxValueForEachSize, Input input) {
44 this.integers = integers; // this.integers = orderParts( integers,
45 // avgValueForEachSize, maxValueForEachSize,
46 // input );
47 this.integersSortedAscendingly = General.sortArray(integers, true);
48 this.timeToSearchThisSubspace = 0;
49 this.enabled = true;
50
51 // compute the number of coalition structures in this subspace
52 this.sizeOfSubspace = computeNumOfCSInSubspace(this.integers);
53
54 // compute the total number of expansions in this subspace. This number
55 // depends on the sorting of the integers
56 this.totalNumOfExpansionsInSubspace = computeTotalNumOfExpansionsInSubspace(
57 this.integers, input);
58
59 // initialize the number of searched coalitions (for the subspaces of
60 // which the integer partition is of size: 1, 2, or "n"
61 if (this.integers.length == 2) {
62 int size1 = this.integers[0];
63 int size2 = this.integers[1];
64 int numOfCombinationsOfSize1 = (int) Combinations
65 .binomialCoefficient(input.numOfAgents, size1);
66 int temp;
67 if (size1 != size2)
68 temp = numOfCombinationsOfSize1;
69 else
70 temp = (numOfCombinationsOfSize1 / 2);
71
72 this.numOfSearchedCoalitionsInThisSubspace = 2 * temp;
73 ;
74 } else if ((this.integers.length == 1)
75 || (this.integers.length == input.numOfAgents))
76 this.numOfSearchedCoalitionsInThisSubspace = this.integers.length;
77 else
78 this.numOfSearchedCoalitionsInThisSubspace = 0;
79
80 // Calculating UB:
81 int j = 0;
82 this.UB = 0;
83 for (int k = 0; k <= this.integers.length - 1; k++) {
84 if ((k > 0) && (this.integers[k] == this.integers[k - 1]))
85 j++;
86 else
87 j = 0;
88 this.UB += maxValueForEachSize[this.integers[k] - 1][j];
89 }
90
91 // Calculating Avg:
92 this.Avg = 0;
93 for (int k = 0; k <= this.integers.length - 1; k++)
94 this.Avg += avgValueForEachSize[this.integers[k] - 1];
95
96 // Calculating LB:
97 this.LB = this.Avg;
98 }
99
100 // ******************************************************************************************************
101
102 /**
103 * Search this subspace using the IP algorithm Returns the number of
104 * subspaces that were searched
105 */
106 public int search(Input input, Output output, Result result,
107 double acceptableValue, double[] avgValueForEachSize,
108 double[] sumOfMax, int numOfIntegersToSplit) {
109 long timeBeforeSearchingThisSubspace = System.currentTimeMillis();
110
111 if (input.solverName == SolverNames.ODPIP) {
112 if (result.get_dpMaxSizeThatWasComputedSoFar() >= ((int) Math
113 .floor(2 * input.numOfAgents / (double) 3))) {
114 this.enabled = false;
115 return (1);
116 }
117 }
118 if (input.printTheSubspaceThatIsCurrentlyBeingSearched)
119 System.out.println(input.problemID + " - Searching "
120 + General.convertArrayToString(integersSortedAscendingly)
121 + " --> " + General.convertArrayToString(integers));
122
123 if (input.useSamplingWhenSearchingSubspaces) {
124 if (input.samplingDoneInGreedyFashion)
125 searchUsingSamplingInGreedyFashion(input, output, result,
126 acceptableValue);
127 else
128 searchUsingSampling(input, output, result);
129 // System.out.println("I am sampling from the subspace:
130 // "+General.convertArrayToString(integers));
131 } else
132 search_useBranchAndBound(input, output, result, acceptableValue,
133 sumOfMax, numOfIntegersToSplit);
134
135 // If we are running IDP-IP, then we need to split the resulting CS in
136 // the optimal way
137 if (input.solverName == SolverNames.ODPIP) {
138 int[][] CS = result.idpSolver_whenRunning_ODPIP.dpSolver
139 .getOptimalSplit(result.get_ipBestCSFound());
140 result.updateIPSolution(CS, input.getCoalitionStructureValue(CS));
141 }
142 timeToSearchThisSubspace = System.currentTimeMillis()
143 - timeBeforeSearchingThisSubspace;
144 output.printTimeRequiredForEachSubspace(this, input);
145 this.enabled = false;
146 int numOfSearchedSubspaces = 1;
147 // disable every relevant subspace
148 if ((input.solverName == SolverNames.ODPIP)
149 && (relevantNodes != null)) {
150 for (int i = 0; i < relevantNodes.length; i++)
151 if (relevantNodes[i].subspace.enabled) {
152 relevantNodes[i].subspace.enabled = false;
153 numOfSearchedSubspaces++;
154 if (input.printTheSubspaceThatIsCurrentlyBeingSearched)
155 System.out.println(input.problemID
156 + " - ****** with DP's help, IP avoided the subspace: "
157 + Arrays.toString(
158 relevantNodes[i].integerPartition.partsSortedAscendingly));
159 }
160 }
161 return (numOfSearchedSubspaces);
162 }
163
164 // ******************************************************************************************************
165
166 private void searchUsingSampling(Input input, Output output,
167 Result result) {
168 // Checking the special case where the size of the coalition structure
169 // is either "1" or "numOfAgents"
170 if ((integers.length == 1) || (integers.length == input.numOfAgents)) {
171 searchFirstOrLastLevel(integers, input, output, result);
172 return;
173 }
174 // Initialization
175 int numOfSamples = Math.min(100000,
176 (int) Math.round(sizeOfSubspace * 0.1));
177 RandomPermutation randomPermutation = new RandomPermutation(
178 input.numOfAgents);
179
180 // for every sample
181 for (int i = 0; i < numOfSamples; i++) {
182 int[] permutation = randomPermutation.get();
183 double coalitionStructureValue = 0;
184 int[] coalitionStructure = new int[integers.length];
185 int indexInPermutation = 0;
186 // for every size in the integer partition
187 for (int j = integers.length - 1; j >= 0; j--) {
188 int size = integers[j];
189 int currentCoalition = 0;
190 // Compute the current coalition
191 for (int k = 0; k < size; k++) {
192 currentCoalition += (1 << (permutation[indexInPermutation])); // add
193 // agent
194 // "permutation[
195 // indexInPermutation
196 // ]"
197 // to
198 // "currentCoalition"
199 indexInPermutation++;
200 }
201 coalitionStructure[j] = currentCoalition;
202
203 // update the value of the current coalition structure
204 coalitionStructureValue += input
205 .getCoalitionValue(currentCoalition);
206 // coalitionStructureValue +=
207 // localBranchAndBoundObject.getLowerBoundForCurrentAgents(
208 // currentCoalition );
209 }
210 // If this value is greater than the best value found so far
211 if (result.get_ipValueOfBestCSFound() < coalitionStructureValue) {
212 int[][] CSInByteFormat = Combinations
213 .convertSetOfCombinationsFromBitToByteFormat(
214 coalitionStructure, input.numOfAgents,
215 integers);
216 result.updateIPSolution(CSInByteFormat,
217 coalitionStructureValue);
218 }
219 }
220 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
221 input, result);
222 }
223
224 // ******************************************************************************************************
225
226 private void searchUsingSamplingInGreedyFashion(Input input, Output output,
227 Result result, double acceptableValue) {
228 // Checking the special case where the size of the coalition structure
229 // is either "1" or "numOfAgents"
230 if ((integers.length == 1) || (integers.length == input.numOfAgents)) {
231 searchFirstOrLastLevel(integers, input, output, result);
232 return;
233 }
234 // e.g., numOfRemainingAgents[i] is the number of agents that did not
235 // appear in coalitions: CS[0],...,CS[i-1]
236 int[] numOfRemainingAgents = new int[integers.length];
237 numOfRemainingAgents[0] = input.numOfAgents;
238 for (int j = 1; j < integers.length; j++)
239 numOfRemainingAgents[j] = numOfRemainingAgents[j - 1]
240 - integers[j - 1];
241
242 // Compute the number of possible coalitions, given the size, and the
243 // number of remaining agents
244 long[] numOfPossibleCoalitions = new long[integers.length];
245 for (int j = 0; j < integers.length; j++)
246 numOfPossibleCoalitions[j] = Combinations
247 .binomialCoefficient(numOfRemainingAgents[j], integers[j]);
248
249 // While constructing a coalition structure (CS), the algorithm will
250 // take a
251 // number of samples of every coalition size, and select the best one
252 // seen.
253 int[] numOfCoalitionSamplesPerSizePerCS = new int[integers.length];
254 for (int j = 0; j < integers.length; j++)
255 numOfCoalitionSamplesPerSizePerCS[j] = Math.min(100000,
256 (int) Math.ceil(numOfPossibleCoalitions[j] * 0.1));
257
258 // The number of coalition structures (CS) that the algorithm will
259 // construct
260 int numOfCoalitionStructureSamples = Math.min(10000,
261 (int) Math.ceil(sizeOfSubspace * 0.1));
262
263 // This is the coalition structure that will be constructed by the
264 // algorithm
265 int[] CS = new int[integers.length];
266
267 // For every CS that the algorithm will construct
268 for (int i = 0; i < numOfCoalitionStructureSamples; i++) {
269 // initialize the set of remaining agents to be the grand coalition
270 int setOfRemainingAgentsInBitFormat = (1 << input.numOfAgents) - 1;
271 int[] setOfRemainingAgentsInByteFormat = Combinations
272 .convertCombinationFromBitToByteFormat(
273 setOfRemainingAgentsInBitFormat, input.numOfAgents);
274
275 for (int j = 0; j < integers.length - 1; j++) // For every size
276 {
277 RandomSubsetOfGivenSet samplingObject = new RandomSubsetOfGivenSet(
278 setOfRemainingAgentsInByteFormat,
279 numOfRemainingAgents[j], integers[j]);
280 double bestValueOfCurrentSize = Double.MIN_VALUE;
281 // For every sample of the current size
282 for (int k = 0; k < numOfCoalitionSamplesPerSizePerCS[j]; k++) {
283 int C = samplingObject.getSubsetInBitFormat();
284 // Update the best coalition seen of the current size
285 double currentCoalitionValue = input.getCoalitionValue(C);
286 if (bestValueOfCurrentSize < currentCoalitionValue) {
287 bestValueOfCurrentSize = currentCoalitionValue;
288 CS[j] = C;
289 }
290 }
291 // the set of agents not in coalitions: CS[0],...,CS[i-1]
292 setOfRemainingAgentsInBitFormat -= CS[j];
293 setOfRemainingAgentsInByteFormat = Combinations
294 .convertCombinationFromBitToByteFormat(
295 setOfRemainingAgentsInBitFormat,
296 input.numOfAgents, numOfRemainingAgents[j]);
297 }
298 // Add the last coalition in CS
299 CS[integers.length - 1] = setOfRemainingAgentsInBitFormat;
300
301 // Update the currest best CS found
302 if (result.get_ipValueOfBestCSFound() < input
303 .getCoalitionStructureValue(CS)) {
304 int[][] CSInByteFormat = Combinations
305 .convertSetOfCombinationsFromBitToByteFormat(CS,
306 input.numOfAgents, integers);
307 result.updateIPSolution(CSInByteFormat,
308 input.getCoalitionStructureValue(CS));
309 if (result.get_ipValueOfBestCSFound() >= acceptableValue) { // If
310 // the
311 // value
312 // is
313 // within
314 // the
315 // acceptable
316 // ratio
317 // {
318 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
319 input, result);
320 return;
321 }
322 }
323 }
324 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
325 input, result);
326 }
327
328 // ******************************************************************************************************
329
330 /**
331 * Order the parts of the integer partition. Here, I did it such that the
332 * first part is the one that has the maximum difference between its upper
333 * bound and its average. This ended up exactly as the descending order.
334 */
335 public int[] orderParts(int[] integers, double[] avgValueForEachSize,
336 double[][] maxValueForEachSize, Input input) {
337 // Get (1) the underlying set of the integer partition, and (2) the
338 // multiplicity of each part.
339 int[] underlyingSet = General.getUnderlyingSet(integers);
340 int[] multiplicity = new int[input.numOfAgents];
341 for (int i = 0; i < input.numOfAgents; i++)
342 multiplicity[i] = 0;
343 for (int i = 0; i < integers.length; i++)
344 multiplicity[integers[i] - 1]++;
345
346 // Initialize the new ordering of the underlying set
347 int[] newUnderlyingSet = new int[underlyingSet.length];
348 for (int i = 0; i < newUnderlyingSet.length; i++) {
349 newUnderlyingSet[i] = 0;
350 }
351 // Compute the new ordering of the underlying set
352 for (int i = 0; i < newUnderlyingSet.length; i++) {
353 double biggestDifference = -1;
354 int sizeWithMaxDifference = -1;
355 for (int j = 0; j < underlyingSet.length; j++) {
356 int curSize = underlyingSet[j];
357
358 // if we already put this size in the list "newOrderingOfSizes",
359 // then continue skip
360 boolean sizeAlreadyAddedToList = false;
361 for (int k = 0; k < i; k++)
362 if (newUnderlyingSet[k] == curSize) {
363 sizeAlreadyAddedToList = true;
364 break;
365 }
366 if (sizeAlreadyAddedToList)
367 continue;
368
369 // Check if the current size has the biggest difference between
370 // Max and Avg
371 if (biggestDifference < (maxValueForEachSize[curSize - 1][0]
372 - avgValueForEachSize[curSize - 1])) {
373 biggestDifference = (maxValueForEachSize[curSize - 1][0]
374 - avgValueForEachSize[curSize - 1]);
375 sizeWithMaxDifference = curSize;
376 }
377 }
378 newUnderlyingSet[i] = sizeWithMaxDifference;
379 }
380 // constructing the new Integer partition
381 int[] newIntegers = new int[integers.length];
382 int index = 0;
383 for (int i = 0; i < newUnderlyingSet.length; i++) {
384 int curSize = newUnderlyingSet[i];
385 for (int j = 0; j < multiplicity[curSize - 1]; j++) {
386 newIntegers[index] = curSize;
387 index++;
388 }
389 }
390 return (newIntegers);
391 }
392
393 // ******************************************************************************************************
394
395 /**
396 * Computes the size of the subspace (i.e., the number of coalition
397 * structures in it). I HIGHLY RECOMMEND reading the comments that are at
398 * the beginning of the method: "search_usingBranchAndBound".
399 */
400 public long computeNumOfCSInSubspace(int[] integers) {
401 // Calculate the number of agents from the given integers...
402 int numOfAgents = 0;
403 for (int i = 0; i < integers.length; i++)
404 numOfAgents += integers[i];
405
406 // Check the special case where the size of the integer partition equals
407 // 1 or "numOfAgents"
408 if ((integers.length == 1) || (integers.length == numOfAgents))
409 return (1);
410
411 // Initialization
412 int[] length_of_A = init_length_of_A(numOfAgents, integers);
413 int[] max_first_member_of_M = init_max_first_member_of_M(integers,
414 length_of_A, false);
415 long[][] numOfCombinations = init_numOfCombinations(integers,
416 length_of_A, max_first_member_of_M);
417 long[] sumOf_numOfCombinations = init_sumOf_numOfCombinations(
418 numOfCombinations, integers, length_of_A,
419 max_first_member_of_M);
420 long[] numOfRemovedCombinations = init_numOfRemovedCombinations(
421 integers, length_of_A, max_first_member_of_M);
422 long[][] increment = init_increment(integers, numOfCombinations,
423 sumOf_numOfCombinations, max_first_member_of_M, false);
424
425 // Calculating size of the subspace, i.e., the total number of coalition
426 // structures in it:
427 long sizeOfSubspace = 0;
428 if (numOfRemovedCombinations[0] == 0) { // then the list has a single
429 // increment value
430 sizeOfSubspace = increment[0][0] * sumOf_numOfCombinations[0];
431 } else { // then the list has different increment values
432 for (int i = 0; i <= max_first_member_of_M[0] - 1; i++)
433 sizeOfSubspace += increment[0][i] * numOfCombinations[0][i];
434 }
435 return (sizeOfSubspace);
436
437 // An alternative way for computing the number of CS in a subspace (by
438 // using the equation). However, for
439 // large numbers of agents, the factorial method might overflow.
440 // Therefore, we do not use the equation.
441 /*
442 * int[] underlyingSet = General.getUnderlyingSet(integers);
443 *
444 * long num1 = Combinations.binomialCoefficient( numOfAgents ,
445 * integers[0] ); int x=numOfAgents; for(int j=1; j<=integers.length-2;
446 * j++) { x=(int)(x-integers[j-1]); num1 = num1 *
447 * Combinations.binomialCoefficient( x, integers[j] ); } long num2=1;
448 * for(int j=0; j<=underlyingSet.length-1; j++) num2 = num2 *
449 * General.factorial( General.multiplicity(underlyingSet[j],integers) );
450 *
451 * return( (long)num1/num2 );
452 */ }
453
454 // ******************************************************************************************************
455
456 /**
457 * Computes the total number of expansions in each search space. Observe
458 * that this differs according to whether the integer partition is ordered
459 * ascendingly or descendingly. This method is thoroughly tested, and is
460 * guaranteed to work.
461 */
462 public static long computeTotalNumOfExpansionsInSubspace(int[] integers,
463 Input input) {
464 // Compute the number of agents
465 int numOfAgents = 0;
466 for (int i = 0; i < integers.length; i++)
467 numOfAgents += integers[i];
468
469 // Sort the parts in the integer partition
470 int[] sortedIntegers = General.sortArray(integers,
471 input.orderIntegerPartitionsAscendingly);
472
473 int[] alpha = new int[sortedIntegers.length];
474 long[][] gamma = new long[sortedIntegers.length][];
475 for (int j = 0; j < sortedIntegers.length; j++) {
476 // compute the maximum index (in the integer partition) at which the
477 // current integer appears
478 int maxIndex = 0;
479 for (int k = 0; k < sortedIntegers.length; k++)
480 if (sortedIntegers[k] == sortedIntegers[j])
481 maxIndex = k;
482
483 // compute alpha for the current integer
484 alpha[j] = numOfAgents + 1;
485 for (int k = 0; k <= maxIndex; k++)
486 alpha[j] -= sortedIntegers[k];
487
488 // compute gamma for the current integer
489 gamma[j] = new long[alpha[j]];
490 for (int beta = 0; beta < alpha[j]; beta++) {
491 int sumOfPreviousIntegers = 0;
492 for (int k = 0; k < j; k++)
493 sumOfPreviousIntegers += sortedIntegers[k];
494
495 if (j == 0)
496 gamma[j][beta] = Combinations.binomialCoefficient(
497 numOfAgents - sumOfPreviousIntegers - (beta + 1),
498 sortedIntegers[j] - 1);
499 else {
500 int lambda;
501 if (sortedIntegers[j] == sortedIntegers[j - 1])
502 lambda = beta;
503 else
504 lambda = alpha[j - 1] - 1;
505
506 long sum = 0;
507 for (int k = 0; k <= lambda; k++)
508 sum += gamma[j - 1][k];
509 gamma[j][beta] = sum * Combinations.binomialCoefficient(
510 numOfAgents - sumOfPreviousIntegers - (beta + 1),
511 sortedIntegers[j] - 1);
512 }
513 }
514 }
515 long numOfExpansionsInSubspace = 0;
516 for (int j = 0; j < sortedIntegers.length; j++)
517 for (int beta = 0; beta < alpha[j]; beta++)
518 numOfExpansionsInSubspace += gamma[j][beta];
519
520 return (numOfExpansionsInSubspace);
521 }
522
523 // ******************************************************************************************************
524
525 /**
526 * //Description of the main variables used (it is HIGHLY RECOMMENDED to
527 * read these comments before reading the method). //For more detail, see
528 * Section 4.3, and figure 3 in the paper: "Near-optimal anytime coalition
529 * structure generation"
530 * /*_______________________________________________________________________________________________________________________________
531 * | length_of_A[i]: | A coalition structure consists of a number of
532 * coalitions (e.g. c[1],c[2],...). | length_of_A[i] represents THE NUMBER
533 * of agents from which we can select members of c[i] | | (In figure 3,
534 * "length_of_A" contains the values: 7,5,3)
535 * |___________________________________________________________________________________________________
536 * | A[i]: | A coalition structure consists of a number of coalitions (e.g.
537 * c[1],c[2],...). | A[i] represents THE SET of agents from which we can
538 * select members of c[i]. | Note: | Every time you update c[i], you would
539 * have to update A[j]:j>i | | (In figure 3, "A" contains the values:
540 * {1,2,3,4,5,6,7}, {2,3,4,5,7}, {2,3,7} )
541 * |___________________________________________________________________________________________________
542 * | M[i]: | (In figure 3, "M" contains the values: {1,6},{3,4},{1,2,3})
543 * |___________________________________________________________________________________________________
544 * | max_first_member_of_M[i] | Represents the maximum value that the first
545 * member of "M[i]" can take. | | (In figure 3, "max_first_member_of_M"
546 * contains the values: 4,4,1)
547 * |___________________________________________________________________________________________________
548 * | index_of_M[i] | The index of "M" in the list of potential combinations
549 * for "M" | | (In figure 3, "index_of_M" contains the values: 17,3,1)
550 * |___________________________________________________________________________________________________
551 * | numOfCombinations: | Represents the number of possible combinations for
552 * M[s] | | Note(1) | If( integers[s] != integers[s+1] ), then
553 * numOfCombinations[s] would actually | be the number of possible
554 * combinations of size integers[s] out of the set A[s]. | Note(2) | If(
555 * integers[s] == integers[s+1] ), then the set of possible coalitions would
556 * | be A SUBSET of the possible combinations of size integers[s] out of the
557 * set A[s]. | | In more detail, it would be those coalitions containing 1,
558 * and those not containing | 1 but containing 2, and those not containing
559 * 1,2 but containing 3, and so on, until | those not containing:
560 * 1,...,(length_of_A[s+1]-integers[s+1]+1)-1, but containing: |
561 * (length_of_A[s+1]-integers[s+1]+1). | | numOfCombinations[s][0] contains
562 * the number of coalitions containing 1. | numOfCombinations[s][1] contains
563 * the number of coalitions not containing 1, but containing 2 |
564 * numOfCombinations[s][2] contains the number of coalitions not containing
565 * 1,2, but containing 3 | and so on... | | (In figure 3,
566 * "numOfCombinations[0]" contains the values: 6,5,4,3 |
567 * "numOfCombinations[1]" contains the values: 4,3,2,1 |
568 * "numOfCombinations[2]" contains the value : 1 )
569 * |___________________________________________________________________________________________________
570 * | sumOf_numOfCombinations[i]| Contains the sum of:
571 * numOfCombinations[i][j] : j = 0,1,2,... | | (In figure 3,
572 * "sumOf_numOfCombinations" contains the values: 18,10,1)
573 * |___________________________________________________________________________________________________
574 * | numOfRemovedCombinations: | As mentioned above: | if( integers[s] !=
575 * integers[s+1] ) then the set of possible combinations for M[s] | would be
576 * the set of possible combinations of size integers[s] out of the set A[s].
577 * In | this case, "numOfRemovedCombinations" would be 0. | | if(
578 * integers[s] == integers[s+1] ) then the set of possible combinaitons for
579 * M[s] | would only be a subset of that set. In this case
580 * "numOfRemovedCombinations" would be the size of | the set minus the size
581 * of the subset. | | (In figure 3, "numOfRemovedCombinations" contains the
582 * values: 3,0,0)
583 * |___________________________________________________________________________________________________
584 * | indexToStartAt[i] | The index at which M[i] starts. It equals:
585 * sumOf_numOfCombinations[i] + numOfRemovedCombinations[i] | | (In figure
586 * 3, "indexToStartAt" contains the values: 21, 10, 1)
587 * |___________________________________________________________________________________________________
588 * | indexToStopAt[i] | The index at which M[i] stops. It equals:
589 * numOfRemovedCombinations[i] + 1 | | (In figure 3, "indexToStopAt"
590 * contains the values: 4, 1, 1)
591 * |___________________________________________________________________________________________________
592 * | CS: | CS[i][j] = A[ M[i][j] ]. In other words, "CS" represents the
593 * actual coalition, | while "M" only represents indices that point to the
594 * actual agents | | (In figure 3, "CS" contains the values:
595 * {1,6},{4,5},{2,3,7})
596 * |___________________________________________________________________________________________________
597 * | increment[s]: | Every time we move up one step in the list of
598 * combinations for M[s], we would have finished | scanning a particular
599 * number of coalition structures. This number is "increment[s]" | | Note
600 * that if( integers[s] == integers[s+1] ), then this number would not be
601 * equal | for every combination in the list. | | (In figure 3, increment[0]
602 * contains the values: 10,6,3,1 | increment[1] contains the value : 1 |
603 * increment[2] contains the value : 1)
604 * |___________________________________________________________________________________________________
605 * | sumOf_values | Every time we calculate the value of a coalition
606 * structure, we sum the values of its constituent | coalitions. | | Now,
607 * due to the way we scan the possible CS, every time we move M[s] one step,
608 * | (M[i] : i>s) must be updated, while (M[j] : j<s) remain unchanged. This
609 * implies that: (CS[i] : i>s) | must be updated, while (CS[j] : j<s)
610 * remains unchanged. Therefore, if we knew the summation of the | values of
611 * coalitions (CS[j] : j<s), then we would only need to add to it the value
612 * of coalition | CS[s], plus the values of coalitions (CS[i] : i>s). | |
613 * sumOf_values[1] = the value of the first coalition (i.e. v(CS[0])) |
614 * sumOf_values[2] = the sum of the values of the first 2 coalitions (i.e.
615 * v(CS[0]) + v(CS[1])) | and so on... | | IMPORTANT NOTE: | sumOf_values
616 * actually contains: "numOfAgents+1" values, where sumOf_values[0] is
617 * always equal | to 0. This way, the value at location i would be:
618 * sumOf_values[i], and not: sumOf_values[i-1], | which makes accessing the
619 * value slightly faster. Moreover, we can now say: | sumOf_values[i] =
620 * sumOf_values[i-1] + getCoalitionValue(...), even if i=1, because we know
621 * that | sumOf_values[0] will always be equal to zero.
622 * |___________________________________________________________________________________________________
623 * | sumOf_agents | sumOf_agents[s] = the agents that belong to coalitions
624 * (CS[j] : j<=s), represented as a bit string
625 * |__________________________________________________________________________________________________
626 * | sumOf_parts | sumOf_parts[s] = the sum of the following parts in the
627 * integer partition: 0, 1, ..., s | | (In figure 3, "sumOf_parts" contains
628 * the values: 2, 4, 7
629 * ___________________________|__________________________________________________________________________________________________
630 */
631
632 private void search_useBranchAndBound(Input input, Output output,
633 Result result, double acceptableValue, double[] sumOfMax,
634 int numOfIntegersToSplit) {
635 // Checking the special case where the size of the coalition structure
636 // is either "1" or "numOfAgents"
637 if ((integers.length == 1) || (integers.length == input.numOfAgents)) {
638 searchFirstOrLastLevel(integers, input, output, result);
639 return;
640 }
641 // Initialization
642 final int numOfIntegers = integers.length;
643 final long ipNumOfSearchedCoalitions_beforeSearchingThisSubspace = result.ipNumOfExpansions;
644 final int numOfAgents = input.numOfAgents;
645 final int numOfIntsToSplit = numOfIntegersToSplit;
646 final boolean ipUsesBranchAndBound = input.useBranchAndBound;
647 final boolean constraintsExist;
648 boolean this_CS_is_useless;
649 double valueOfCS = 0;
650 if (input.feasibleCoalitions == null)
651 constraintsExist = false;
652 else
653 constraintsExist = true;
654 final boolean ODPIsHelpingIP;
655 if (input.solverName == SolverNames.ODPIP)
656 ODPIsHelpingIP = true;
657 else
658 ODPIsHelpingIP = false;
659
660 // Initialization (in the right order)
661 final int[] bit = init_bit(numOfAgents);
662 final int[] length_of_A = init_length_of_A(numOfAgents, integers);
663 final int[] max_first_member_of_M = init_max_first_member_of_M(integers,
664 length_of_A, ODPIsHelpingIP);
665 final long[][] numOfCombinations = init_numOfCombinations(integers,
666 length_of_A, max_first_member_of_M);
667 final long[] sumOf_numOfCombinations = init_sumOf_numOfCombinations(
668 numOfCombinations, integers, length_of_A,
669 max_first_member_of_M);
670 final long[] numOfRemovedCombinations = init_numOfRemovedCombinations(
671 integers, length_of_A, max_first_member_of_M);
672 final long[][] increment = init_increment(integers, numOfCombinations,
673 sumOf_numOfCombinations, max_first_member_of_M, ODPIsHelpingIP);
674 final long[] indexToStartAt = init_indexToStartAt(numOfIntegers,
675 numOfRemovedCombinations, sumOf_numOfCombinations);
676 final long[] indexToStopAt = init_indexToStopAt(numOfIntegers,
677 numOfRemovedCombinations);
678 long[] index_of_M = init_index_of_M(1, integers, increment,
679 max_first_member_of_M, numOfCombinations,
680 numOfRemovedCombinations, sumOf_numOfCombinations);
681 int[][] M = init_M(index_of_M, integers, length_of_A, numOfAgents);
682 int[][] A = init_A(numOfAgents, integers, M, length_of_A);
683 int[] CS = init_CS_hashTableVersion(M, A, length_of_A, bit,
684 numOfIntegers);
685 int[] sumOf_agents = init_sumOf_agents_hashTableVersion(numOfIntegers,
686 CS);
687 double[] sumOf_values = init_sumOf_values_hashTableVersion(
688 numOfIntegers, CS, input);
689 result.ipNumOfExpansions += integers.length - 2;
690 IDPSolver_whenRunning_ODPIP localBranchAndBoundObject = result.idpSolver_whenRunning_ODPIP;
691
692 main_loop: while (true) {
693 // In the following loop, we fix the coalitions
694 // 1,2,...,numOfIntegers-3, and try all
695 // the possibilities for the last two coalitions in the integer
696 // partition.
697 do {
698 setTheLastTwoCoalitionsInCS(CS, M[numOfIntegers - 2], A,
699 numOfIntegers, bit);
700
701 // If there are constraints, then check them on the last two
702 // coalitions
703 this_CS_is_useless = false;
704 if ((constraintsExist)
705 && (checkIfLastTwoCoalitionsSatisfyConstraints(CS,
706 input.feasibleCoalitions) == false))
707 this_CS_is_useless = true;
708
709 // If the current coalition structure satisfies the constraints,
710 // then...
711 if (this_CS_is_useless == false) {
712 // Calculate the value of the current coalition structure
713 switch (numOfIntsToSplit) {
714 case 0:
715 valueOfCS = sumOf_values[numOfIntegers - 2]
716 + input.getCoalitionValue(CS[numOfIntegers - 2])
717 + input.getCoalitionValue(
718 CS[numOfIntegers - 1]);
719 break;
720 case 1:
721 valueOfCS = sumOf_values[numOfIntegers - 2]
722 + input.getCoalitionValue(CS[numOfIntegers - 2])
723 + localBranchAndBoundObject
724 .getValueOfBestPartitionFound(
725 CS[numOfIntegers - 1]);
726 break;
727 default:
728 valueOfCS = sumOf_values[numOfIntegers - 2]
729 + localBranchAndBoundObject
730 .getValueOfBestPartitionFound(
731 CS[numOfIntegers - 2])
732 + localBranchAndBoundObject
733 .getValueOfBestPartitionFound(
734 CS[numOfIntegers - 1]);
735 }
736 // If this value is greater than the best value found so far
737 if (result.get_ipValueOfBestCSFound() < valueOfCS) {
738 int[][] CSInByteFormat = Combinations
739 .convertSetOfCombinationsFromBitToByteFormat(CS,
740 numOfAgents, integers);
741 result.updateIPSolution(CSInByteFormat, valueOfCS);
742
743 if (result
744 .get_ipValueOfBestCSFound() >= acceptableValue) // If
745 // the
746 // value
747 // is
748 // within
749 // the
750 // acceptable
751 // ratio
752 {
753 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
754 input, result);
755 numOfSearchedCoalitionsInThisSubspace = result.ipNumOfExpansions
756 - ipNumOfSearchedCoalitions_beforeSearchingThisSubspace;
757 return;
758 }
759 }
760 }
761 index_of_M[numOfIntegers - 2]--;
762 Combinations.getPreviousCombination(
763 length_of_A[numOfIntegers - 2],
764 integers[numOfIntegers - 2], M[numOfIntegers - 2]);
765 } while (index_of_M[numOfIntegers
766 - 2] >= indexToStopAt[numOfIntegers - 2]);
767
768 /*
769 * In the following loop, we keep changing the coalitions
770 * 1,2,...,numOfIntegers-3 until we find a combinations of them that
771 * is potentially useful (i.e., until the sum of their values, plus
772 * the maximum possible value of the remaining coalitions, is
773 * greater than the best value found so far)
774 */
775 int s1 = numOfIntegers - 3;
776 sub_loop: while (s1 >= 0) {
777 if (index_of_M[s1] > indexToStopAt[s1]) // If you have NOT
778 // finished scannig this
779 // column:
780 {
781 if (s1 == 0) {
782 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
783 input, result);
784 if (ODPIsHelpingIP) {
785 if (result
786 .get_dpMaxSizeThatWasComputedSoFar() >= ((int) Math
787 .floor(2 * input.numOfAgents
788 / (double) 3))) {
789 numOfSearchedCoalitionsInThisSubspace = result.ipNumOfExpansions
790 - ipNumOfSearchedCoalitions_beforeSearchingThisSubspace;
791 return;
792 }
793 }
794 }
795 for (int s2 = s1; s2 <= numOfIntegers - 3; s2++) {
796 boolean firstTime = true;
797 do {
798 result.ipNumOfExpansions++; // update the number of
799 // searched coalitions
800
801 if ((firstTime) && (s2 > s1)) {
802 // Set the index of M to be the last index in
803 // the column
804 set_M_and_index_of_M(M, index_of_M, length_of_A,
805 indexToStartAt, s2);
806 firstTime = false;
807 } else {
808 // move M one step upwards, and update the index
809 // of M
810 Combinations.getPreviousCombination(
811 length_of_A[s2], integers[s2], M[s2]);
812 index_of_M[s2]--;
813 }
814 // Set CS, given the new M
815 int temp3 = 0;
816 for (int j1 = integers[s2] - 1; j1 >= 0; j1--)
817 temp3 |= bit[A[s2][M[s2][j1] - 1]];
818 CS[s2] = temp3;
819
820 // If there exists constraints that we need to deal
821 // with, then check them
822 this_CS_is_useless = false;
823 if (constraintsExist) {
824 if (input.feasibleCoalitions
825 .contains(new Integer(CS[s2])) == false)
826 this_CS_is_useless = true;
827 }
828 // If all the possible values that can be found by
829 // fixing this coalition (along
830 // with the ones before it) can never be greater
831 // than the value we found so far, then...
832 if ((ipUsesBranchAndBound)
833 && (this_CS_is_useless == false)) {
834 // Recalculate sumOf_values[s2+1] and
835 // sumOf_agents[s2+1], given the new CS
836 int newCoalition = CS[s2];
837 double valueOfNewCoalition;
838 if (s2 >= numOfIntegers - numOfIntsToSplit) {
839 valueOfNewCoalition = localBranchAndBoundObject
840 .getValueOfBestPartitionFound(
841 CS[s2]);
842 } else {
843 valueOfNewCoalition = input
844 .getCoalitionValue(CS[s2]);
845 }
846 sumOf_values[s2 + 1] = sumOf_values[s2]
847 + valueOfNewCoalition;
848 sumOf_agents[s2 + 1] = sumOf_agents[s2]
849 + CS[s2];
850
851 // Use branch and bound to see if the current
852 // coalitions have potential
853 double upperBoundForRemainingAgents = sumOfMax[s2
854 + 2];
855 // if( (
856 // (sumOf_values[s2+1]+upperBoundForRemainingAgents)
857 // <= result.get_ipValueOfBestCSFound() )
858 if (((sumOf_values[s2 + 1]
859 + upperBoundForRemainingAgents)
860 - result.get_ipValueOfBestCSFound() < -0.00000000005)
861 || ((ODPIsHelpingIP)
862 && (useLocalBranchAndBound(
863 input,
864 localBranchAndBoundObject,
865 sumOf_values,
866 sumOf_agents, s2,
867 newCoalition,
868 valueOfNewCoalition))))
869 this_CS_is_useless = true;
870 }
871 // If the current combination of coalitions has been
872 // found useless...
873 if (this_CS_is_useless == false)
874 break;
875 } while (index_of_M[s2] > indexToStopAt[s2]);
876
877 if (this_CS_is_useless) { // If we kept moving upwards,
878 // until we reached the top:
879 s1 = s2 - 1;
880 continue sub_loop;
881 }
882 update_A(A[s2 + 1], A[s2], length_of_A[s2], M[s2],
883 integers[s2]);
884 }
885 // Set M, given its new index
886 int s2 = numOfIntegers - 2;
887 set_M_and_index_of_M(M, index_of_M, length_of_A,
888 indexToStartAt, s2);
889
890 continue main_loop;
891 }
892 s1--;
893 }
894 break main_loop;
895 }
896 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
897 input, result);
898 numOfSearchedCoalitionsInThisSubspace = result.ipNumOfExpansions
899 - ipNumOfSearchedCoalitions_beforeSearchingThisSubspace;
900 }
901
902 // ******************************************************************************************************
903
904 /**
905 * This method is called for both the integer partition of size 1, and that
906 * of size numOfAgents. This is because each of the corresponding subspaces
907 * contain a single coalition structure, and searching it can be done
908 * instantly
909 */
910 private void searchFirstOrLastLevel(int[] integers, Input input,
911 Output output, Result result) {
912 // Initialization
913 int numOfAgents = input.numOfAgents;
914 int[][] curCS;
915
916 if (integers.length == 1) {
917 curCS = new int[1][numOfAgents];
918 for (int i = 0; i <= numOfAgents - 1; i++)
919 curCS[0][i] = i + 1;
920 } else {
921 curCS = new int[numOfAgents][1];
922 for (int i = 0; i <= numOfAgents - 1; i++)
923 curCS[i][0] = i + 1;
924 }
925 double valueOfCurCS = input.getCoalitionStructureValue(curCS);
926
927 result.updateIPSolution(curCS, valueOfCurCS);
928
929 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
930 input, result);
931 }
932
933 // ******************************************************************************************************
934
935 /**
936 * Check if the last two coalitions in the coalition structure satisfy the
937 * constraints (i.e., chech whether they appear in the list of feasible
938 * coalitions).
939 */
940 private boolean checkIfLastTwoCoalitionsSatisfyConstraints(int[] CS,
941 TreeSet<Integer> feasibleCoalitions) {
942 if (feasibleCoalitions
943 .contains(new Integer(CS[CS.length - 1])) == false)
944 return (false);
945 if (feasibleCoalitions
946 .contains(new Integer(CS[CS.length - 2])) == false)
947 return (false);
948 return (true);
949 }
950
951 // ******************************************************************************************************
952
953 /**
954 * bit[i] is the bit representing agent a_i (e.g. given 4 agents,
955 * bit[2]=2=0010, bit[3]=4=0100, etc.)
956 */
957 private int[] init_bit(int numOfAgents) {
958 int[] bit = new int[numOfAgents + 1];
959 for (int i = 0; i < numOfAgents; i++)
960 bit[i + 1] = 1 << i;
961 return (bit);
962 }
963
964 // ******************************************************************************************************
965
966 /**
967 * This method initializes indexToStopAt. For more details see the comments
968 * at the beginning of "search_useBranchAndBound"
969 */
970 private long[] init_indexToStartAt(int numOfIntegers,
971 long[] numOfRemovedCombinations, long[] sumOf_numOfCombinations) {
972 long[] indexToStartAt = new long[numOfIntegers];
973 for (int i = 0; i < numOfIntegers; i++) {
974 indexToStartAt[i] = sumOf_numOfCombinations[i]
975 + numOfRemovedCombinations[i];
976 }
977 return (indexToStartAt);
978 }
979
980 // ******************************************************************************************************
981
982 /**
983 * This method initializes indexToStopAt. For more details see the comments
984 * at the beginning of "search_useBranchAndBound"
985 */
986 private long[] init_indexToStopAt(int numOfIntegers,
987 long[] numOfRemovedCombinations) {
988 long[] indexToStopAt = new long[numOfIntegers];
989 for (int i = 0; i < numOfIntegers; i++) {
990 indexToStopAt[i] = numOfRemovedCombinations[i] + 1;
991 }
992 return (indexToStopAt);
993 }
994
995 // ******************************************************************************************************
996
997 /**
998 * This method initializes "init_max_first_member_of_M". For more details
999 * see the comments at the beginning of "search_useBranchAndBound"
1000 */
1001 private int[] init_max_first_member_of_M(int[] integers, int[] length_of_A,
1002 boolean ipUsesLocalBranchAndBound) {
1003 int[] max_first_member_of_M = new int[integers.length];
1004 int i = integers.length - 1;
1005
1006 if ((ipUsesLocalBranchAndBound) && (relevantNodes != null)
1007 && (integers.length > 2)) {
1008 max_first_member_of_M[i] = length_of_A[i] - integers[i] + 1;
1009 i--;
1010 }
1011 while (i >= 0) {
1012 max_first_member_of_M[i] = length_of_A[i] - integers[i] + 1;
1013 i--;
1014 while ((i >= 0) && (integers[i] == integers[i + 1])) {
1015 max_first_member_of_M[i] = max_first_member_of_M[i + 1];
1016 i--;
1017 }
1018 }
1019 return (max_first_member_of_M);
1020 }
1021
1022 // ******************************************************************************************************
1023
1024 /**
1025 * This method initializes "numOfCombinatinos". For more details see the
1026 * comments at the beginning of "search_useBranchAndBound"
1027 */
1028 private long[][] init_numOfCombinations(int[] integers, int[] length_of_A,
1029 int[] max_first_member_of_M) {
1030 long[][] numOfCombinations = new long[integers.length][];
1031 for (int i = 0; i <= integers.length - 1; i++) {
1032 if (length_of_A[i] == integers[i]) {
1033 numOfCombinations[i] = new long[1];
1034 numOfCombinations[i][0] = 1;
1035 } else {
1036 numOfCombinations[i] = new long[max_first_member_of_M[i]];
1037 for (int j = 0; j <= max_first_member_of_M[i] - 1; j++) {
1038 numOfCombinations[i][j] = Combinations.binomialCoefficient(
1039 length_of_A[i] - (j + 1), integers[i] - 1);
1040 }
1041 }
1042 }
1043 return (numOfCombinations);
1044 }
1045
1046 // ******************************************************************************************************
1047
1048 /**
1049 * This method initializes "sumOf_numOfCombinations". For more details see
1050 * the comments at the beginning of "search_useBranchAndBound"
1051 */
1052 private long[] init_sumOf_numOfCombinations(long[][] numOfCombinations,
1053 int[] integers, int[] length_of_A, int[] max_first_member_of_M) {
1054 long[] sumOf_numOfCombinations = new long[integers.length];
1055
1056 for (int i = 0; i <= integers.length - 1; i++) {
1057 if (length_of_A[i] == integers[i]) {
1058 sumOf_numOfCombinations[i] = 1;
1059 } else {
1060 sumOf_numOfCombinations[i] = 0;
1061 for (int j = 0; j <= max_first_member_of_M[i] - 1; j++) {
1062 sumOf_numOfCombinations[i] = sumOf_numOfCombinations[i]
1063 + numOfCombinations[i][j];
1064 }
1065 }
1066 }
1067 return (sumOf_numOfCombinations);
1068 }
1069
1070 // ******************************************************************************************************
1071
1072 /**
1073 * This method initializes: numOfRemovedCombinations. (For more details on:
1074 * "numOfRemovedCombinations", read the comments that are in the beginning
1075 * of method: "search_useBranchAndBound")
1076 */
1077 private long[] init_numOfRemovedCombinations(int[] integers,
1078 int[] length_of_A, int[] max_first_member_of_M) {
1079 long[] numOfRemovedCombinations = new long[integers.length];
1080
1081 for (int i = 0; i <= integers.length - 1; i++) {
1082 if (length_of_A[i] == integers[i]) {
1083 numOfRemovedCombinations[i] = 0;
1084 } else {
1085 numOfRemovedCombinations[i] = 0;
1086 for (int j = max_first_member_of_M[i]; j <= length_of_A[i]
1087 - integers[i]; j++) {
1088 numOfRemovedCombinations[i] = numOfRemovedCombinations[i]
1089 + Combinations.binomialCoefficient(
1090 length_of_A[i] - (j + 1), integers[i] - 1);
1091 }
1092 }
1093 }
1094 return (numOfRemovedCombinations);
1095 }
1096
1097 // ******************************************************************************************************
1098
1099 /**
1100 * This method initializes increment (For more details on: "increment", read
1101 * the comments that are in the beginning of method:
1102 * "search_useBranchAndBound")
1103 */
1104 private long[][] init_increment(int[] integers, long[][] numOfCombinations,
1105 long[] sumOf_numOfCombinations, int[] max_first_member_of_M,
1106 boolean ipUsesLocalBranchAndBound) {
1107 long[][] increment = new long[integers.length][];
1108 increment[integers.length - 1] = new long[1];
1109 increment[integers.length - 1][0] = 1;
1110
1111 int s = integers.length - 2;
1112 while (s >= 0) // make sure to define s as integer
1113 {
1114 if ((integers[s] != integers[s + 1]) || ((ipUsesLocalBranchAndBound)
1115 && (s == integers.length - 2) && (integers.length > 2))) {
1116 // For the possible combinations of M[s], the increment would be
1117 // equal to the number of possible
1118 // combinations for M[s+1], multiplied by the increment of each
1119 // of these combinations.
1120 increment[s] = new long[1];
1121 increment[s][0] = sumOf_numOfCombinations[s + 1]
1122 * increment[s + 1][0];
1123 s--;
1124 } else {
1125 /*
1126 * Calculate the increment for the possible combinations of
1127 * M[s].
1128 *
1129 * Here, we calculate the increment for the combinations that
1130 * start with j, where: j = 1,2,..., max_first_member_of_M[s]),
1131 * although they will all have the same increment, which is the
1132 * number of possible combinations of M[s+1], multiplied by the
1133 * increment of each of these combinations.
1134 */
1135 increment[s] = new long[max_first_member_of_M[s]];
1136 for (int i = 0; i <= max_first_member_of_M[s] - 1; i++) {
1137 increment[s][i] = 0;
1138 for (int j = i; j <= max_first_member_of_M[s] - 1; j++)
1139 increment[s][i] += (numOfCombinations[s + 1][j]
1140 * increment[s + 1][0]);
1141 }
1142 s--;
1143
1144 /*
1145 * If there exists (M[i] : i<s) such that (M[i]=M[i+1]), then
1146 * calculate the increment for the possible combinations of
1147 * M[i].
1148 *
1149 * For the possible combinations of M[i] that start with j
1150 * (j=1,2,...,max_first_member_of_M[i]), the increment is equal
1151 * to the number of possible combinations of M[i+1] that start
1152 * with j, multiplied by the increment of each of these
1153 * combinations.
1154 */
1155 while ((s >= 0) && (integers[s] == integers[s + 1])) {
1156 increment[s] = new long[max_first_member_of_M[s]];
1157 for (int i = 0; i <= max_first_member_of_M[s] - 1; i++) {
1158 increment[s][i] = 0;
1159 for (int j = i; j <= max_first_member_of_M[s] - 1; j++)
1160 increment[s][i] += (numOfCombinations[s + 1][j]
1161 * increment[s + 1][j]);
1162 }
1163 s--;
1164 }
1165
1166 /*
1167 * Now, knowing that M[s]!=M[s+1], we calculate the increment
1168 * for the possible combinations of M[s]
1169 *
1170 * Note that these would all have the same increment, which is
1171 * the summation of the following: the number of possible
1172 * combinations for M[s+1] that start with j, multiplied by the
1173 * increment of each of these combinations, where:
1174 * j=1,2,...,max_first_member_of_M[s+1]
1175 */
1176 if (s >= 0) {
1177 increment[s] = new long[1];
1178 increment[s][0] = 0;
1179 for (int j = 0; j <= max_first_member_of_M[s + 1] - 1; j++)
1180 increment[s][0] += (numOfCombinations[s + 1][j]
1181 * increment[s + 1][j]);
1182 s--;
1183 }
1184 }
1185 }
1186 return (increment);
1187 }
1188
1189 // ******************************************************************************************************
1190
1191 /**
1192 * This method sets M[i] to be the combination located at: index_of_M[i]
1193 */
1194 private int[][] init_M(long[] index_of_M, int[] integers, int[] length_of_A,
1195 int numOfAgents) {
1196 long[][] pascalMatrix = Combinations.initPascalMatrix(numOfAgents + 1,
1197 numOfAgents + 1);
1198
1199 // Memory allocation:
1200 int[][] M = new int[integers.length][];
1201 for (int s = 0; s <= integers.length - 1; s++) {
1202 M[s] = new int[integers[s]];
1203 }
1204
1205 // Setting M[0], M[1], ..., M[integers.length-1]:
1206 for (int i = 0; i <= integers.length - 1; i++) {
1207 /* 1 */int j = 1;
1208 long index = index_of_M[i];
1209 int s1 = integers[i];
1210
1211 boolean done = false;
1212 do {
1213 // Check the values: pascalMatrix[s1,1],pascalMatrix[s1,2],...
1214 /* 2 */ int x = 1;
1215 while (pascalMatrix[s1 - 1][x - 1] < index)
1216 x++;
1217
1218 /* 3 */ M[i][j - 1] = (length_of_A[i] - s1 + 1) - x + 1;
1219
1220 /* 4 */ if (pascalMatrix[s1 - 1][x - 1] == index) {
1221 // Set the rest of the coalition as follows:
1222 for (int k = j; k <= integers[i] - 1; k++)
1223 M[i][k] = M[i][k - 1] + 1;
1224 done = true;
1225 }
1226 // Otherwise:
1227 else {
1228 j = j + 1;
1229 index = index - pascalMatrix[s1 - 1][x - 2];
1230 s1 = s1 - 1;
1231 }
1232 } while (done == false);
1233 }
1234 return (M);
1235 }
1236
1237 // ******************************************************************************************************
1238
1239 /**
1240 * This method initializes index_of_M (Converts the index into a list of
1241 * indices for every list) (For more details on: "index_of_M", read the
1242 * comments that are in the beginning of method: "search_useBranchAndBound")
1243 */
1244 private long[] init_index_of_M(long index, int[] integers,
1245 long[][] increment, int[] max_first_member_of_M,
1246 long[][] numOfCombinations, long[] numOfRemovedCombinations,
1247 long[] sumOf_numOfCombinations) {
1248 /*
1249 * Here, we will use the variables: counter1, counter2. counter1 will be
1250 * used to count the coalition structures that were scanned before
1251 * reaching the current one (i.e., before reaching the coalition
1252 * structure that is located at: "index"). counter2 will be used to
1253 * count the combinations that were scanned before reaching the current
1254 * M
1255 *
1256 * As an example, I will refer to figure 3 in the paper:
1257 * "Near-optimal anytime coalition structure generation".
1258 *
1259 * In figure 3, in the list of possible combinations of M[0], we will
1260 * consider the index of combination: "6,7" to be: 1, and the index of
1261 * combination: "5,7" to be: 2, and so on.
1262 *
1263 * In figure 3, we have:
1264 *
1265 * "integers" contains the values: 2,2,3
1266 *
1267 * "numOfCombinations[0]" contains the values: 6,5,4,3
1268 * "numOfCombinations[1]" contains the values: 4,3,2,1
1269 * "numOfCombinations[2]" contains the value : 1
1270 *
1271 * "sumOf_numOfCombinations" contains the values: 18,10,1
1272 *
1273 * "numOfRemovedCombinations" contains the values: 3,0,0
1274 *
1275 * "increment[0]" contains the values: 10,6,3,1 "increment[1]" contains
1276 * the value : 1 "increment[2]" contains the value : 1
1277 *
1278 * "max_first_member_of_M" contains the values: 4,4,1
1279 *
1280 * "counter1" contains the value: 48 "counter2" contains the value: 5
1281 * (when searching for M[0]) contians the value: 8 (when searching for
1282 * M[1])
1283 */
1284
1285 long counter1 = 0;
1286 long counter2 = 1;
1287 long[] index_of_M = new long[integers.length];
1288
1289 // Setting index_of_M[integers.length-1]:
1290 index_of_M[integers.length - 1] = 1;
1291
1292 // Setting index_of_M[0], index_of_M[1], ...,
1293 // index_of_M[integers.length-2]:
1294 int min_first_member_of_M = 0;
1295 for (int i = 0; i <= integers.length - 2; i++) {
1296 if (sumOf_numOfCombinations[i] == 1) // If the list of possible
1297 // combiantions of M[i]
1298 // contains one
1299 // combinations...
1300 {
1301 index_of_M[i] = 1;
1302 } else if (increment[i].length == 1) // i.e., if all the possible
1303 // combinations of M[i] had
1304 // equal increments...
1305 {
1306 counter1 = 0;
1307 counter2 = 1;
1308 if (min_first_member_of_M > 0)
1309 for (int j = 0; j <= min_first_member_of_M - 1; j++)
1310 counter2 += numOfCombinations[i][j];
1311
1312 long steps = (long) (Math.ceil(index / (double) increment[i][0])
1313 - 1);
1314 counter1 += steps * increment[i][0];
1315 counter2 += steps;
1316
1317 index_of_M[i] = counter2;
1318 index -= counter1;
1319
1320 if ((i >= integers.length - 1)
1321 || (integers[i] != integers[i + 1]))
1322 min_first_member_of_M = 0;
1323 } else
1324 // i.e., if the possible combinations of M[i] had different
1325 // increments. (In this case, all the combinations
1326 // that start with j, where j=1,2,...,max_first_member_of_M[i],
1327 // would have the increment = "increment[i][j]")
1328 {
1329 counter1 = 0;
1330 counter2 = 1;
1331 if (min_first_member_of_M > 0)
1332 for (int j = 0; j < min_first_member_of_M; j++)
1333 counter2 += numOfCombinations[i][j];
1334
1335 /*
1336 * Note that counter1 is initially equal to 0, and counter2 is
1337 * initially equal to 1. Now, in figure 3, we have the
1338 * following:
1339 *
1340 * In the list of possible combinations of M[0], we have 6
1341 * combinations that start with 1, each of which the increment
1342 * is 10. Therefore, if index <= counter1+60, then M[0] must
1343 * start with 1. Otherwise: (1) we add 60 to counter1, (2) we
1344 * add 6 to counter2, (3) we move to the next setp.
1345 *
1346 * In the list of possible combinations of M[0], we have 5
1347 * combinations that start with 2, each of which the increment
1348 * is 6. Therefore, if index <= counter1+30, then M[0] must
1349 * start with 2. Otherwise: (1) we add 30 to counter1, (2) we
1350 * add 5 to counter2, (3) we move to the next setp.
1351 *
1352 * This is done until we find the required first element of
1353 * M[0], let us denote it by "x". Now, we need to know which of
1354 * these combinations (that start with "x") is the required one.
1355 *
1356 * We count the steps that we take within the coalitions that
1357 * start with "x". For example, if the required combination was
1358 * 80, then M[0] would be one of the combinations that start
1359 * with 2, and the number of steps that we take within these
1360 * combinations is 3.
1361 */
1362 for (int j = min_first_member_of_M; j < max_first_member_of_M[i]; j++) {
1363 if (index <= counter1
1364 + (numOfCombinations[i][j] * increment[i][j])) {
1365 long steps = (long) Math.ceil(
1366 (index - counter1) / (double) increment[i][j])
1367 - 1;
1368 counter1 += steps * increment[i][j];
1369 counter2 += steps;
1370
1371 index_of_M[i] = counter2;
1372 index -= counter1;
1373
1374 if ((i < integers.length - 1)
1375 && (integers[i] == integers[i + 1]))
1376 min_first_member_of_M = j;
1377 else
1378 min_first_member_of_M = 0;
1379
1380 break;
1381 } else {
1382 long steps = numOfCombinations[i][j];
1383 counter1 += steps * increment[i][j];
1384 counter2 += steps;
1385 }
1386 }
1387 }
1388 }
1389
1390 // When calculating a combination, based on its index, we assume
1391 // 1,2,..,n to be the last combination
1392 // (instead of the first). Therefore, we flip the indices (i.e., the
1393 // index: i becomes: n-i)
1394 for (int i = 0; i <= index_of_M.length - 1; i++)
1395 index_of_M[i] = (sumOf_numOfCombinations[i]
1396 + numOfRemovedCombinations[i]) - index_of_M[i] + 1;
1397
1398 return (index_of_M);
1399 }
1400
1401 // ******************************************************************************************************
1402
1403 /**
1404 * This method initializes A. (For more details on: "A", read the comments
1405 * that are in the beginning of method: "search_useBranchAndBound")
1406 */
1407 private int[][] init_A(int numOfAgents, int[] integers, int[][] M,
1408 int[] length_of_A) {
1409 /*
1410 * Note that if we have a subspace [n_1, n_2, ..., n_s], then we only
1411 * need: A[1], A[2], ... A[s-1]. Because A[s] would simply contain all
1412 * of the remaining agents.
1413 */
1414 int[][] A = new int[integers.length - 1][];
1415 for (int s = 0; s <= integers.length - 2; s++) {
1416 A[s] = new int[length_of_A[s]];
1417 if (s == 0) {
1418 for (int j1 = 0; j1 <= numOfAgents - 1; j1++) {
1419 A[s][j1] = j1 + 1;
1420 }
1421 } else {
1422 int j1 = 0;
1423 int j2 = 0;
1424 for (int j3 = 0; j3 <= length_of_A[s - 1] - 1; j3++) {
1425 if ((j1 >= M[s - 1].length) || (j3 + 1 != M[s - 1][j1])) {
1426 A[s][j2] = A[s - 1][j3];
1427 j2++;
1428 } else
1429 j1++;
1430 }
1431 }
1432 }
1433 return (A);
1434 }
1435
1436 // ******************************************************************************************************
1437
1438 /**
1439 * This method initializes "length_of_A". For more details see the comments
1440 * at the beginning of "search_useBranchAndBound"
1441 */
1442 private int[] init_length_of_A(int numOfAgents, int[] integers) {
1443 int[] length_of_A = new int[integers.length];
1444
1445 length_of_A[0] = numOfAgents;
1446 if (integers.length > 1)
1447 for (int s = 1; s <= integers.length - 1; s++)
1448 length_of_A[s] = length_of_A[s - 1] - integers[s - 1];
1449
1450 return (length_of_A);
1451 }
1452
1453 // ******************************************************************************************************
1454
1455 /**
1456 * This method is similar to the method: "init_CS", except that it is used
1457 * with CS where the agents are represented as bits, rather than ints.
1458 */
1459 private int[] init_CS_hashTableVersion(int[][] M, int[][] A,
1460 int[] length_of_A, int[] bit, int numOfIntegers) {
1461 int[] CS = new int[integers.length];
1462
1463 for (int s = 0; s <= integers.length - 2; s++) {
1464 CS[s] = 0;
1465 for (int j1 = 0; j1 < M[s].length; j1++) {
1466 CS[s] |= bit[A[s][M[s][j1] - 1]];
1467 }
1468 }
1469 setTheLastTwoCoalitionsInCS(CS, M[numOfIntegers - 2], A, numOfIntegers,
1470 bit);
1471 return (CS);
1472 }
1473
1474 // ******************************************************************************************************
1475
1476 /**
1477 * This method initializes sumOf_values. (For more details on:
1478 * "sumOf_values", read the comments that are in the beginning of method:
1479 * "search_useBranchAndBound")
1480 */
1481 private double[] init_sumOf_values_hashTableVersion(int numOfIntegers,
1482 int[] CS, Input input) {
1483 double[] sumOf_values = new double[numOfIntegers + 1];
1484
1485 sumOf_values[0] = 0;
1486 for (int i = 1; i <= numOfIntegers; i++) {
1487 sumOf_values[i] = sumOf_values[i - 1]
1488 + input.getCoalitionValue(CS[i - 1]);
1489 }
1490
1491 return (sumOf_values);
1492 }
1493
1494 // ******************************************************************************************************
1495
1496 /**
1497 * This method initializes sumOf_agents. (For more details on:
1498 * "sumOf_agents", read the comments that are in the beginning of method:
1499 * "search_useBranchAndBound")
1500 */
1501 private int[] init_sumOf_agents(int numOfIntegers, int[][] CS, int[] bit) {
1502 int[] sumOf_agents = new int[numOfIntegers + 1];
1503
1504 sumOf_agents[0] = 0;
1505
1506 for (int i = 1; i <= numOfIntegers; i++) {
1507 sumOf_agents[i] = sumOf_agents[i - 1];
1508 for (int j = 0; j < integers[i - 1]; j++) {
1509 sumOf_agents[i] += bit[CS[i - 1][j]];
1510 }
1511 }
1512
1513 return (sumOf_agents);
1514 }
1515
1516 // ******************************************************************************************************
1517
1518 /**
1519 * This method is similar to the method: "init_sumOf_agents", except that it
1520 * is used with CS where the agents are represented as bits, rather than
1521 * ints.
1522 */
1523 private int[] init_sumOf_agents_hashTableVersion(int numOfIntegers,
1524 int[] CS) {
1525 int[] sumOf_agents = new int[numOfIntegers + 1];
1526
1527 sumOf_agents[0] = 0;
1528
1529 for (int i = 1; i <= numOfIntegers; i++) {
1530 sumOf_agents[i] = sumOf_agents[i - 1] + CS[i - 1];
1531 }
1532
1533 return (sumOf_agents);
1534 }
1535
1536 // ******************************************************************************************************
1537
1538 /**
1539 * This method is only used in the subspace search methods. It sets "M" and
1540 * "index_of_M" (For more details, read the comments that are in the
1541 * beginning of method: "search_useBranchAndBound")
1542 */
1543 private void set_M_and_index_of_M(int[][] M, long[] index_of_M,
1544 final int[] length_of_A, final long[] indexToStartAt, int s2) {
1545 // Set the index of M to be the last index in the column
1546 index_of_M[s2] = indexToStartAt[s2];
1547
1548 // Set M, given its new index
1549 if (integers[s2] == integers[s2 - 1]) {
1550 if (M[s2 - 1][0] > 1)
1551 for (int j = 1; j < M[s2 - 1][0]; j++)
1552 index_of_M[s2] = index_of_M[s2]
1553 - Combinations.binomialCoefficient(
1554 length_of_A[s2] - j, integers[s2] - 1);
1555
1556 for (int j1 = 0; j1 < integers[s2]; j1++)
1557 M[s2][j1] = M[s2 - 1][0] + j1;
1558 } else
1559 for (int j1 = 0; j1 < integers[s2]; j1++)
1560 M[s2][j1] = 1 + j1;
1561 }
1562
1563 // ******************************************************************************************************
1564
1565 /**
1566 * Given: A[s-1], M[s-1], it sets the elements of: A[s]. These are simply
1567 * the emelents that are in A[s-1] that were not pointed at by M[s-1].
1568 */
1569 private void update_A(int[] A1, int[] A2, final int numOfAgents, int[] M,
1570 final int length_of_M) {
1571 int j1 = 0;
1572 int j2 = 0;
1573 for (int j3 = 0; j3 < A2.length; j3++) {
1574 if ((j1 >= length_of_M) || ((j3 + 1) != M[j1])) {
1575 A1[j2] = A2[j3];
1576 j2++;
1577 } else
1578 j1++;
1579 }
1580 }
1581
1582 // ******************************************************************************************************
1583
1584 /**
1585 * Note that we need both M[i] and A[i] in order to find CS[i]. (for more
1586 * detail on: M, A, CS, see the comments at the beginning of method:
1587 * "search_useBranchAndBound"). However, this does not apply to the last
1588 * coalition (i.e., CS[integers.length-1]). This is because
1589 * M[integers.length-2] and A[integers.length-2] are enough to find both:
1590 * CS[integers.length-2] and CS[integers.length-1]. This is because the
1591 * elements of: A[integers.length-2] that were not pointed at by
1592 * M[integers.length-2] must belong to CS[integers.length-1].
1593 */
1594 private void setTheLastTwoCoalitionsInCS(int[][] CS, int[][] M, int[][] A,
1595 final int[] length_of_A, final int numOfIntegers) {
1596 int j1 = 0;
1597 int j2 = 0;
1598 for (int j3 = 0; j3 < length_of_A[numOfIntegers - 2]; j3++) {
1599 if ((j1 >= integers[numOfIntegers - 2])
1600 || ((j3 + 1) != M[numOfIntegers - 2][j1])) {
1601 CS[numOfIntegers - 1][j2] = A[numOfIntegers - 2][j3];
1602 j2++;
1603 } else {
1604 CS[numOfIntegers - 2][j1] = A[numOfIntegers - 2][j3];
1605 j1++;
1606 }
1607 }
1608 }
1609
1610 // ******************************************************************************************************
1611
1612 /**
1613 * This method is similar to the method: "setTheLastTwoCoalitionsInCS" that
1614 * is mentioned above, except that it is used with CS where the agents are
1615 * represented as bits, rather than ints.
1616 */
1617 private void setTheLastTwoCoalitionsInCS(int[] CS, int[] M, int[][] A,
1618 final int numOfIntegers, final int[] bit) {
1619 int result1 = 0;
1620 int result2 = 0;
1621 int m = integers[numOfIntegers - 2] - 1;
1622 int a = A[numOfIntegers - 2].length - 1;
1623 do {
1624 if (a == M[m] - 1) {
1625 result1 += bit[A[numOfIntegers - 2][a]];
1626 if (m == 0) {
1627 a--;
1628 break;
1629 }
1630 m--;
1631 } else
1632 result2 += bit[A[numOfIntegers - 2][a]];
1633
1634 a--;
1635 } while (a >= 0);
1636
1637 while (a >= 0) {
1638 result2 += bit[A[numOfIntegers - 2][a]];
1639 a--;
1640 }
1641 CS[numOfIntegers - 2] = result1;
1642 CS[numOfIntegers - 1] = result2;
1643 }
1644
1645 // ******************************************************************************************************
1646
1647 /**
1648 * This method sets CS to the coalition structure located at the given
1649 * index.
1650 */
1651 private void set_CS_given_its_index(final int numOfAgents, int[][] CS,
1652 final long index, final int[] length_of_A, final long[][] increment,
1653 final int[] max_first_member_of_M, final long[][] numOfCombinations,
1654 final long[] numOfRemovedCombinations,
1655 final long[] sumOf_numOfCombinations) {
1656 // Convert the index into a list of indices for every list
1657 long[] index_of_M = init_index_of_M(index, integers, increment,
1658 max_first_member_of_M, numOfCombinations,
1659 numOfRemovedCombinations, sumOf_numOfCombinations);
1660
1661 // Set M[i] to be the coalition located at: index_of_M[i]
1662 int[][] M = init_M(index_of_M, integers, length_of_A, numOfAgents);
1663
1664 // Set A
1665 int[][] A = init_A(numOfAgents, integers, M, length_of_A);
1666
1667 // Finding the actual CS...
1668 for (int s = 0; s <= integers.length - 3; s++)
1669 for (int i = 0; i <= M[s].length - 1; i++)
1670 CS[s][i] = A[s][M[s][i] - 1];
1671 setTheLastTwoCoalitionsInCS(CS, M, A, length_of_A, integers.length);
1672 }
1673
1674 // ******************************************************************************************************
1675
1676 /**
1677 * This method is similar to the method: "set_CS_given_its_index" that is
1678 * mentioned above, except that it is used with CS where the agents are
1679 * represented as bits, rather than ints.
1680 */
1681 private void set_CS_given_its_index(final int numOfAgents, int[] CS,
1682 final long index, final int[] length_of_A, final long[][] increment,
1683 final int[] max_first_member_of_M, final long[][] numOfCombinations,
1684 final long[] numOfRemovedCombinations,
1685 final long[] sumOf_numOfCombinations, final int[] bit) {
1686 // Convert the index into a list of indices for every list
1687 long[] index_of_M = init_index_of_M(index, integers, increment,
1688 max_first_member_of_M, numOfCombinations,
1689 numOfRemovedCombinations, sumOf_numOfCombinations);
1690
1691 // Set M[i] to be the coalition located at: index_of_M[i]
1692 int[][] M = init_M(index_of_M, integers, length_of_A, numOfAgents);
1693
1694 // Set A
1695 int[][] A = init_A(numOfAgents, integers, M, length_of_A);
1696
1697 // Finding the actual CS...
1698 for (int s = 0; s <= integers.length - 3; s++) {
1699 CS[s] = 0;
1700 for (int j1 = 0; j1 <= M[s].length - 1; j1++)
1701 CS[s] |= bit[A[s][M[s][j1] - 1]];
1702 }
1703
1704 int remainingAgents = 0;
1705 for (int i = length_of_A[integers.length - 2] - 1; i >= 0; i--) {
1706 remainingAgents |= bit[A[integers.length - 2][i]];
1707 }
1708 setTheLastTwoCoalitionsInCS(CS, M[integers.length - 2], A,
1709 integers.length, bit);
1710 }
1711
1712 // ******************************************************************************************************
1713
1714 /**
1715 * This method uses the technique called: "local branch and bound". In more
1716 * detail, For every subset of agents S, we record the best value found so
1717 * far, and that is regardless of the way the agents in S are partitioned.
1718 *
1719 * For example, given S={a,b,c,d}, and while we are cycling through
1720 * coalition structures in subspace [2,2,4,4], we we might come across the
1721 * following set of coalitions: {{a,b},{c,d},...}, and suppose that
1722 * v({2,3})+v({5,9})=100 then we store in the table the value: 100.
1723 *
1724 * After that, while cycling through coalition structures in subspace
1725 * [1,1,2,4,4,4], suppose that we come across the following set of
1726 * coalitions: {{a},{c},{b,d},...}, then: * if( v({a})+v({c})+v({b,d}=80 ),
1727 * then there is no need to continue searching the tree of coalitions that
1728 * comes with {{a},{c},{b,d},...} * if( v({a})+v({c})+v({b,d}=120 ), then
1729 * the table is updated, and the value 120 is stored instead of 100.
1730 */
1731 private boolean useLocalBranchAndBound(Input input,
1732 IDPSolver_whenRunning_ODPIP localBranchAndBoundObject,
1733 double[] sumOf_values, int[] sumOf_agents, int s2, int newCoalition,
1734 double valueOfNewCoalition) {
1735 boolean result = false;
1736
1737 // if((
1738 // localBranchAndBoundObject.getLowerBoundForCurrentAgents(sumOf_agents[s2+1])
1739 // > sumOf_values[s2+1] )||(
1740 // localBranchAndBoundObject.getLowerBoundForCurrentAgents(newCoalition)
1741 // > valueOfNewCoalition ))
1742 if ((localBranchAndBoundObject.getValueOfBestPartitionFound(
1743 sumOf_agents[s2 + 1]) - sumOf_values[s2 + 1] > 0.00000000005)
1744 || (localBranchAndBoundObject.getValueOfBestPartitionFound(
1745 newCoalition) - valueOfNewCoalition > 0.00000000005))
1746 result = true;
1747
1748 // Update the local-branch-and-bound table if necessary
1749 // if(
1750 // localBranchAndBoundObject.getLowerBoundForCurrentAgents(sumOf_agents[s2+1])
1751 // < sumOf_values[s2+1] )
1752 if (localBranchAndBoundObject.getValueOfBestPartitionFound(
1753 sumOf_agents[s2 + 1]) - sumOf_values[s2 + 1] < -0.00000000005)
1754 localBranchAndBoundObject.updateValueOfBestPartitionFound(
1755 sumOf_agents[s2 + 1], sumOf_values[s2 + 1]);
1756
1757 // if( localBranchAndBoundObject.getLowerBoundForCurrentAgents(
1758 // newCoalition ) < valueOfNewCoalition )
1759 if (localBranchAndBoundObject.getValueOfBestPartitionFound(newCoalition)
1760 - valueOfNewCoalition < -0.00000000005)
1761 localBranchAndBoundObject.updateValueOfBestPartitionFound(
1762 newCoalition, valueOfNewCoalition);
1763
1764 return (result);
1765 }
1766}
Note: See TracBrowser for help on using the repository browser.