source: ip/src/main/java/geniusweb/ip/dpSolver/DPSolver.java@ 47

Last change on this file since 47 was 47, checked in by bart, 3 years ago

Refactor to help reusing partiesserver.
File size: 30.6 KB
Line 
1/**
2 * The dynamic programming solvers. This code is used for either DP, IDP, ODP, or the IDP part of ODP-IP
3 * @author Talal Rahwan
4 */
5package geniusweb.ip.dpSolver;
6
7import java.util.Arrays;
8
9import geniusweb.ip.general.Combinations;
10import geniusweb.ip.inputOutput.Input;
11import geniusweb.ip.inputOutput.SolverNames;
12import geniusweb.ip.inputOutput.ValueDistribution;
13import geniusweb.ip.mainSolver.Result;
14
15public class DPSolver {
16 int[] t; // t[i] contains the first half of the best split of coalition i
17 // (where the coalition is represented in bit format)
18 // this is only used by DP, i.e., it is not used by IDP, ODP, or the IDP
19 // part of ODP-IP
20
21 private double[] f;
22
23 private boolean stop = false;
24
25 private Input input;
26
27 private Result result;
28
29 public DPSolver(Input input, Result result) {
30 this.input = input;
31 this.result = result;
32 }
33
34 // *********************************************************************************************************
35
36 public void set_f(int index, double value) {
37 if (input.solverName == SolverNames.ODPIP)
38 result.idpSolver_whenRunning_ODPIP
39 .updateValueOfBestPartitionFound(index, value);
40 else
41 f[index] = value;
42 }
43
44 public double get_f(int index) {
45 if (input.solverName == SolverNames.ODPIP)
46 return result.idpSolver_whenRunning_ODPIP
47 .getValueOfBestPartitionFound(index);
48 else
49 return f[index];
50 }
51
52 // *********************************************************************************************************
53
54 public void setStop(boolean value) {
55 stop = value;
56 }
57
58 public boolean getStop() {
59 return stop;
60 }
61
62 // *********************************************************************************************************
63
64 /**
65 * Run DP or IDP, or the IDP part of ODP-IP. To specify which algorithm to
66 * run, set input.solverName to either SolverNames.DP or SolverNames.IDP, or
67 * SolverNames.ODPIP
68 */
69 public void runDPorIDP() {
70 if (input.solverName != SolverNames.ODPIP) {
71 f = new double[input.coalitionValues.length];
72 for (int i = 0; i < f.length; i++)
73 set_f(i, input.coalitionValues[i]);
74 }
75 int numOfAgents = input.numOfAgents;
76 set_f(0, 0); // just in case, set the value of the empty set to 0
77
78 // initialization
79 long[] requiredTimeForEachSize = new long[numOfAgents + 1];
80 requiredTimeForEachSize[1] = 0;
81 long[] startTimeForEachSize = new long[numOfAgents + 1];
82 int grandCoalition = (1 << numOfAgents) - 1;
83 int numOfCoalitions = 1 << numOfAgents;
84 int bestHalfOfGrandCoalition = -1;
85 long startTime = System.currentTimeMillis();
86 result.set_dpMaxSizeThatWasComputedSoFar(1);
87
88 // Step 1 (initialization for step 2). Basically, initialize the t
89 // table.
90 if (input.solverName == SolverNames.DP) { // Initialize the best half of
91 // every coalition to be the
92 // coalition itself.
93 t = new int[numOfCoalitions];
94 for (int coalition = 0; coalition < numOfCoalitions; coalition++)
95 t[coalition] = coalition;
96 }
97 // Step 2 (evaluate the possible splits of every coalition of size 2, 3,
98 // 4, ...)
99 for (int curSize = 2; curSize <= numOfAgents; curSize++)// For every
100 // size
101 {
102 if ((input.solverName == SolverNames.IDP)
103 || (input.solverName == SolverNames.ODPIP))
104 if (((int) (Math
105 .floor((2 * numOfAgents) / (double) 3)) < curSize)
106 && (curSize < numOfAgents))
107 continue;
108
109 // check if all splits of this size will be evaluated
110 boolean allSplitsOfCurSizeWillBeEvaluated = true;
111 for (int sizeOfFirstHalf = (int) Math.ceil(curSize
112 / (double) 2); sizeOfFirstHalf < curSize; sizeOfFirstHalf++)
113 if ((input.solverName == SolverNames.IDP)
114 || (input.solverName == SolverNames.ODPIP))
115 if ((sizeOfFirstHalf > numOfAgents - curSize)
116 && (curSize != numOfAgents)) {
117 allSplitsOfCurSizeWillBeEvaluated = false;
118 break;
119 }
120 startTimeForEachSize[curSize] = System.currentTimeMillis();
121
122 // If the coalition happens to be the grand coalition, then deal
123 // with this case saperately
124 if (curSize < numOfAgents) {
125 int numOfCoalitionsOfCurSize = (int) Combinations
126 .binomialCoefficient(numOfAgents, curSize);
127
128 if (allSplitsOfCurSizeWillBeEvaluated) // in this case, the
129 // evaluation of the
130 // splits can be done
131 // more efficiently
132 {
133 // Compute the number of possible splits of any coalition of
134 // size = "curSize"
135 int numOfPossibleSplits = 1 << curSize;
136 // Evaluate the possible splits of the current coalition
137 int[] curCoalition = Combinations
138 .getCombinationAtGivenIndex(curSize,
139 numOfCoalitionsOfCurSize - 1, numOfAgents);
140 evaluateSplitsEfficiently(curCoalition, curSize,
141 numOfPossibleSplits);
142 for (int i = 1; i < numOfCoalitionsOfCurSize; i++) {
143 Combinations.getPreviousCombination(numOfAgents,
144 curSize, curCoalition);
145 evaluateSplitsEfficiently(curCoalition, curSize,
146 numOfPossibleSplits);
147 if (getStop())
148 break;
149 }
150 } else {
151 // Compute the number of possible splits of any coalition of
152 // size = "curSize"
153 int numOfPossibleSplits = 1 << curSize;
154 // Compute the number of possible splits for every partition
155 // of "curSize" into "sizeOfFirstHalf" + "sizeOfSecondHalf"
156 long[] numOfPossibleSplitsBasedOnSizeOfFirstHalf = computeNumOfPossibleSplitsBasedOnSizeOfFirstHalf(
157 curSize);
158 // Evaluate the possible splits of the current coalition
159 int[] curCoalition = Combinations
160 .getCombinationAtGivenIndex(curSize,
161 numOfCoalitionsOfCurSize - 1, numOfAgents);
162 for (int i = 1; i < numOfCoalitionsOfCurSize; i++) {
163 Combinations.getPreviousCombination(numOfAgents,
164 curSize, curCoalition);
165 if ((input.solverName == SolverNames.DP)
166 || (input.useEfficientImplementationOfIDP))
167 evaluateSplitsEfficiently(curCoalition, curSize,
168 numOfPossibleSplits);
169 else
170 evaluateSplits(curCoalition, curSize,
171 numOfPossibleSplitsBasedOnSizeOfFirstHalf);
172
173 if (getStop())
174 break;
175 }
176 }
177 if (getStop())
178 break;
179 } else
180 bestHalfOfGrandCoalition = evaluateSplitsOfGrandCoalition();
181
182 // Update the value of the best CS found so far by IDP
183 if (curSize < numOfAgents) {
184 bestHalfOfGrandCoalition = evaluateSplitsOfGrandCoalition();
185 int[] bestCSFoundSoFar = getOptimalSplit(grandCoalition,
186 bestHalfOfGrandCoalition);
187 int[][] bestCSFoundSoFar_byteFormat = Combinations
188 .convertSetOfCombinationsFromBitToByteFormat(
189 bestCSFoundSoFar, numOfAgents);
190 result.updateDPSolution(bestCSFoundSoFar_byteFormat,
191 +input.getCoalitionStructureValue(
192 bestCSFoundSoFar_byteFormat));
193 if (input.solverName == SolverNames.ODPIP)
194 result.updateIPSolution(bestCSFoundSoFar_byteFormat,
195 input.getCoalitionStructureValue(
196 bestCSFoundSoFar_byteFormat));
197 }
198 // Print the time that was taken to perform this step
199 requiredTimeForEachSize[curSize] = System.currentTimeMillis()
200 - startTimeForEachSize[curSize];
201 if (input.solverName == SolverNames.DP) {
202 System.out.println(
203 " The time for DP to finish evaluating the splittings of coalitions of size "
204 + curSize + " is: "
205 + requiredTimeForEachSize[curSize]);
206 } else { // i.e., if it is IDP or ODP-IP
207 System.out.print(
208 " The time for IDP to finish evaluating the splittings of coalitions of size "
209 + curSize + " is: "
210 + requiredTimeForEachSize[curSize]);
211 System.out.println(". The best CS found so far by IDP is : "
212 + Arrays.deepToString(result.get_dpBestCSFound())
213 + " , its value is: "
214 + result.get_dpValueOfBestCSFound());
215 }
216 // Update the maximum size that DP has finished searching
217 result.set_dpMaxSizeThatWasComputedSoFar(curSize);
218 }
219 if (getStop())
220 return;
221
222 // Initialize the result
223 result.dpTimeForEachSize = requiredTimeForEachSize;
224
225 // Step 3 (divide the grand coalition in the optimal way using the f
226 // table)
227 int[] bestCSFound = getOptimalSplit(grandCoalition,
228 bestHalfOfGrandCoalition);
229
230 // Set the final result
231 result.dpTime = System.currentTimeMillis() - startTime;
232 int[][] dpBestCSInByteFormat = Combinations
233 .convertSetOfCombinationsFromBitToByteFormat(bestCSFound,
234 numOfAgents);
235 result.updateDPSolution(dpBestCSInByteFormat,
236 input.getCoalitionStructureValue(dpBestCSInByteFormat));
237 if (input.solverName == SolverNames.ODPIP)
238 result.updateIPSolution(dpBestCSInByteFormat,
239 input.getCoalitionStructureValue(dpBestCSInByteFormat));
240
241 // Print the distribution of f if required
242 if (input.printDistributionOfThefTable)
243 printDistributionOfThefTable();
244
245 if (input.printPercentageOf_v_equals_f)
246 printPercentageOf_v_equals_f();
247 }
248
249 // *********************************************************************************************************
250
251 /**
252 * Given a size, we can split it into [size-1,1], and [size-2,2],and so on.
253 * Now suppose that there are 1000 possible splits that match [size-1,1],
254 * and 8700 splits that match [size-2,2], and so on. This method computes
255 * these numbers of possible splits.
256 *
257 * numOfPossibleSplitsBasedOnSizeOfFirstHalf[ 3 ] is the number of possible
258 * splits, where the first half is equals 3
259 */
260 private long[] computeNumOfPossibleSplitsBasedOnSizeOfFirstHalf(int size) {
261 long[] numOfPossibleSplitsBasedOnSizeOfFirstHalf = new long[size];
262 for (int sizeOfFirstHalf = (int) Math.ceil(
263 size / (double) 2); sizeOfFirstHalf < size; sizeOfFirstHalf++) {
264 int sizeOfSecondHalf = size - sizeOfFirstHalf;
265 if (((size % 2) == 0) && (sizeOfFirstHalf == sizeOfSecondHalf))
266 numOfPossibleSplitsBasedOnSizeOfFirstHalf[sizeOfFirstHalf] = Combinations
267 .binomialCoefficient(size, sizeOfFirstHalf) / 2;
268 else
269 numOfPossibleSplitsBasedOnSizeOfFirstHalf[sizeOfFirstHalf] = Combinations
270 .binomialCoefficient(size, sizeOfFirstHalf);
271 }
272 return (numOfPossibleSplitsBasedOnSizeOfFirstHalf);
273 }
274
275 // *********************************************************************************************************
276
277 /**
278 * Splits the given coalition in an optimal way using the f table (i.e., it
279 * makes the optimal movements in the coalition structure graph). Here,
280 * coalitions are represented IN BIT FORMAT.
281 */
282 private int[] getOptimalSplit(int coalitionInBitFormat,
283 int bestHalfOfCoalition) {
284 int[] optimalSplit;
285 if (bestHalfOfCoalition == coalitionInBitFormat) {
286 optimalSplit = new int[1];
287 optimalSplit[0] = coalitionInBitFormat;
288 } else {
289 // Initialization
290 int[] arrayOfBestHalf = new int[2];
291 int[][] arrayOfOptimalSplit = new int[2][];
292 int[] arrayOfCoalitionInBitFormat = new int[2];
293
294 // Set the two halves
295 arrayOfCoalitionInBitFormat[0] = bestHalfOfCoalition;
296 arrayOfCoalitionInBitFormat[1] = coalitionInBitFormat
297 - bestHalfOfCoalition;
298
299 // For each one of the two halves
300 for (int i = 0; i < 2; i++) {
301 if ((input.solverName == SolverNames.DP))
302 arrayOfBestHalf[i] = t[arrayOfCoalitionInBitFormat[i]];
303 else
304 arrayOfBestHalf[i] = getBestHalf(
305 arrayOfCoalitionInBitFormat[i]); // We need to
306 // recompute the
307 // best half
308
309 arrayOfOptimalSplit[i] = getOptimalSplit(
310 arrayOfCoalitionInBitFormat[i], arrayOfBestHalf[i]);
311 }
312 // Set "optimalSplit" by combining "arrayOfOptimalSplit[0]" with
313 // "arrayOfOptimalSplit[1]"
314 optimalSplit = new int[arrayOfOptimalSplit[0].length
315 + arrayOfOptimalSplit[1].length];
316 int k = 0;
317 for (int i = 0; i < 2; i++)
318 for (int j = 0; j < arrayOfOptimalSplit[i].length; j++) {
319 optimalSplit[k] = arrayOfOptimalSplit[i][j];
320 k++;
321 }
322 }
323 return (optimalSplit);
324 }
325
326 // *********************************************************************************************************
327
328 /**
329 * @param CS an array of coalition structures.
330 * @return Split each coalition in the given structure in an optimal way
331 * using the f table (i.e., it makes the optimal movements in the
332 * coalition structure graph). Here, coalitions are represented IN
333 * BYTE FORMAT.
334 */
335 public int[][] getOptimalSplit(int[][] CS) {
336 // Initialization
337 int[][] optimalSplit = new int[CS.length][];
338 int numOfCoalitionsInFinalResult = 0;
339
340 // For every coalition CS[i] in CS, find the optimal split of CS[i], and
341 // store it in "optimalSplit[i]"
342 for (int i = 0; i < CS.length; i++) {
343 int coalitionInBitFormat = Combinations
344 .convertCombinationFromByteToBitFormat(CS[i]);
345 int bestHalfOfCoalitionInBitFormat = getBestHalf(
346 coalitionInBitFormat);
347 optimalSplit[i] = getOptimalSplit(coalitionInBitFormat,
348 bestHalfOfCoalitionInBitFormat);
349 numOfCoalitionsInFinalResult += optimalSplit[i].length;
350 }
351 // Group the optimal splits of different coalitions into "finalResult"
352 int[][] finalResult = new int[numOfCoalitionsInFinalResult][];
353 int k = 0;
354 for (int i = 0; i < CS.length; i++) // For every coalition CS[i] in CS
355 {
356 for (int j = 0; j < optimalSplit[i].length; j++) // For every
357 // coalition in
358 // the optimal
359 // split of
360 // CS[i]
361 {
362 finalResult[k] = Combinations
363 .convertCombinationFromBitToByteFormat(
364 optimalSplit[i][j], input.numOfAgents);
365 k++;
366 }
367 }
368 return (finalResult);
369 }
370
371 // *********************************************************************************************************
372
373 /**
374 * Evaluate the possible splittings of the grand coalition. The way this is
375 * done is similar to the way IP searches the second layer while scanning
376 * the input.
377 */
378 private int evaluateSplitsOfGrandCoalition() {
379 // Initialization
380 double curValue = -1;
381 double bestValue = -1;
382 int bestHalfOfGrandCoalitionInBitFormat = -1;
383 int numOfCoalitions = 1 << input.numOfAgents;
384 int grandCoalition = (1 << input.numOfAgents) - 1;
385
386 // Check the possible ways of splitting the grand coalition into two
387 // (non-empty) coalitions
388 for (int firstHalfOfGrandCoalition = (numOfCoalitions / 2)
389 - 1; firstHalfOfGrandCoalition < numOfCoalitions; firstHalfOfGrandCoalition++) {
390 int secondHalfOfGrandCoalition = numOfCoalitions - 1
391 - firstHalfOfGrandCoalition;
392 curValue = get_f(firstHalfOfGrandCoalition)
393 + get_f(secondHalfOfGrandCoalition);
394 if (curValue > bestValue) {
395 bestValue = curValue;
396 bestHalfOfGrandCoalitionInBitFormat = firstHalfOfGrandCoalition;
397 }
398 }
399 // Deal with the case where the first half is the grand coalition itself
400 int firstHalfOfGrandCoalition = grandCoalition;
401 curValue = get_f(firstHalfOfGrandCoalition);
402 if (curValue > bestValue) {
403 bestValue = curValue;
404 bestHalfOfGrandCoalitionInBitFormat = firstHalfOfGrandCoalition;
405 }
406 // Set t and f
407 set_f(grandCoalition, bestValue);
408 if (input.solverName == SolverNames.DP) // Then use the t table
409 t[grandCoalition] = bestHalfOfGrandCoalitionInBitFormat;
410
411 return (bestHalfOfGrandCoalitionInBitFormat);
412 }
413
414 // *********************************************************************************************************
415
416 /**
417 * Given a coalition of a particular size, this method evaluates the
418 * possible splits of this coalition into two. Here, the evaluation is based
419 * on f (not v) of each of the two halves.
420 *
421 * NOTE: this will be called when running DP or IDP, but not when running
422 * ODP!!
423 */
424 private void evaluateSplits(int[] coalitionInByteFormat, int coalitionSize,
425 long[] numOfPossibleSplitsBasedOnSizeOfFirstHalf) {
426 double curValue = -1;
427 double bestValue = -1;
428 int bestHalfOfCoalitionInBitFormat = -1;
429 int numOfAgents = input.numOfAgents;
430 int coalitionInBitFormat = Combinations
431 .convertCombinationFromByteToBitFormat(coalitionInByteFormat);
432
433 // bit[i] is the bit representing agent a_i (e.g. given 4 agents,
434 // bit[2]=2=0010, bit[3]=4=0100, etc.)
435 int[] bit = new int[numOfAgents + 1];
436 for (int i = 0; i < numOfAgents; i++)
437 bit[i + 1] = 1 << i;
438
439 // Check the possible ways of splitting the coalition into two
440 // (non-empty) coalitions
441 for (int sizeOfFirstHalf = (int) Math.ceil(coalitionSize
442 / (double) 2); sizeOfFirstHalf < coalitionSize; sizeOfFirstHalf++) {
443 // int sizeOfSecondHalf = (int)(coalitionSize - sizeOfFirstHalf);
444
445 // If we want to evaluate only the useful splits, and the size of
446 // the biggest half (which, here, happens to
447 // be the first half) is greater than the number of agents minus the
448 // size of the coalition, then continue.
449 if (((input.solverName == SolverNames.IDP)
450 || (input.solverName == SolverNames.ODPIP))
451 && (sizeOfFirstHalf > numOfAgents - coalitionSize)
452 && (coalitionSize != numOfAgents))
453 continue;
454
455 // Set the initial indices of the members of the first half
456 int[] indicesOfMembersOfFirstHalf = new int[sizeOfFirstHalf];
457 for (int i = 0; i < sizeOfFirstHalf; i++)
458 indicesOfMembersOfFirstHalf[i] = i + 1;
459
460 // Compute the first half (in bit format)
461 int firstHalfInBitFormat = 0;
462 for (int i = 0; i < sizeOfFirstHalf; i++)
463 firstHalfInBitFormat += bit[coalitionInByteFormat[indicesOfMembersOfFirstHalf[i]
464 - 1]];
465
466 // Compute the second half (in bit format)
467 int secondHalfInBitFormat = (coalitionInBitFormat
468 - firstHalfInBitFormat);
469
470 // Update the functions t and f
471 curValue = get_f(firstHalfInBitFormat)
472 + get_f(secondHalfInBitFormat);
473 if (bestValue < curValue) {
474 bestValue = curValue;
475 if (input.solverName == SolverNames.DP)
476 bestHalfOfCoalitionInBitFormat = firstHalfInBitFormat;
477 }
478 // Do the same for the remaining possibilities of the first and
479 // second halves
480 for (int j = 1; j < numOfPossibleSplitsBasedOnSizeOfFirstHalf[sizeOfFirstHalf]; j++) {
481 /**/
482 Combinations.getPreviousCombination(coalitionSize,
483 sizeOfFirstHalf, indicesOfMembersOfFirstHalf);
484
485 // Compute the first half (in bit format)
486 firstHalfInBitFormat = 0;
487 for (int i = 0; i < sizeOfFirstHalf; i++)
488 firstHalfInBitFormat += bit[coalitionInByteFormat[indicesOfMembersOfFirstHalf[i]
489 - 1]];
490 /**/
491 // Combinations.getPreviousCombinationInBitFormat2(numOfAgents,
492 // sizeOfFirstHalf, firstHalfInBitFormat);
493
494 // Compute the second half (in bit format)
495 secondHalfInBitFormat = (coalitionInBitFormat
496 - firstHalfInBitFormat);
497
498 // Update the functions t and f
499 curValue = get_f(firstHalfInBitFormat)
500 + get_f(secondHalfInBitFormat);
501 if (bestValue < curValue) {
502 bestValue = curValue;
503 if (input.solverName == SolverNames.DP)
504 bestHalfOfCoalitionInBitFormat = firstHalfInBitFormat;
505 }
506 }
507 }
508 // Deal with the case where the first half is the coalition itself
509 int firstHalfInBitFormat = coalitionInBitFormat;
510 curValue = get_f(firstHalfInBitFormat);
511 if (bestValue < curValue) {
512 bestValue = curValue;
513 if (input.solverName == SolverNames.DP)
514 bestHalfOfCoalitionInBitFormat = firstHalfInBitFormat;
515 }
516
517 // Update the maximum value of f for the size that is equal to
518 // "coalitionSize"
519 if (input.solverName == SolverNames.ODPIP)
520 if (result.get_max_f(coalitionSize - 1) < bestValue)
521 result.set_max_f(coalitionSize - 1, bestValue);
522
523 // Finalizing
524 set_f(coalitionInBitFormat, bestValue);
525 if (input.solverName == SolverNames.DP)
526 t[coalitionInBitFormat] = bestHalfOfCoalitionInBitFormat;
527 }
528
529 // *********************************************************************************************************
530
531 /**
532 * Given a coalition of a particular size, this method evaluates the
533 * possible splits of this coalition into two. Here, the evaluation is based
534 * on f (not v) of each of the two halves. NOTE: here, the iteration over
535 * all splits is done efficiently
536 */
537 private void evaluateSplitsEfficiently(int[] coalitionInByteFormat,
538 int coalitionSize, int numOfPossibilities) {
539 double curValue = -1;
540 double bestValue = -1;
541 int bestHalfOfCoalitionInBitFormat = -1;
542 int coalitionInBitFormat = Combinations
543 .convertCombinationFromByteToBitFormat(coalitionInByteFormat);
544
545 bestValue = input.getCoalitionValue(coalitionInBitFormat);
546 bestHalfOfCoalitionInBitFormat = coalitionInBitFormat;
547
548 // Check the possible ways of splitting the grand coalition into two
549 // (non-empty) coalitions
550 for (int firstHalfInBitFormat = coalitionInBitFormat - 1
551 & coalitionInBitFormat; /* firstHalfInBitFormat > 0 */; firstHalfInBitFormat = firstHalfInBitFormat
552 - 1 & coalitionInBitFormat) {
553 int secondHalfInBitFormat = coalitionInBitFormat
554 ^ firstHalfInBitFormat;
555
556 // Update the functions t and f
557 curValue = get_f(firstHalfInBitFormat)
558 + get_f(secondHalfInBitFormat);
559
560 if (bestValue <= curValue) {
561 bestValue = curValue;
562 if (input.solverName == SolverNames.DP) { // i.e., if we are
563 // using the t table
564 if (Integer.bitCount(firstHalfInBitFormat) > Integer
565 .bitCount(secondHalfInBitFormat))
566 bestHalfOfCoalitionInBitFormat = firstHalfInBitFormat;
567 else
568 bestHalfOfCoalitionInBitFormat = secondHalfInBitFormat;
569 }
570 }
571 if ((firstHalfInBitFormat & (firstHalfInBitFormat - 1)) == 0)
572 break;
573 }
574 // Update the maximum value of f for the size that is equal to
575 // "coalitionSize"
576 if (input.solverName == SolverNames.ODPIP)
577 if (result.get_max_f(coalitionSize - 1) < bestValue)
578 result.set_max_f(coalitionSize - 1, bestValue);
579
580 // Finalizing
581 set_f(coalitionInBitFormat, bestValue);
582 if (input.solverName == SolverNames.DP)
583 t[coalitionInBitFormat] = bestHalfOfCoalitionInBitFormat;
584 }
585
586 // *********************************************************************************************************
587
588 /**
589 * Given a non-empty coalition C \subset A\{1,2}, this method evaluates the
590 * possible splits of this coalition into two coalitions, C1 and C2
591 * (including the split {\emptyset,C}). For every such split, compute: f(C1
592 * U {1}) + f(C2 U {2}) f(C1 U {2}) + f(C2 U {1}) if( min agents in C1 < min
593 * agent in A \ (C U {1,2}) ) f(C2 U {1,2}) + f(C1) if( min agents in C2 <
594 * min agent in A \ (C U {1,2}) ) f(C1 U {1,2}) + f(C2)
595 */
596 private void evaluateSplitsOptimally(int C, int sizeOfC, int grandCoalition,
597 int numOfAgents) {
598 double bestValue = input.getCoalitionValue(C + 3); // curValue = v( C U
599 // {1,2} )
600
601 // Compute the minimum agent in: "remainingAgents", which is: A \ ( C U
602 // {1,2} )
603 int remainingAgents = grandCoalition - C - 3;
604 int minAgent = 0; // here, I put "=0" just to stop the compiler from
605 // complaining
606 for (int i = 2; i < numOfAgents; i++)
607 if ((remainingAgents & (1 << i)) != 0) { // If agent "i+1" is a
608 // member of
609 // "remainingAgents"
610 minAgent = i + 1;
611 break;
612 }
613 // set "acceptableMinAgents" to be the set of all agents from 1 to
614 // minAgent-1
615 int acceptableMinAgents = (1 << (minAgent - 1)) - 1;
616
617 // Check all splits of C into two coalitions, including the split
618 // {C,\emptyset}
619 double value;
620 for (int C1 = C & C; /* C1>0 */; C1 = C1 - 1 & C) {
621 int C2 = C - C1;
622
623 value = input.coalitionValues[C1 + 1]
624 + input.coalitionValues[C2 + 2];
625 if (bestValue < value)
626 bestValue = value;
627
628 value = input.coalitionValues[C1 + 2]
629 + input.coalitionValues[C2 + 1];
630 if (bestValue < value)
631 bestValue = value;
632
633 if ((C1 & acceptableMinAgents) != 0) {
634 value = input.coalitionValues[C1] + get_f(C2 + 3);
635 if (bestValue < value)
636 bestValue = value;
637 }
638 if ((C2 & acceptableMinAgents) != 0) {
639 value = input.coalitionValues[C2] + get_f(C1 + 3);
640 if (bestValue < value)
641 bestValue = value;
642 }
643 if ((C1 & (C1 - 1)) == 0)
644 break; // check if we have seen all splits of C into two
645 // non-empty coalitions, {C1,C2}
646 }
647 set_f(C + 3, bestValue); // set f[ C U {1,2}] = bestValue
648
649 // Update the maximum value of f for the size that is equal to "sizeOfC
650 // + 2"
651 if (input.solverName == SolverNames.ODPIP)
652 if (result.get_max_f((sizeOfC + 2) - 1) < bestValue) // we use:
653 // "sizeOfC+2"
654 // because
655 // we want:
656 // C U {1,2}
657 result.set_max_f((sizeOfC + 2) - 1, bestValue);
658 }
659
660 // `*********************************************************************************************************
661
662 /**
663 * Compute the optimal split of coalition {1,2}
664 */
665 private void evaluateSplitsOf12() {
666 int coalitionSize = 2;
667 int coalitionInBitFormat = 3;
668 int firstHalfInBitFormat = 1;
669 int secondHalfInBitFormat = 2;
670 double valueOfCoalition = input.getCoalitionValue(coalitionInBitFormat);
671 double valueOfSplit = get_f(firstHalfInBitFormat)
672 + get_f(secondHalfInBitFormat);
673 double bestValue = Math.max(valueOfCoalition, valueOfSplit);
674 set_f(coalitionInBitFormat, bestValue);
675 if (input.solverName == SolverNames.ODPIP)
676 result.set_max_f(coalitionSize - 1, bestValue);
677 }
678
679 // *********************************************************************************************************
680
681 /**
682 * Given a coalition, and given the value of the best split, find the best
683 * split, and return the first half
684 */
685 private int getBestHalf(int coalitionInBitFormat) {
686 double valueOfBestSplit = input.getCoalitionValue(coalitionInBitFormat);
687 int best_firstHalfInBitFormat = coalitionInBitFormat;
688
689 // bit[i] is the bit representing agent a_i (e.g. given 4 agents,
690 // bit[2]=2=0010, bit[3]=4=0100, etc.)
691 int[] bit = new int[input.numOfAgents + 1];
692 for (int i = 0; i < input.numOfAgents; i++)
693 bit[i + 1] = 1 << i;
694
695 // Convert the original coalition from bit format to int format
696 int[] coalitionInByteFormat = Combinations
697 .convertCombinationFromBitToByteFormat(coalitionInBitFormat,
698 input.numOfAgents);
699
700 // Check the possible ways of splitting the coalition into two
701 // (non-empty) coalitions
702 int coalitionSize = coalitionInByteFormat.length;
703 for (int sizeOfFirstHalf = (int) Math.ceil(coalitionSize
704 / (double) 2); sizeOfFirstHalf < coalitionSize; sizeOfFirstHalf++) {
705 int sizeOfSecondHalf = coalitionSize - sizeOfFirstHalf;
706
707 // Compute the number of possible splits
708 long numOfPossibleSplits;
709 if (((coalitionSize % 2) == 0)
710 && (sizeOfFirstHalf == sizeOfSecondHalf))
711 numOfPossibleSplits = Combinations.binomialCoefficient(
712 coalitionSize, sizeOfFirstHalf) / 2;
713 else
714 numOfPossibleSplits = Combinations
715 .binomialCoefficient(coalitionSize, sizeOfFirstHalf);
716
717 // Set the initial indices of the members of the first half
718 int[] indicesOfMembersOfFirstHalf = new int[sizeOfFirstHalf];
719 for (int i = 0; i < sizeOfFirstHalf; i++)
720 indicesOfMembersOfFirstHalf[i] = i + 1;
721
722 // Compute the first half (in bit format)
723 int firstHalfInBitFormat = 0;
724 for (int i = 0; i < sizeOfFirstHalf; i++)
725 firstHalfInBitFormat += bit[coalitionInByteFormat[indicesOfMembersOfFirstHalf[i]
726 - 1]];
727
728 // Compute the second half (in bit format)
729 int secondHalfInBitFormat = (coalitionInBitFormat
730 - firstHalfInBitFormat);
731
732 // Check if we have found a half that gives the value of the best
733 // split
734 if (get_f(firstHalfInBitFormat)
735 + get_f(secondHalfInBitFormat) > valueOfBestSplit) {
736 best_firstHalfInBitFormat = firstHalfInBitFormat;
737 valueOfBestSplit = get_f(firstHalfInBitFormat)
738 + get_f(secondHalfInBitFormat);
739 }
740 // Do the same for the remaining possibilities of the first and
741 // second halves
742 for (int j = 1; j < numOfPossibleSplits; j++) {
743 Combinations.getPreviousCombination(coalitionSize,
744 sizeOfFirstHalf, indicesOfMembersOfFirstHalf);
745
746 // Compute the first half (in bit format)
747 firstHalfInBitFormat = 0;
748 for (int i = 0; i < sizeOfFirstHalf; i++)
749 firstHalfInBitFormat += bit[coalitionInByteFormat[indicesOfMembersOfFirstHalf[i]
750 - 1]];
751
752 // Compute the second half (in bit format)
753 secondHalfInBitFormat = (coalitionInBitFormat
754 - firstHalfInBitFormat);
755
756 // Check if we have found a half that gives the value of the
757 // best split
758 if (get_f(firstHalfInBitFormat)
759 + get_f(secondHalfInBitFormat) > valueOfBestSplit) {
760 best_firstHalfInBitFormat = firstHalfInBitFormat;
761 valueOfBestSplit = get_f(firstHalfInBitFormat)
762 + get_f(secondHalfInBitFormat);
763 }
764 }
765 }
766 // If we haven't found any split of which the value is equal to
767 // "valueOfBestSplit", then:
768 return (best_firstHalfInBitFormat);
769 }
770
771 // ******************************************************************************************************
772
773 /**
774 * Print the percentage of coalitions, C, for which: f(C) = v(C). Should be
775 * used with DP, not IDP or ODP
776 */
777 private void printPercentageOf_v_equals_f() {
778 int numOfAgents = input.numOfAgents;
779 int totalNumOfCoalitions = 1 << numOfAgents;
780 int totalCounter = 0;
781 long[] numOfCoalitionsOfParticularSize = new long[numOfAgents + 1];
782 int[] counter = new int[numOfAgents + 1];
783 for (int i = 1; i < numOfAgents + 1; i++) {
784 counter[i] = 0;
785 numOfCoalitionsOfParticularSize[i] = Combinations
786 .binomialCoefficient(numOfAgents, i);
787 }
788 for (int i = 1; i < totalNumOfCoalitions; i++)
789 if (input.getCoalitionValue(i) == get_f(i)) {
790 counter[Integer.bitCount(i)]++;
791 totalCounter++;
792 }
793 System.out.println(
794 "percentage of all coalitions of that are optimal partitions of themselves is: "
795 + ((double) totalCounter / totalNumOfCoalitions));
796 for (int i = 2; i <= numOfAgents; i++) {
797 System.out.println(
798 "size: " + i + " percentage: " + ((double) counter[i]
799 / numOfCoalitionsOfParticularSize[i]));
800 // System.out.println(" counter = "+counter[i]);
801 // System.out.println("numOfCoalitions =
802 // "+numOfCoalitionsOfParticularSize[i]);
803 }
804 }
805
806 // ******************************************************************************************************
807
808 /**
809 * Given the f values, get the "weighted" distribution. Meaning that every
810 * f(C) value is divided by the size of C
811 */
812 private void printDistributionOfThefTable() {
813 // Initialization
814 int totalNumOfCoalitions = 1 << input.numOfAgents;
815 int[] counter = new int[40];
816 for (int i = 0; i < counter.length; i++) {
817 counter[i] = 0;
818 }
819 // get the minimum and maximum values
820 long min = Integer.MAX_VALUE;
821 long max = Integer.MIN_VALUE;
822 for (int i = 1; i < totalNumOfCoalitions; i++) {
823 long currentWeightedValue = Math
824 .round(get_f(i) / Integer.bitCount(i));
825 if (min > currentWeightedValue)
826 min = currentWeightedValue;
827 if (max < currentWeightedValue)
828 max = currentWeightedValue;
829 }
830 System.out.println("The maximum weighted f value is " + max
831 + " and the minimum one is " + min);
832
833 // get the distribution
834 for (int i = 1; i < totalNumOfCoalitions; i++) {
835 long currentWeightedValue = Math
836 .round(get_f(i) / Integer.bitCount(i));
837 int percentageOfMax = Math.round((currentWeightedValue - min)
838 * (counter.length - 1) / (max - min));
839 counter[percentageOfMax]++;
840 }
841 // Printing
842 System.out
843 .println("The distribution of the weighted coalition values:");
844 System.out.print(
845 ValueDistribution.toString(input.valueDistribution) + "_f = [");
846 for (int i = 0; i < counter.length; i++)
847 System.out.print(counter[i] + " ");
848 System.out.println("]");
849 }
850}
Note: See TracBrowser for help on using the repository browser.