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

Close

Cost function implementation

Help
luka
2013-02-13
2013-05-30
  • luka
    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
    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