Courses/CS 460/Fall 2006/Strom, Richard/Choco

From CSWiki

This is the same problem as run in JaCoP. There is a difference in strategy. In JaCoP it was run as a minimization problem. In Choco it is being run as a strait constraint problem.

[edit] Code

//Partition using constraints

package examples;

import java.util.ArrayList;
import java.util.Random;

import choco.Problem;
import choco.integer.IntDomainVar;

public class PartitionStress {

  public static int setSize;
  public static Random generator;
  public static int[] set;
  public static IntDomainVar[] selectors;
  public static Problem prob;
  public static ArrayList<IntDomainVar> fdvList;
  public static long totalFailureTime = 0;

  public static void main(String[] args) {
    // Init random generator
    generator = new Random(System.currentTimeMillis());
    // Run the trials.
    for (setSize = 9; setSize < 40; setSize += 4) runTrial();
  }

  public static void generateConstraints() {
    // Create an FDV selector for each element in the set. 
    // It's value may be either -1 or 1.
    for (int i = 0; i < setSize; i++) {
      selectors[i] =  prob.makeEnumIntVar("selectors[" + i + "]", -1, 1 ); 
      prob.post(prob.neq(0, selectors[i]));
    }
    // Distribute -1 and 1 among the selectors so that the weighted sum is 0.
    prob.post(prob.eq(0, prob.scalar(set, selectors)));
  }

  public static void buildSet() {
    set = new int[setSize];
    for (int i = 0; i < setSize; i++) set[i] = 1;
  }

  public static void outputSet() {
    System.out.print("Set:   ");
    for (int i = 0; i < setSize; i++) {
      System.out.print(set[i] + (i < setSize - 1 ? " " : "\n"));
    }
  }

  public static void outputSolution() {
    for (int k: new int[] {-1, 1}) {
      System.out.print("Set " + (k == -1 ? 1 : 2) + ": ");
      for (int i = 0; i < setSize; i++) {
        if (selectors[i].getVal() == k) System.out.print(set[i] + " ");
      }
      System.out.println();
    }
  }

  private static void runTrial() {
    fdvList = new ArrayList<IntDomainVar>();
    selectors = new IntDomainVar[setSize];
    prob = new Problem();

    buildSet();
    generateConstraints();

    long t1 = System.currentTimeMillis();
    // Run branch and bound minimization search. 
    // Minimize difference (absolute value).
    prob.solve(); //  prob, fdvList, difference, new IndomainMin(), new Delete()); 
    long time = System.currentTimeMillis() - t1;
    
    totalFailureTime += time;
    System.out.print("\nSet size: " + setSize + "; ");
    if (time < 1000) {
      System.out.println(time + " ms. 2^(" + setSize + "-9) = " + Math.pow(2, setSize-9));
      return;
    }
    int divisor = 1000;
    time /= 1000;
    if (time < 60) {
      System.out.println(time + " sec. 2^(" + setSize + "-9)/" + divisor + 
                         " = " + Math.pow(2, setSize-9)/divisor);
      return;
    }
    divisor *= 60;
    time /= 60;
    if (time < 60) {
      System.out.println(time + " min. 2^(" + setSize + "-9)/" + divisor + 
                         " = " + Math.pow(2, setSize-9)/divisor);
      return;
    }
    divisor *= 60;
    time /= 60;
    System.out.println(time + " hr. 2^(" + setSize + "-9)/" + divisor + 
                       " = " + Math.pow(2, setSize-9)/divisor);

  }

}

[edit] Output

Set size: 9; 31 ms. 2^(9-9) = 1.0

Set size: 13; 141 ms. 2^(13-9) = 16.0

Set size: 17; 703 ms. 2^(17-9) = 256.0

Set size: 21; 11 sec. 2^(21-9)/1000 = 4.096

Set size: 25; 3 min. 2^(25-9)/60000 = 1.0922666666666667

Set size: 29; 52 min. 2^(29-9)/60000 = 17.476266666666668