Decision Optimization

 View Only
Expand all | Collapse all

If then CPO Java

  • 1.  If then CPO Java

    Posted Mon August 21, 2023 04:17 PM

    Hello everyone.

    I would like to know how to express the sentence if x = 10 then p + 5 = q. However, I am struggling to accomplish this, specifically, I do not know how to express p - q in Java. Below follows my code:

    import ilog.cp.*;
    import ilog.concert.*;
    
    public class Color {
        public static void main(String[] args) {
            try {
                IloCP cp = new IloCP();
    
                IloIntVar x = cp.intVar(10, 10);
                IloIntVar p = cp.intVar(0, 10);
                IloIntervalVar q = cp.intervalVar(0, 10);
    
                IloConstraint eq = cp.eq(x, 10);
    
                IloNumExpr ex = p - q; ???????????????????
    
                IloConstraint eq1 = cp.eq(ex, -5);
                IloConstraint ifThen = cp.ifThen(eq, eq1);
    
                cp.add(ifThen);
    
                if (cp.solve()) {
                    System.out.println("Solved");
                } else
                    System.out.println("Error");
    
            } catch (IloException e) {
                System.err.println("Error " + e);
            }
        }
    }
    

    Thanks and regards.



    ------------------------------
    Matheus Andrade
    ------------------------------


  • 2.  RE: If then CPO Java

    IBM Champion
    Posted Mon August 21, 2023 10:42 PM

    If p is an integer and q is an interval, I don't think the statement p + 5 = q makes sense. Do you mean that p + 5 should be in the interval given by q (q-start <= p + 5 < q-end)?



    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: If then CPO Java

    Posted Tue August 22, 2023 05:29 AM

    Thanks for saving my day once more!

    So, if we impose the constraint (q-start <= p + 5 < q-end), the q would have multiple values as solutions, and based on the 4th comment given in this thread:


    CP Optimizer can solve problems on integer decision variables only. Floatting points variables are admitted but they must behave as an expression. That is they must be fixed to a value once all the integer variables are fixed. They cannot be decision variables.

    That is why I am forcing the fixing over q. For a more detailed description of my intentions, I am trying to model an MTZ constraint, so my end goal would be

    if next[i] = j then mtz[j] = mtz[i] + distance[i, j]

    Of course we could simply create a variable x[i, j] telling whether the arc between i and j exists, but I am trying to scape from this modeling in order to have a model with less variables.

    Case you have any other insight in this regard, please, let me know.

    Thanks and BR.



    ------------------------------
    Matheus Andrade
    ------------------------------



  • 4.  RE: If then CPO Java

    Posted Tue August 22, 2023 06:50 AM

    Hello,
    it seems that you expect that in CP Optimizer Interval Variables are continuous variables, but they are a different kind of variables, typically used to modelize tasks in scheduling.

    In CP, instead of using MTZ constraints as in MIP, one can use a subCircuit constraint: it has been introduced in the last release of CP Optimizer (see https://www.ibm.com/docs/en/icos/22.1.1?topic=2211-new-circuit-subcircuit-constraint) and an example of use is given in the release (for Java, see cpoptimizer/examples/src/java/Cvrptw.java)



    ------------------------------
    Olivier Lhomme
    ------------------------------



  • 5.  RE: If then CPO Java

    Posted Tue August 22, 2023 07:09 AM

    Thank you very much.

    However, in my case the MTZ has also another purpose, it is being also used for delimiting the maximum spent time, specifically I am working with a max-profit TSP, So, when I state that if next[i] = j then mtz[j] = mtz[i] + distance[i, j], I am aiming to also impose the constraint

    mtz[i] <= salesman_distance_limit, forall i

    Let me know case any additional clarificaion is required.

    Thanks and regards.



    ------------------------------
    Matheus Andrade
    ------------------------------



  • 6.  RE: If then CPO Java

    Posted Tue August 22, 2023 10:51 AM

    Have a look at the Cvrptw.java example:

    the total distance is simply a sum of terms like "distance[i][next[i]]", where "next" is the intExprArray passed to the subCircuit constraint. 

    Note the useful CP construct: the array distance[i] is indexed by the intExp, distance[i][next[i]]

    If your question is about how to force each partial sum to be less than salesman_distance_limit:

     just add a constraint in the loop that builds the sum to constrain the current partial sum.

    (not needed if you have non-negative distances only)



    ------------------------------
    Olivier Lhomme
    ------------------------------



  • 7.  RE: If then CPO Java

    Posted Tue August 22, 2023 12:03 PM
    Edited by Matheus Andrade Tue August 22, 2023 03:28 PM

    Thanks for the attention.

    Yes, I already took a look at the mentioned file, however, the script discretizes the floating magnitudes, cf. the lines 217 to 221 of the mentioned file.

    private IloIntVar[] veh;
    private IloIntVar[] startTime;
    private IloIntVar[] load;
    private IloIntVar used;
    private IloIntVar[] prev;

    Obviously, I could do the same for my case, however I would like to know if it is possible to model a distance limit constraint (salesman_distance_limit) without the discretization, by using CPO. And, without creating variables for the arcs, i.e., keeping the variables number linear wrt the number of nodes.

    Precisely, I am trying to express the following reasoning through CPO.

    ...
    IloIntVar[] next;
    IloIntervalVar[] incurred_distance;
    ...
    IloConstraint null_distance_depot = cp.eq(incurred_distance[depot], 0.0); // Don't think it is semantically right,
                                           // but you get the meaning
    cp.add(null_distance_depot);
    ...
    for (int i : nodes)
                for (int j : nodes) {
                            if (j == depot) continue;
    
                            IloConstraint arc_ij = cp.eq(next[i], j);
                            IloConstraint increment_distance = cp.eq(incurred_distance[j], incurred_distance[i] + DISTANCE_MATRIX[i][j]);
    
                            IloConstraint ifThen = cp.ifThen(arc_ij, increment_distance);
                            cp.add(ifThen);
                }
    ...
    

    Note that, in the above code, whenever all the integer variables assume some integer value, there will be only one possible assignment of values for the floating variables (the incremental incurred distance at each node), and thus, the statement give at the 4th comment given in this thread, is respected.

    Thanks for the attention, and BR.



    ------------------------------
    Matheus Andrade
    ------------------------------



  • 8.  RE: If then CPO Java

    IBM Champion
    Posted Tue August 22, 2023 02:11 PM
    Edited by Paul Rubin Tue August 22, 2023 02:12 PM

    Try changing 

    IloIntervalVar[] incurred_distance;

    to

    IloNumVar[] incurred_distance = new IloNumVar[];
    for (i = whatever) {
      incurred_distance[i] = cp.numVar(0, salesman_distance_limit);
    }

    There is no reason I can see to be using interval variables here.



    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 9.  RE: If then CPO Java

    Posted Tue August 22, 2023 04:04 PM

    Thank you very much everyone.

    So, I created a POC for evaluating all these strategies, here it is. The code is the one below:

    import ilog.cp.*;
    import ilog.concert.*;
    
    public class Main {
        public static void main(String[] args) {
            try {
    
                // params
                int j = 10;
                double DISTANCE_IJ = 4.5;
    
                // init model
                IloCP cp = new IloCP();
    
                // set vars
                IloIntVar next_i = cp.intVar(0, 10); //next node to be visited after node i
                IloNumVar distance_at_i = cp.numVar(0, 0); // incurred distance at node i
                                // forces the distance at i to be 0 (as it was supposed to be a depot)
                IloNumVar distance_at_j = cp.numVar(0, 10);// incurred distance at node j
    
                // set constraints
    
                // if next node of i is j then update distance at j
                cp.add(
                        cp.ifThen(
                            cp.eq(next_i, j), 
                            cp.eq(cp.diff(distance_at_i, distance_at_j), - DISTANCE_IJ)
                            )
                      );
    
                // edge case, since CPO requires the floating variables to have fixed value when 
                // all the discrete variables are setted, we say that if arc ij does not exist
                // simply set the distance_at_j to 0
                cp.add(
                        cp.ifThen(
                            cp.neq(next_i, j), 
                            cp.eq(distance_at_j, 0)
                            )
                      );
    
                // for seeing the behaviour of when the next_i = j,
                // just uncomment the snippet below
                //cp.add(
                //      cp.eq(
                //          next_i, 
                //          j
                //          )
                //    );
    
                if (cp.solve()) {
                    System.out.println("Solved");
    
                    System.out.println(cp.getValue(next_i));
                    System.out.println(cp.getValue(distance_at_i));
                    System.out.println(cp.getValue(distance_at_j));
    
                } else
                    System.out.println("Not solved");
    
            } catch (IloException e) {
                System.err.println("Error: " + e);
            }
        }
    }

    The execution ends up with the following log:

    Warning: Comparison of floating point expressions may result in true or false for very small changes in expression values.
               FloatVar_3 - FloatVar_4 == -4.5
    Warning: Comparison of floating point expressions may result in true or false for very small changes in expression values.
               FloatVar_4 == 0
     ! --------------------------------------------------- CP Optimizer 22.1.1.0 --
     ! Satisfiability problem - 1 variable, 3 constraints
     ! Initial process time : 0,01s (0,01s extraction + 0,00s propagation)
     !  . Log search space  : 3,5 (before), 3,5 (after)
     !  . Memory usage      : 266,9 kB (before), 266,9 kB (after)
     ! Using parallel search with 20 workers.
     ! ----------------------------------------------------------------------------
     !               Branches  Non-fixed    W       Branch decision
     *                      2  0,04s        1         5  = _int0
     ! ----------------------------------------------------------------------------
     ! Search completed, 1 solution found.
     ! ----------------------------------------------------------------------------
     ! Number of branches     : 168
     ! Number of fails        : 70
     ! Total memory usage     : 8,8 MB (8,8 MB CP Optimizer + 0,0 MB Concert)
     ! Time spent in solve    : 0,04s (0,04s engine + 0,01s extraction)
     ! Search speed (br. / s) : 5.600,0
     ! ----------------------------------------------------------------------------
    Solved
    5.0
    0.0
    0.0
    

    Which, besides the warnings, seems to be fine.

    Thank you very much everyone. Let me know of any detail I am missing.



    ------------------------------
    Matheus Andrade
    ------------------------------



  • 10.  RE: If then CPO Java

    IBM Champion
    Posted Tue August 22, 2023 04:43 PM

    You might be able to avoid the warnings by change floating expression = constant to constant - epsilon <= floating expression <= constant + epsilon, but personally I don't think I would bother. If it works, it works.



    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 11.  RE: If then CPO Java

    Posted Wed August 23, 2023 02:02 PM

    Thank you very much.



    ------------------------------
    Matheus Andrade
    ------------------------------