Courses/CS 460/Fall 2006/Strom, Richard/Partition/PartitionStress

From CSWiki

Run the partition problem on sets of various size. Each set contains an odd number of 1's. So there is no solution. This is an experiment to see how the time of the run increases with set size.

[edit] Code

//Partition using constraints

package ExamplesJaCoP;

import java.util.ArrayList;
import java.util.Random;
import JaCoP.*;

public class PartitionStress {

  public static int setSize;
  public static Random generator;
  public static int[] set;
  public static FDV[] selectors;
  public static FDV difference;
  public static FDstore store;
  public static ArrayList<FDV> 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++) {
      FDV fdv =  new FDV( store, "Selector-" + i, -1, -1 ); 
      fdv.addDom(1, 1);
      fdvList.add(fdv);
      selectors[i] = fdv;
    }
    difference = new FDV(store, "Difference", 0, setSize);
    // Distribute -1 and 1 among the selectors so that the weighted sum is 0.
    store.impose ( new SumWeight(selectors, set, difference ) );
  }

  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].value() == k) System.out.print(set[i] + " ");
      }
      System.out.println();
    }
  }

  private static void runTrial() {
    fdvList = new ArrayList<FDV>();
    selectors = new FDV[setSize];
    store = new FDstore();

    buildSet();
    generateConstraints();

    Search search = new Search();
    search.setPrintInfo(false);

    long t1 = System.currentTimeMillis();
    // Run branch and bound minimization search. 
    // Minimize difference (absolute value).
    search.labeling(store, 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

The output shows the set size (number of elements), time (in ms), and for comparison 2^(setsize - 9), which turned out to be an order of magnitute fit.

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

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

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

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

Set size: 25; 52 sec. 2^(25-9)/1000 = 65.536

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

Set size: 33; 3 hr. 2^(33-9)/3600000 = 4.6603377777777775