source: ip/src/main/java/geniusweb/ip/inputOutput/Input.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: 21.0 KB
Line 
1package geniusweb.ip.inputOutput;
2
3import java.io.BufferedReader;
4import java.io.FileReader;
5import java.util.Random;
6import java.util.TreeSet;
7
8import org.apache.commons.math.MathException;
9import org.apache.commons.math.distribution.BetaDistributionImpl;
10import org.apache.commons.math.distribution.ExponentialDistributionImpl;
11import org.apache.commons.math.distribution.GammaDistributionImpl;
12
13import geniusweb.ip.general.Combinations;
14import geniusweb.ip.general.General;
15import geniusweb.ip.general.RandomPartition;
16
17public class Input {
18 // The parameters that can only be set here (i.e., not through the GUI):
19 public final boolean printPercentageOf_v_equals_f = false; // only relevant
20 // when using
21 // dynamic
22 // programming.
23 // The
24 // percentage of
25 // coalitions
26 // whose value
27 // equals their
28 // best
29 // partition
30 public final boolean printDistributionOfThefTable = false; // only relevant
31 // when using
32 // dynamic
33 // programming.
34 // The
35 // distribution
36 // of the f
37 // table
38 public final boolean printCoalitionValueDistribution = false; // the
39 // distribution
40 // of the
41 // coalition
42 // values
43 public final boolean printCoalitionStructureValueDistribution = false; // the
44 // distribution
45 // of
46 // the
47 // coalition
48 // structure
49 // values
50 // (based
51 // on
52 // a
53 // sample
54 // of
55 // coalition
56 // structures)
57 public final boolean printTheSubspaceThatIsCurrentlyBeingSearched = false; // only
58 // relevant
59 // when
60 // running
61 // IP
62 // or
63 // ODP-IP
64 public final boolean printTheCoalitionsWhenPrintingTheirValues = true;
65 public final boolean pruneSubspaces = true; // only relevant when running IP
66 // or ODP-IP. Determines whether
67 // IP is allowed to prune entire
68 // subspaces based on their
69 // bounds.
70 public final boolean useBranchAndBound = true; // only relevant when running
71 // IP or ODP-IP
72 public final boolean useSamplingWhenSearchingSubspaces = false; // only
73 // relevant
74 // when
75 // running
76 // IP or
77 // ODP-IP.
78 public final boolean samplingDoneInGreedyFashion = false;
79 private final double sigma = 0.1; // relevant to the following
80 // distributions: "Normal", "Modified
81 // Normal", and "Agent-based Normal"
82 public final boolean useEfficientImplementationOfIDP = true; // if "true",
83 // IDP
84 // evaluates
85 // more
86 // splits,
87 // but this
88 // allows
89 // for a
90 // more
91 // efficient
92 // implementation
93 // and a
94 // shorter
95 // runtime.
96
97 public SolverNames solverName;
98 public boolean readCoalitionValuesFromFile;
99 public boolean storeCoalitionValuesInFile;
100
101 // The IP parameters
102 public boolean orderIntegerPartitionsAscendingly; // setting this to false
103 // means integers will
104 // be ordered
105 // descendingly
106 public double acceptableRatio; // only relevant when running IP or ODP-IP
107
108 // The printing parameters
109 public boolean printDetailsOfSubspaces; // only relevant when running IP or
110 // ODP-IP
111 public boolean printNumOfIntegerPartitionsWithRepeatedParts;
112 public boolean printInterimResultsOfIPToFiles; // only relevant when running
113 // IP or ODP-IP
114 public boolean printTimeTakenByIPForEachSubspace; // only relevant when
115 // running IP or ODP-IP
116
117 // General parameters
118 public TreeSet<Integer> feasibleCoalitions;
119 public int numOfAgents;
120 public long numOfRunningTimes;
121 public double[] coalitionValues;
122 public String outputFolder;
123 public ValueDistribution valueDistribution;
124 public String folderInWhichCoalitionValuesAreStored = "D:/CSGtemp/coalitionValues"; // this
125 // is
126 // the
127 // default
128 // setting,
129 // unless
130 // it
131 // is
132 // modified
133 // by
134 // another
135 // method
136
137 public String problemID = ""; // This is the ID of the problem instance
138 // (useful when taking average over multiple
139 // instances)
140
141 // ******************************************************************************************************
142
143 /**
144 * @param numOfAgents the number of agents
145 * @param coalitionValues. Should be double[] of size 2^numOfAgents
146 * @param acceptableRatio usually 100 (%)
147 */
148 public Input(int numOfAgents, double[] coalitionValues,
149 double acceptableRatio) {
150 this.numOfAgents = numOfAgents;
151 this.coalitionValues = coalitionValues;
152 this.acceptableRatio = acceptableRatio;
153 feasibleCoalitions = null; // this is only needed for a constraint
154 // solver. Just ignore it.
155 numOfRunningTimes = 1; // Setting this to 1 means we are not taking an
156 // average over multiple run with different
157 // problem instaces.
158 storeCoalitionValuesInFile = false; // Setting this to false means we
159 // won't be storing the coalition
160 // values after solving the problem
161 printDetailsOfSubspaces = false;
162 valueDistribution = ValueDistribution.UNKNOWN;
163 }
164
165 // ******************************************************************************************************
166
167 /**
168 * Return the value of a coalition where every member is represented by an
169 * bit
170 */
171 public double getCoalitionValue(int coalitionInBitFormat) {
172 return (coalitionValues[coalitionInBitFormat]);
173 }
174
175 /**
176 * Return the value of a coalition where every member is represented by an
177 * integer
178 */
179 public double getCoalitionValue(int[] coalitionInByteFormat) {
180 int coalitionInBitFormat = Combinations
181 .convertCombinationFromByteToBitFormat(coalitionInByteFormat);
182 return (getCoalitionValue(coalitionInBitFormat));
183 }
184
185 /**
186 * Return the value of a given coalition structure CS, where each coalition
187 * member is represented using an integer
188 */
189 public double getCoalitionStructureValue(int[][] coalitionStructure) {
190 double valueOfCS = 0;
191 for (int i = 0; i < coalitionStructure.length; i++)
192 valueOfCS += getCoalitionValue(coalitionStructure[i]);
193 return (valueOfCS);
194 }
195
196 /**
197 * Return the value of a given coalition structure CS, where each coalition
198 * member is represented using a bit
199 */
200 public double getCoalitionStructureValue(int[] coalitionStructure) {
201 double valueOfCS = 0;
202 for (int i = 0; i < coalitionStructure.length; i++)
203 valueOfCS += getCoalitionValue(coalitionStructure[i]);
204 return (valueOfCS);
205 }
206
207 // *****************************************************************************************************
208
209 /**
210 * This method sets the values of the coalitions of a particular size.
211 */
212 public void generateCoalitionValues() {
213 // initialization
214 Random random = new Random();
215 long time = System.currentTimeMillis();
216 coalitionValues = new double[(int) Math.pow(2, numOfAgents)];
217 coalitionValues[0] = 0; // just in case, set the value of the empty set
218 // to 0
219
220 // Give random strengths to the agents. This is only used in
221 // "agent-Based" distributions
222 double[] agentStrength_normal = new double[numOfAgents];
223 double[] agentStrength_uniform = new double[numOfAgents];
224 for (int agent = 1; agent <= numOfAgents; agent++) {
225 agentStrength_normal[agent - 1] = Math.max(0, General
226 .getRandomNumberFromNormalDistribution(10, sigma, random));
227 agentStrength_uniform[agent - 1] = random.nextDouble() * 10;
228 }
229 // Uniform distribution
230 if (valueDistribution == ValueDistribution.UNIFORM)
231 for (int coalition = coalitionValues.length
232 - 1; coalition > 0; coalition--)
233 coalitionValues[coalition] = Math.round(
234 (Integer.bitCount(coalition) * random.nextDouble())
235 * 100000000);
236
237 // Normal distribution
238 if (valueDistribution == ValueDistribution.NORMAL)
239 for (int coalition = coalitionValues.length
240 - 1; coalition > 0; coalition--) {
241 coalitionValues[coalition] = Math.max(0,
242 Integer.bitCount(coalition)
243 * General.getRandomNumberFromNormalDistribution(
244 10, sigma, random));
245 coalitionValues[coalition] = Math
246 .round(coalitionValues[coalition] * 100000000);
247 }
248 // Modified Uniform distribution
249 if (valueDistribution == ValueDistribution.MODIFIEDUNIFORM)
250 for (int coalition = coalitionValues.length
251 - 1; coalition > 0; coalition--) {
252 coalitionValues[coalition] = random.nextDouble() * 10
253 * Integer.bitCount(coalition);
254 int probability = random.nextInt(100);
255 if (probability <= 20)
256 coalitionValues[coalition] += random.nextDouble() * 50;
257 coalitionValues[coalition] = Math
258 .round(coalitionValues[coalition] * 100000000);
259 }
260 // Modified Normal distribution
261 if (valueDistribution == ValueDistribution.MODIFIEDNORMAL)
262 for (int coalition = coalitionValues.length
263 - 1; coalition > 0; coalition--) {
264 coalitionValues[coalition] = Math.max(0,
265 Integer.bitCount(coalition)
266 * General.getRandomNumberFromNormalDistribution(
267 10, sigma, random));
268 int probability = random.nextInt(100);
269 // if(probability <=20) valuesOfCurSize[index] += r.nextDouble()
270 // * 50;
271 if (probability <= 20)
272 coalitionValues[coalition] += General
273 .getRandomNumberFromNormalDistribution(25, sigma,
274 random);
275 coalitionValues[coalition] = Math
276 .round(coalitionValues[coalition] * 100000000);
277 }
278 // Exponential distribution
279 if (valueDistribution == ValueDistribution.EXPONENTIAL) {
280 ExponentialDistributionImpl exponentialDistributionImpl = new ExponentialDistributionImpl(
281 1); // the mean of an exponential distribution is 1/lambda.
282 for (int coalition = coalitionValues.length
283 - 1; coalition > 0; coalition--) {
284 boolean repeat = false;
285 do {
286 try {
287 coalitionValues[coalition] = Math.max(0,
288 Integer.bitCount(coalition)
289 * exponentialDistributionImpl.sample());
290 } catch (MathException e) {
291 repeat = true;
292 }
293 } while (repeat == true);
294 coalitionValues[coalition] = Math
295 .round(coalitionValues[coalition] * 100000000);
296 }
297 }
298 // Beta distribution
299 if (valueDistribution == ValueDistribution.BETA) {
300 BetaDistributionImpl betaDistributionImpl = new BetaDistributionImpl(
301 0.5, 0.5);
302 for (int coalition = coalitionValues.length
303 - 1; coalition > 0; coalition--) {
304 boolean repeat = false;
305 do {
306 try {
307 coalitionValues[coalition] = Math.max(0,
308 Integer.bitCount(coalition)
309 * betaDistributionImpl.sample());
310 } catch (MathException e) {
311 repeat = true;
312 }
313 } while (repeat == true);
314 coalitionValues[coalition] = Math
315 .round(coalitionValues[coalition] * 100000000);
316 }
317 }
318 // Gamma distribution
319 if (valueDistribution == ValueDistribution.GAMMA) {
320 GammaDistributionImpl gammaDistributionImpl = new GammaDistributionImpl(
321 2, 2);
322 for (int coalition = coalitionValues.length
323 - 1; coalition > 0; coalition--) {
324 boolean repeat = false;
325 do {
326 try {
327 coalitionValues[coalition] = Math.max(0,
328 Integer.bitCount(coalition)
329 * gammaDistributionImpl.sample());
330 } catch (MathException e) {
331 repeat = true;
332 }
333 } while (repeat == true);
334 coalitionValues[coalition] = Math
335 .round(coalitionValues[coalition] * 100000000);
336 }
337 }
338 // Agent-based Uniform distribution
339 if (valueDistribution == ValueDistribution.AGENTBASEDUNIFORM)
340 for (int coalition = coalitionValues.length
341 - 1; coalition > 0; coalition--) {
342 int[] members = Combinations
343 .convertCombinationFromBitToByteFormat(coalition,
344 numOfAgents);
345
346 // if percentage is, say 60%, then an agent's value can go up by
347 // at most 60%, and down by at most 60%
348 double percentage = 100;
349 coalitionValues[coalition] = 0;
350 for (int m = 0; m < Integer.bitCount(coalition); m++) {
351 double rangeSize = (percentage / 100)
352 * agentStrength_uniform[members[m] - 1] * 2;
353 double startOfRange = ((100 - percentage) / 100)
354 * agentStrength_uniform[members[m] - 1];
355 coalitionValues[coalition] += startOfRange
356 + (random.nextDouble() * rangeSize);
357 }
358 coalitionValues[coalition] = Math
359 .round(coalitionValues[coalition] * 100000000);
360 }
361 // Agent-based Normal distribution
362 if (valueDistribution == ValueDistribution.AGENTBASEDNORMAL)
363 for (int coalition = coalitionValues.length
364 - 1; coalition > 0; coalition--) {
365 int[] members = Combinations
366 .convertCombinationFromBitToByteFormat(coalition,
367 numOfAgents);
368 coalitionValues[coalition] = 0;
369 for (int m = 0; m < Integer.bitCount(coalition); m++) {
370 double newValue;
371 newValue = General.getRandomNumberFromNormalDistribution(
372 agentStrength_normal[members[m] - 1], sigma,
373 random);
374 coalitionValues[coalition] += Math.max(0, newValue);
375 }
376 coalitionValues[coalition] = Math
377 .round(coalitionValues[coalition] * 100000000);
378 }
379 // NDCS distribution
380 if (valueDistribution == ValueDistribution.NDCS)
381 for (int coalition = coalitionValues.length
382 - 1; coalition > 0; coalition--) {
383 do {
384 coalitionValues[coalition] = (General
385 .getRandomNumberFromNormalDistribution(
386 Integer.bitCount(coalition),
387 Math.sqrt(Integer.bitCount(coalition)),
388 random));
389 } while (coalitionValues[coalition] <= 0);
390 coalitionValues[coalition] = Math
391 .round(coalitionValues[coalition] * 100000000);
392 }
393
394 System.out.println(numOfAgents + " agents, "
395 + ValueDistribution.toString(valueDistribution)
396 + " distribution. The time required to generate the coalition values (in milli second): "
397 + (System.currentTimeMillis() - time));
398
399 // get the coalition value distribution
400 if (printCoalitionValueDistribution)
401 printCoalitionValueDistribution();
402
403 // get the coalition structure value distribution
404 if (printCoalitionStructureValueDistribution)
405 printCoalitionStructureValueDistribution(numOfAgents);
406 }
407
408 // ******************************************************************************************************
409
410 /**
411 * Store the coalition values in a file
412 */
413 public void storeCoalitionValuesInFile(int problemID) {
414 // Create the output folder
415 General.createFolder(folderInWhichCoalitionValuesAreStored);
416
417 // Set the name of the output file, and empty it
418 String filePathAndName = folderInWhichCoalitionValuesAreStored;
419 filePathAndName += "/" + numOfAgents + "Agents_"
420 + ValueDistribution.toString(valueDistribution) + "_"
421 + problemID + ".txt";
422 General.clearFile(filePathAndName);
423
424 // Print the coalition values to a string buffer
425 StringBuffer tempStringBuffer = new StringBuffer();
426 for (int coalition = 0; coalition < coalitionValues.length; coalition++)
427 tempStringBuffer.append(coalitionValues[coalition] + "\n");
428
429 // empty the contents of the string buffer into the output file
430 General.printToFile(filePathAndName, tempStringBuffer.toString(),
431 false);
432 tempStringBuffer.setLength(0);
433 }
434
435 // *****************************************************************************************************
436
437 /**
438 * Read the coalition values from a file
439 */
440 public void readCoalitionValuesFromFile(int problemID) {
441 coalitionValues = new double[(int) Math.pow(2, numOfAgents)];
442
443 // Set the name and path of the file from which we will read the
444 // coalition values
445 String filePathAndName = folderInWhichCoalitionValuesAreStored;
446 filePathAndName += "/" + numOfAgents + "Agents_"
447 + ValueDistribution.toString(valueDistribution) + "_"
448 + problemID + ".txt";
449 try {
450 BufferedReader bufferedReader = new BufferedReader(
451 new FileReader(filePathAndName));
452 for (int coalition = 0; coalition < coalitionValues.length; coalition++)
453 coalitionValues[coalition] = (new Double(
454 bufferedReader.readLine())).doubleValue();
455
456 bufferedReader.close();
457 } catch (Exception e) {
458 System.out.println(e);
459 }
460 }
461
462 // ******************************************************************************************************
463
464 /**
465 * Read the coalition values from a file
466 */
467 public void readCoalitionValuesFromFile(String fileName) {
468 coalitionValues = new double[(int) Math.pow(2, numOfAgents)];
469
470 // Set the name and path of the file from which we will read the
471 // coalition values
472 // String filePathAndName = folderInWhichCoalitionValuesAreStored;
473 String filePathAndName = fileName;
474 try {
475 BufferedReader bufferedReader = new BufferedReader(
476 new FileReader(filePathAndName));
477 for (int coalition = 0; coalition < coalitionValues.length; coalition++)
478 coalitionValues[coalition] = (new Double(
479 bufferedReader.readLine())).doubleValue();
480
481 bufferedReader.close();
482 } catch (Exception e) {
483 System.out.println(e);
484 }
485 }
486
487 // ******************************************************************************************************
488
489 /**
490 * Given the coalition values, print the "weighted" distribution (i.e.,
491 * where every coalition value is divided by the size of that coalition).
492 */
493 public void printCoalitionValueDistribution() {
494 // Initialization
495 int[] counter = new int[40];
496 for (int i = 0; i < counter.length; i++) {
497 counter[i] = 0;
498 }
499 // get the minimum and maximum values
500 long min = Integer.MAX_VALUE;
501 long max = Integer.MIN_VALUE;
502 for (int coalition = 1; coalition < coalitionValues.length; coalition++) {
503 long currentWeightedValue = Math.round(
504 coalitionValues[coalition] / Integer.bitCount(coalition));
505 if (min > currentWeightedValue)
506 min = currentWeightedValue;
507 if (max < currentWeightedValue)
508 max = currentWeightedValue;
509 }
510 System.out.println(
511 "The maximum weighted coalition value (i.e., value of coalition divided by size of that coalition) is "
512 + max + " and the minimum one is " + min);
513
514 // get the distribution
515 for (int coalition = 1; coalition < coalitionValues.length; coalition++) {
516 long currentWeightedValue = Math.round(
517 coalitionValues[coalition] / Integer.bitCount(coalition));
518 int percentageOfMax = Math.round((currentWeightedValue - min)
519 * (counter.length - 1) / (max - min));
520 counter[percentageOfMax]++;
521 }
522 // Printing
523 System.out.println(
524 "The distribution of the weighted coalition values (i.e., every value of coalition is divided by size of that coalition) is:");
525 System.out.print(ValueDistribution.toString(valueDistribution)
526 + "_coalition = [");
527 for (int i = 0; i < counter.length; i++)
528 System.out.print(counter[i] + " ");
529 System.out.println("]");
530 }
531
532 // ******************************************************************************************************
533
534 /**
535 * Given the coalition values, print the "weighted" distribution (i.e.,
536 * where every coalition value is divided by the size of that coalition).
537 */
538 public void printCoalitionStructureValueDistribution(int n) {
539 RandomPartition randomPartition = new RandomPartition(n);
540 int numOfSamples = 10000000;
541 long[] sampleValues = new long[numOfSamples];
542 for (int i = 0; i < numOfSamples; i++) {
543 int[] currentCoalitionStructure = randomPartition.get();
544 long value = 0;
545 for (int j = 0; j < currentCoalitionStructure.length; j++)
546 value += coalitionValues[currentCoalitionStructure[j]];
547 // value /= currentCoalitionStructure.length;
548 sampleValues[i] = value;
549 }
550 // Initialization
551 int[] counter = new int[200];
552 for (int i = 0; i < counter.length; i++) {
553 counter[i] = 0;
554 }
555 // get the minimum and maximum values
556 long min = Integer.MAX_VALUE;
557 long max = Integer.MIN_VALUE;
558 for (int i = 1; i < sampleValues.length; i++) {
559 long currentValue = sampleValues[i];
560 if (min > currentValue)
561 min = currentValue;
562 if (max < currentValue)
563 max = currentValue;
564 }
565 System.out.println(
566 "The maximum weighted coalition value (i.e., value of coalition divided by size of that coalition) is "
567 + max + " and the minimum one is " + min);
568
569 // get the distribution
570 for (int i = 1; i < sampleValues.length; i++) {
571 long currentValue = sampleValues[i];
572 int percentageOfMax = Math.round(
573 (currentValue - min) * (counter.length - 1) / (max - min));
574 counter[percentageOfMax]++;
575 }
576 // Printing
577 System.out.println(
578 "The distribution of the weighted coalition STRUCTURE values (i.e., every value of coalition is divided by size of that coalition) is:");
579 System.out.print(ValueDistribution.toString(valueDistribution)
580 + "_structure = [");
581 for (int i = 0; i < counter.length; i++)
582 System.out.print(counter[i] + " ");
583 System.out.println("]");
584 }
585}
Note: See TracBrowser for help on using the repository browser.