source: ip/src/main/java/geniusweb/ip/ipSolver/MethodsForScanningTheInput.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: 7.8 KB
Line 
1package geniusweb.ip.ipSolver;
2
3import java.util.TreeSet;
4
5import geniusweb.ip.general.Combinations;
6import geniusweb.ip.inputOutput.Input;
7import geniusweb.ip.inputOutput.Output;
8import geniusweb.ip.mainSolver.Result;
9
10public class MethodsForScanningTheInput {
11 // This class is only used while scanning the input, and that is only if
12 // there are constraints.
13 protected static class CheckFeasibilityOfCoalitions {
14 // The data members
15 public boolean firstCoalitionIsFeasible = true;
16 public boolean firstCoalitionAsSingletonsIsFeasible = true;
17 public boolean secondCoalitionIsFeasible = true;
18 public boolean secondCoalitionAsSingletonsIsFeasible = true;
19
20 /**
21 * This method fills the data members. Here, "firstCoalition" and
22 * "secondCoalition" are provided as int arrays In more detail, this
23 * method determines whether: (1) "firstCoalition" is feasible (2)
24 * "secondCoalition" is feasible (3) the singletons that can be formed
25 * from "firstCoalition" are all feasible (4) the singletons that can be
26 * formed from "secondCoalition" are all feasible
27 */
28 public void setDataMembers(int numOfAgents, int[] firstCoalition,
29 int[] secondCoalition, TreeSet<Integer> feasibleCoalitions) {
30 // If there are no constraints to be dealt with, then do nothing
31 if (feasibleCoalitions == null)
32 return;
33 int firstCoalitionInBitFormat = Combinations
34 .convertCombinationFromByteToBitFormat(firstCoalition);
35 int secondCoalitionInBitFormat = Combinations
36 .convertCombinationFromByteToBitFormat(secondCoalition);
37 setDataMembers(numOfAgents, firstCoalitionInBitFormat,
38 secondCoalitionInBitFormat, feasibleCoalitions);
39 }
40
41 /**
42 * This method fills the data members. Here, "firstCoalition" and
43 * "secondCoalition" are provided in bit format (i.e., as masks) In more
44 * detail, this method determines whether: (1) "firstCoalition" is
45 * feasible (2) "secondCoalition" is feasible (3) the singletons that
46 * can be formed from "firstCoalition" are all feasible (4) the
47 * singletons that can be formed from "secondCoalition" are all feasible
48 */
49 public void setDataMembers(int numOfAgents, int firstCoalition,
50 int secondCoalition, TreeSet<Integer> feasibleCoalitions) {
51 // If there are no constraints to be dealt with, then do nothing
52 if (feasibleCoalitions == null)
53 return;
54
55 firstCoalitionIsFeasible = feasibleCoalitions
56 .contains(new Integer(firstCoalition));
57 secondCoalitionIsFeasible = feasibleCoalitions
58 .contains(new Integer(secondCoalition));
59
60 firstCoalitionAsSingletonsIsFeasible = true;
61 for (int i = 0; i < numOfAgents; i++) {
62 if ((firstCoalition & (1 << i)) != 0) { // If agent "i+1" is a
63 // member of
64 // "firstCoalition"
65 if (feasibleCoalitions
66 .contains(new Integer((1 << i))) == false) {
67 firstCoalitionAsSingletonsIsFeasible = false;
68 break;
69 }
70 }
71 }
72 secondCoalitionAsSingletonsIsFeasible = true;
73 for (int i = 0; i < numOfAgents; i++) {
74 if ((secondCoalition & (1 << i)) != 0) { // If agent "i+1" is a
75 // member of
76 // "secondCoalition"
77 if (feasibleCoalitions
78 .contains(new Integer((1 << i))) == false) {
79 secondCoalitionAsSingletonsIsFeasible = false;
80 break;
81 }
82 }
83 }
84 }
85 }
86
87 // ******************************************************************************************************
88
89 /**
90 * (1) Calculates the average of all the values of sizes
91 * s=1,...,numOfAgents. (2) Searches the second level of the sie graph
92 */
93 public static void scanTheInputAndComputeAverage(Input input, Output output,
94 Result result, double[] avgValueForEachSize) {
95 // initialization
96 long startTime = System.currentTimeMillis();
97 int numOfAgents = input.numOfAgents;
98 int totalNumOfCoalitions = (int) Math.pow(2, numOfAgents);
99 double bestValue = result.get_ipValueOfBestCSFound();
100 int bestCoalition1 = 0;
101 int bestCoalition2 = 0;
102 double[] sumOfValues = new double[numOfAgents];
103 for (int size = 1; size <= numOfAgents; size++)
104 sumOfValues[size - 1] = 0;
105
106 // Initialize the variables that are only used if there are constraints
107 boolean coalition1IsFeasible = true;
108 boolean coalition2IsFeasible = true;
109 final boolean constraintsExist;
110 if (input.feasibleCoalitions == null)
111 constraintsExist = false;
112 else
113 constraintsExist = true;
114
115 for (int coalition1 = totalNumOfCoalitions
116 / 2; coalition1 < totalNumOfCoalitions - 1; coalition1++) {
117 int sizeOfCoalition1 = Combinations
118 .getSizeOfCombinationInBitFormat(coalition1, numOfAgents);
119
120 int coalition2 = totalNumOfCoalitions - 1 - coalition1;
121 int sizeOfCoalition2 = numOfAgents - sizeOfCoalition1;
122
123 sumOfValues[sizeOfCoalition1 - 1] += input
124 .getCoalitionValue(coalition1);
125 sumOfValues[sizeOfCoalition2 - 1] += input
126 .getCoalitionValue(coalition2);
127
128 // Check whether "coalition1" is feasible and whether "coalition2"
129 // is feasible
130 if (constraintsExist) {
131 coalition1IsFeasible = input.feasibleCoalitions
132 .contains(new Integer(coalition1));
133 coalition2IsFeasible = input.feasibleCoalitions
134 .contains(new Integer(coalition2));
135 }
136 // Compute the value of the current pair of coalitions
137 double value = 0;
138 if ((constraintsExist == false)
139 || ((coalition1IsFeasible) && (coalition2IsFeasible))) {
140 value = input.getCoalitionValue(coalition1)
141 + input.getCoalitionValue(coalition2);
142 }
143 // if this value is greater than best_value, then update
144 // best_value...
145 if (bestValue < value) {
146 bestCoalition1 = coalition1;
147 bestCoalition2 = coalition2;
148 bestValue = value;
149 }
150 }
151
152 // If this search has improved the value of the best CS found...
153 if (bestValue > result.get_ipValueOfBestCSFound()) {
154 int[][] bestCS = new int[2][];
155 bestCS[0] = Combinations.convertCombinationFromBitToByteFormat(
156 bestCoalition1, numOfAgents);
157 bestCS[1] = Combinations.convertCombinationFromBitToByteFormat(
158 bestCoalition2, numOfAgents);
159 result.updateIPSolution(bestCS, bestValue);
160 }
161 output.printCurrentResultsOfIPToStringBuffer_ifPrevResultsAreDifferent(
162 input, result);
163
164 // For every coalition size, calculate the average coalition value
165 for (int size = 1; size <= numOfAgents; size++)
166 avgValueForEachSize[size - 1] = sumOfValues[size - 1]
167 / Combinations.binomialCoefficient(numOfAgents, size);
168
169 // Update the number of coalitions, and coalition structures, that were
170 // searched after scanning the input
171 updateNumOfSearchedAndRemainingCoalitionsAndCoalitionStructures(input,
172 result);
173
174 // Calculate the time required to scan the input
175 result.ipTimeForScanningTheInput = System.currentTimeMillis()
176 - startTime;
177 }
178
179 // ******************************************************************************************************
180
181 /**
182 * Update the number of coalitions, and coalition structures, that were
183 * searched after scanning the input
184 */
185 private static void updateNumOfSearchedAndRemainingCoalitionsAndCoalitionStructures(
186 Input input, Result result) {
187 for (int size1 = 1; size1 <= Math
188 .floor(input.numOfAgents / (double) 2); size1++) {
189 // From size1, calculate size2 (e.g., for 7 agents, if size1=1 then
190 // size2=6, and if size1=2 then size2=5)
191 int size2 = input.numOfAgents - size1;
192
193 // Compute the No. of coalitions of size "size1" (p.s., this is the
194 // same as the No. of coalitions of size "size2")
195 int numOfCombinationsOfSize1 = (int) Combinations
196 .binomialCoefficient(input.numOfAgents, size1);
197
198 // Compute the number of coalitions of size "size1" that IP scanned
199 // (p.s., this is the same as the number of coalitions of size
200 // "size2" that IP scanned)
201 int temp;
202 if (size1 != size2)
203 temp = numOfCombinationsOfSize1;
204 else
205 temp = (numOfCombinationsOfSize1 / 2);
206
207 result.ipNumOfExpansions += 2 * temp;
208 ;
209 }
210 }
211}
Note: See TracBrowser for help on using the repository browser.