/*
* Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
*/
package com.koalog.jcs.examples;
import org.apache.log4j.PropertyConfigurator;
import com.koalog.jcs.variable.BooleanVariable;
import com.koalog.jcs.solver.DefaultSplitSolver;
import com.koalog.jcs.constraint.BaseProblem;
import com.koalog.jcs.constraint.arithmetic.Hyperplan;
import com.koalog.jcs.constraint.arithmetic.Exactly;
/**
* This is a partition problem.
* Given the set S = {1, 2, ..., n},
* it consists in finding two sets A and B such that:
* <ul>
* <li>A U B = S,</li>
* <li>|A| = |B|,</li>
* <li>sum(A) = sum(B),</li>
* <li>sum_squares(A) = sum_squares(B).</li>
* </ul>
*
* @author Yan Georget
*/
public class PartitionProblem extends BaseProblem {
//------------------------------------------------------------------------
// CONSTRUCTORS
//------------------------------------------------------------------------
/**
* Sole constructor.
* @param n the size of the problem
*/
public PartitionProblem(int n) {
super();
int[] s = new int[n];
int[] ss = new int[n];
// b[i] <=> i+1 is in set A
BooleanVariable[] b = new BooleanVariable[n];
for (int i=0; i<n; i++) {
s[i] = i+1;
ss[i] = s[i]*s[i];
b[i] = new BooleanVariable("_" + s[i]);
}
add(new Exactly(n/2, b, 1));
add(new Hyperplan(s, b, n*(n+1)/4));
add(new Hyperplan(ss, b, n*(n+1)*(2*n+1)/12));
setVariables(b);
}
//------------------------------------------------------------------------
// STATIC METHODS
//------------------------------------------------------------------------
/**
* Runs the problem.
* @param args the command line arguments:
* args[0] must contain a log4j properties file location
*/
public static void main(String[] args) {
PropertyConfigurator.configure(args[0]);
new DefaultSplitSolver(new PartitionProblem(8)).solve(1);
}
}
|