Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## Cost function implementation

Help
luka
2013-02-13
2013-05-30

• luka
2013-02-13

Hello

I am trying to implement a problem I have modeled into essentially a bin-packing problem.

For optimisation, I want the "fullness" of all bins to be as equal as possible, and I attempted to acheive this by giving each bin a cost that is the square of its allocations, then summing all these costs and using that as the cost in the search. By this method solutions that fill each bin the same amount have lowest cost.

for example, if assigning 4 units
A:  2
B: 2          would incur cost 2^2 + 2^2 = 8
whilst,
A: 1
B: 3          would incur cost 1^2 + 3^2 = 10

However, when running a search the values still stack up in the earliest parts of domain (because using IndomainMin for the select).

Here is a simple example of how I implemented

```import JaCoP.constraints.Constraint;
import JaCoP.constraints.Sum;
import JaCoP.constraints.XmulYeqZ;
import JaCoP.constraints.binpacking.Binpacking;
import JaCoP.core.IntVar;
import JaCoP.core.Store;
import JaCoP.search.DepthFirstSearch;
import JaCoP.search.IndomainMin;
import JaCoP.search.Search;
import JaCoP.search.SelectChoicePoint;
import JaCoP.search.SimpleSelect;
import JaCoP.search.SmallestDomain;
public class CostExample {
/**
* @param args
*/
public static void main(String[] args) {
int TIME_OUT_SECONDS=10;
int max = 200;
Store store = new Store();
// ******* Constraints **********
// each position in array w defines size of item i. (i = index)
int[] w = { 3, 3, 3, 3, 10, 10, 10, 3, 3, 10 };
// each position in array b defines a bin for item i as Intvar.
IntVar[] b = new IntVar[w.length];
for (int i=0; i<10;i++) {
b[i] = new IntVar(store, "b" + i,0 ,23 );
}
int bins = 24; // 24 bins, one per hour
IntVar[] c = new IntVar[bins];
for (int i=0; i<24;i++) {
c[i] = new IntVar(store, "c" + i, 0, max);
}
Constraint binPacking = new Binpacking(b, c, w);
store.impose(binPacking);
boolean Result = store.consistency();

//- ***** COST FUNCTION *****
IntVar[] z = new IntVar[bins];
for (int zi = 0; zi < bins; zi++) {
// the cost of each time-slot
z[zi] = new IntVar(store, "z" + zi, 0, max * max);
// bin i's cost is number allocations to it squared
store.impose(new XmulYeqZ(c[zi], c[zi], z[zi]));
}
IntVar cost = new IntVar(store, "costSum", 0, (int) ((max * max) * 24.0));
//total cost is sum of all costs
Constraint costCnstr = new Sum(z, cost);
store.impose(costCnstr);
long T1, T2;
T1 = System.currentTimeMillis();
// the search
Search<IntVar> label = new DepthFirstSearch<IntVar>();
SelectChoicePoint<IntVar> select = new SimpleSelect<IntVar>(b, new SmallestDomain<IntVar>(), new IndomainMin<IntVar>());
label.setAssignSolution(true);
label.setPrintInfo(true);
label.setTimeOut(TIME_OUT_SECONDS);
label.getSolutionListener().searchAll(true);
Result = label.labeling(store, select, cost);
T2 = System.currentTimeMillis();
System.out.println("");
System.out.println("\n\t*** Execution time = " + (T2 - T1) + " ms");
System.out.println("");
if (Result) {
System.out.println("*** Yes");
System.out.println(java.util.Arrays.asList(c));
IntVar[] theSolution = label.getVariables();
System.out.println("getVariables "+java.util.Arrays.asList(theSolution));
} else
System.out.println("*** No");
}
}
```

If anyone can offer some advice on where I have gone wrong, it would be very gracially appreciated…

Thank you

Luka

• kris
2013-02-13

Hi Luka,

In your program, you minimize cost variable using statement

Result = label.labeling(store, select, cost);

Just remove variable cost from the search and you will be able to search for all solutions or a specific solution.

Regards,
/Kris