/*
* Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
*/
package com.koalog.jcs.examples;
import java.util.List;
import java.util.ArrayList;
import org.apache.log4j.PropertyConfigurator;
import com.koalog.jcs.variable.IntegerVariable;
import com.koalog.jcs.constraint.BaseProblem;
import com.koalog.jcs.constraint.arithmetic.AllDifferent;
import com.koalog.jcs.constraint.arithmetic.Add;
import com.koalog.jcs.constraint.arithmetic.Less;
import com.koalog.jcs.constraint.arithmetic.LeqShift;
/**
* This is the famous Golomb ruler problem.
* It consists in finding n integers mark_i such that:
* <ul>
* <li>mark_0 = 0,</li>
* <li>mark_0 <...< mark_n-1,</li>
* <li>for all i<j, mark_j-mark_i are different,</li>
* <li>mark_n-1 is minimal.</li>
* </ul>
*
* @author Yan Georget
*/
public class GolombProblem extends BaseProblem {
//------------------------------------------------------------------------
// STATIC PROPERTIES
//------------------------------------------------------------------------
// optimal golomb rulers of small size
private static int[] golomb =
new int[] {0, // golomb 0 (0 mark!)
0, // golomb 1 (1 mark!)
1, // golomb 2
3, // golomb 3
6, // golomb 4
11, // golomb 5
17, // golomb 6
25, // golomb 7
34, // golomb 8
44, // golomb 9
55, // golomb 10
72, // golomb 11
85, // golomb 12
106, // golomb 13
127, // golomb 14
};
//------------------------------------------------------------------------
// PROPERTIES
//------------------------------------------------------------------------
/** The number of marks. */
int n;
/**
The distances between marks.
The mark i is modelled as dist[0][i].
*/
IntegerVariable[][] dist;
//------------------------------------------------------------------------
// CONSTRUCTORS
//------------------------------------------------------------------------
/**
* Sole constructor.
* @param n the size of the problem
*/
public GolombProblem(int n) {
this.n = n;
// list of distances between marks
List l = new ArrayList(n*(n-1)/2);
// distance variables
dist = new IntegerVariable[n][n];
dist[0][0] = new IntegerVariable("0_0", 0);
//l.add(dist[0][0]);
for (int i=0; i<n-1; i++) {
for (int j=i+1; j<n; j++) {
// we can always use sum(j-i) as a lower bound
// dist[i][j] is indeed the sum of j-i distinct integers
// moreover, we can use golomb[j-i+1]
// (which is a smaller golomb) as a lower bound
dist[i][j] =
new IntegerVariable(i + "_" + j,
j-i<n-1 ? golomb[j-i+1] : sum(j-i),
Integer.MAX_VALUE/n);
l.add(dist[i][j]);
if (i > 0) {
add(new Add(dist[0][j], dist[0][i], dist[i][j]));
}
}
}
add(new AllDifferent((IntegerVariable[])
l.toArray(new IntegerVariable[] {})));
// redundant constraints
for (int i=0; i<n-1; i++) {
for (int j=i+1; j<n; j++) {
// dist[i][j] = length - (sum of n-1-j+i distinct integers)
if (j-i < n-1) {
add(new LeqShift(dist[i][j],
dist[0][n-1],
-sum(n-1-j+i)));
}
}
}
// to remove symetrical solutions
add(new Less(dist[0][1], dist[n-2][n-1]));
// definition of the problem variables (variables to be labelled)
// here, the marks
setVariables(dist[0]);
}
//------------------------------------------------------------------------
// 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 GolombMinimizer(new GolombProblem(10)).optimize();
}
/**
* Returns 1 + ... + n.
* @param n an integer
* @return an integer
*/
static int sum(int n) {
return n*(n+1)/2;
}
}
|