Dynamic Variable Selection

[Nikolaos Anestos]

Hello, 

I would like to know if it is possible to have Dynamic Variable Selection as a search strategy.

As an example, 

I have a IntVar array which i branch on, the variable selection strategies offered are enough for my purposes.

As a variable selection, I 'd like to check the assignments of another IntVar array (I am not branching on those variables, they are assigned during the solve process).

Then, as soon as the solver has to make a Desiccion, I want to check the latter array, and get the sum of the already assigned variables in that array.

If the sum is over a threshold I want to use ASSIGN_MIN_VALUE otherwise ASSIGN_MAX_VALUE.

I am not really sure if that is possible, that's why I turn here in order to get an answer and try to implement it.

Also, if there is any example that can guide me for the implementation, it would be ideal.

I am currently using the JAVA interface (is there any limitation with that? I can use another if there is).

Thank you  in advance!

[Vincent Furnon]

You can code your own decision builder to do that. We have examples in python (https://github.com/google/or-tools/blob/master/examples/python/steel.py), C# (https://github.com/google/or-tools/blob/master/examples/csharp/techtalk_scheduling.cs) and C++ (https://github.com/google/or-tools/blob/master/examples/cpp/network_routing.cc) which show you how to do that. It should be possible to code one in Java too but we don't have a code sample yet (I'll try to produce a small example).

Vincent

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vincent Furnon]

Here's a modified version of https://github.com/google/or-tools/blob/master/examples/com/google/ortools/samples/RabbitsPheasants.java using a custom decision builder:

package com.google.ortools.samples;

import com.google.ortools.constraintsolver.ConstraintSolverParameters;

import com.google.ortools.constraintsolver.Decision;

import com.google.ortools.constraintsolver.DecisionBuilder;

import com.google.ortools.constraintsolver.JavaDecisionBuilder;

import com.google.ortools.constraintsolver.IntVar;

import com.google.ortools.constraintsolver.Solver;

import java.util.logging.Logger;

/**

 * Sample showing how to model using the constraint programming solver.

 *

 */

public class RabbitsPheasants {

  private static Logger logger = Logger.getLogger(RabbitsPheasants.class.getName());

  static {

    System.loadLibrary("jniortools");

  }

  public static class MyDecisionBuilder extends JavaDecisionBuilder {

    IntVar var1;

    IntVar var2;

    public MyDecisionBuilder(IntVar v1, IntVar v2) {

      var1 = v1;

      var2 = v2;

    }

    @Override

    public Decision next(Solver solver) throws Solver.FailException {

      if (!var1.bound()) {

        return solver.makeAssignVariableValue(var1, var1.min());

      }

      if (!var2.bound()) {

        return solver.makeAssignVariableValue(var2, var2.min());

      }

      return null;

    }

    @Override

    public String toString() {

      return "MyDecisionBuilder";

    }

  }

  /**

   * Solves the rabbits + pheasants problem.  We are seing 20 heads

   * and 56 legs. How many rabbits and how many pheasants are we thus

   * seeing?

   */

  private static void solve(boolean traceSearch) {

    ConstraintSolverParameters parameters =

        ConstraintSolverParameters.newBuilder()

            .mergeFrom(Solver.defaultSolverParameters())

            .setTraceSearch(traceSearch)

            .build();

    Solver solver = new Solver("RabbitsPheasants", parameters);

    IntVar rabbits = solver.makeIntVar(0, 100, "rabbits");

    IntVar pheasants = solver.makeIntVar(0, 100, "pheasants");

    solver.addConstraint(solver.makeEquality(solver.makeSum(rabbits, pheasants), 20));

    solver.addConstraint(

        solver.makeEquality(

            solver.makeSum(solver.makeProd(rabbits, 4), solver.makeProd(pheasants, 2)), 56));

    DecisionBuilder db = new MyDecisionBuilder(rabbits, pheasants);

    solver.newSearch(db);

    solver.nextSolution();

    logger.info(rabbits.toString());

    logger.info(pheasants.toString());

    solver.endSearch();

  }

  public static void main(String[] args) throws Exception {

    boolean traceSearch = args.length > 0 && args[1].equals("--trace");

    RabbitsPheasants.solve(traceSearch);

  }

}

[Nikolaos Anestos]

Thanks a lot for the reply! 

I will give it a go.