/*
* Copyright 2002, 2003, 2004, 2005 - <A href="http://www.koalog.com">Koalog</A>
*/
package com.koalog.jcs.examples;
import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
import org.apache.log4j.PropertyConfigurator;
import com.koalog.jcs.domain.SparseDomain;
import com.koalog.jcs.variable.IntegerVariable;
import com.koalog.jcs.constraint.BaseProblem;
import com.koalog.jcs.constraint.arithmetic.Element;
import com.koalog.jcs.constraint.arithmetic.Cycle;
import com.koalog.jcs.constraint.arithmetic.Permutation;
import com.koalog.jcs.constraint.arithmetic.Sum;
/**
* This is the Travelling Salesman Problem.
* It consists in finding an hamiltonian path of minimal weight
* in a weighted graph.
*
* @author Yan Georget
*/
public class TSPProblem extends BaseProblem {
//------------------------------------------------------------------------
// PROPERTIES
//------------------------------------------------------------------------
/** The weight of the cycle. */
IntegerVariable sum;
/** A map mapping a variable to an array of costs (weights). */
Map costs;
//------------------------------------------------------------------------
// CONSTRUCTORS
//------------------------------------------------------------------------
/**
* Sole constructor.
* @param graph the graph
* @param lowerBound a lower bound of the weight of the cycle
* @param upperBound an upper bound of the weight of the cycle
*/
public TSPProblem(int[][] graph, int lowerBound, int upperBound) {
super();
// variables & constraints definitions
sum = new IntegerVariable("sum", lowerBound, upperBound);
costs = new HashMap(graph.length);
// next[i] is the successor of node i
IntegerVariable next[] = new IntegerVariable[graph.length];
// prev[j] is the predecessor of node j
IntegerVariable prev[] = new IntegerVariable[graph.length];
// nweight[i] is the weight of edge i -> next[i]
IntegerVariable nweight[] = new IntegerVariable[graph.length];
// pweight[j] is the weight of edge prev[j] -> j
IntegerVariable pweight[] = new IntegerVariable[graph.length];
for (int i=0; i<graph.length; i++) {
SparseDomain domain = new SparseDomain(0, graph.length-1);
domain.remove(i);
next[i] = new IntegerVariable("next" + i, domain);
nweight[i] = new IntegerVariable("nweight" + i,
getMin(graph[i]),
getMax(graph[i]));
add(new Element(nweight[i], next[i], graph[i]));
costs.put(next[i], graph[i]);
}
for (int j=0; j<graph.length; j++) {
SparseDomain domain = new SparseDomain(0, graph.length-1);
domain.remove(j);
prev[j] = new IntegerVariable("prev" + j, domain);
// column
int[] tmp = new int[graph.length];
for (int i=0; i<graph.length; i++) {
tmp[i] = graph[i][j];
}
pweight[j] = new IntegerVariable("pweight" + j,
getMin(tmp),
getMax(tmp));
add(new Element(pweight[j], prev[j], tmp));
costs.put(prev[j], tmp);
}
add(new Permutation(next, prev));
add(new Cycle(next));
add(new Cycle(prev));
add(new Sum(sum, nweight));
add(new Sum(sum, pweight));
// definition of the problem variables (variables to be labelled)
List vars = new ArrayList(2*graph.length);
vars.addAll(Arrays.asList(prev));
vars.addAll(Arrays.asList(next));
setVariables((IntegerVariable[])
vars.toArray(new IntegerVariable[]{}));
}
//------------------------------------------------------------------------
// STATIC METHODS
//------------------------------------------------------------------------
private static int getMax(int[] a) {
int max = Integer.MIN_VALUE;
for (int j=0; j<a.length; j++) {
if (a[j] > max) {
max = a[j];
}
}
return max;
}
private static int getMin(int[] a) {
int min = Integer.MAX_VALUE;
for (int j=0; j<a.length; j++) {
if (a[j] < min) {
min = a[j];
}
}
return min;
}
private static int[][] matrixCompletion(int[][] g) {
int n = g.length;
int[][] c = new int[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (j <= i) {
c[i][j] = g[i][j];
} else {
c[i][j] = g[j][i];
}
}
}
return c;
}
/**
* 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 TSPMinimizer(new TSPProblem(TSPProblem.GR21, 0, 10000))
.optimize();
}
//------------------------------------------------------------------------
// STATIC PROPERTIES
//------------------------------------------------------------------------
/** Instance GR21 of TSPLIB (optimum is 2707) */
public static final int[][] GR21 = matrixCompletion(new int[][]{
{0},
{510,0},
{635,355,0},
{91,415,605,0},
{385,585,390,350,0},
{155,475,495,120,240,0},
{110,480,570,78,320,96,0},
{130,500,540,97,285,36,29,0},
{490,605,295,460,120,350,425,390,0},
{370,320,700,280,590,365,350,370,625,0},
{155,380,640,63,430,200,160,175,535,240,0},
{68,440,575,27,320,91,48,67,430,300,90,0},
{610,360,705,520,835,605,590,610,865,250,480,545,0},
{655,235,585,555,750,615,625,645,775,285,515,585,190,0},
{480,81,435,380,575,440,455,465,600,245,345,415,295,170,0},
{265,480,420,235,125,125,200,165,230,475,310,205,715,650,475,0},
{255,440,755,235,650,370,320,350,680,150,175,265,400,435,385,485,0},
{450,270,625,345,660,430,420,440,690,77,310,380,180,215,190,545,225,0},
{170,445,750,160,495,265,220,240,600,235,125,170,485,525,405,375,87,315,0},
{240,290,590,140,480,255,205,220,515,150,100,170,390,425,255,395,205,220,155,0},
{380,140,495,280,480,340,350,370,505,185,240,310,345,280,105,380,280,165,305,150,0}
});
/** Instance GR17 of TSPLIB (optimum is 2085) */
public static final int[][] GR17 = matrixCompletion(new int[][]{
{0},
{633,0},
{257,390,0},
{91,661,228,0},
{412,227,169,383,0},
{150,488,112,120,267,0},
{80,572,196,77,351,63,0},
{134,530,154,105,309,34,29,0},
{259,555,372,175,338,264,232,249,0},
{505,289,262,476,196,360,444,402,495,0},
{353,282,110,324,61,208,292,250,352,154,0},
{324,638,437,240,421,329,297,314,95,578,435,0},
{70,567,191,27,346,83,47,68,189,439,287,254,0},
{211,466,74,182,243,105,150,108,326,336,184,391,145,0},
{268,420,53,239,199,123,207,165,383,240,140,448,202,57,0},
{246,745,472,237,528,364,332,349,202,685,542,157,289,426,483,0},
{121,518,142,84,297,35,29,36,236,390,238,301,55,96,153,336,0}
});
}
|