[33] | 1 | package geniusweb.ip.ipSolver;
|
---|
| 2 |
|
---|
| 3 | import java.util.Arrays;
|
---|
| 4 | import java.util.TreeSet;
|
---|
| 5 |
|
---|
| 6 | import geniusweb.ip.general.Combinations;
|
---|
| 7 | import geniusweb.ip.general.General;
|
---|
| 8 | import geniusweb.ip.general.RandomPermutation;
|
---|
| 9 | import geniusweb.ip.general.RandomSubsetOfGivenSet;
|
---|
| 10 | import geniusweb.ip.inputOutput.Input;
|
---|
| 11 | import geniusweb.ip.inputOutput.Output;
|
---|
| 12 | import geniusweb.ip.inputOutput.SolverNames;
|
---|
| 13 | import geniusweb.ip.mainSolver.Result;
|
---|
| 14 |
|
---|
| 15 | public 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 | } |
---|