[39] | 1 | package geniusweb.ip.ipSolver;
|
---|
| 2 |
|
---|
| 3 | import java.util.TreeSet;
|
---|
| 4 |
|
---|
| 5 | import geniusweb.ip.general.Combinations;
|
---|
| 6 | import geniusweb.ip.inputOutput.Input;
|
---|
| 7 | import geniusweb.ip.inputOutput.Output;
|
---|
| 8 | import geniusweb.ip.mainSolver.Result;
|
---|
| 9 |
|
---|
| 10 | public 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 | } |
---|