Formulating Strict Inequalities and Getting the Values for the Variables

[Geo Sallon]

Is it possible to formulate such a series of inequalities within or-tools and getting the values for x and y?

1/24 < 1/15*y < 1/10*x < 2/24 < 2/15*y < 3/24

I do not need an objective function for this case. In theory, constraint programming would do the job. 

The problems are: 

1. The class cp_model does not offer a numerical variable (float/double) but only IntVar and BoolVar.
2. Since step one is not possible to my knowledge, I tried the classes MPSolver, MPVariable, MPConstraint. With the class MPConstraint I can only formulate inequalities and not strict inequalities.
   

This is the following code written in Java that I tried:

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Solves a problem with a time limit. */
public class test {
 static {
 System.loadLibrary("jniortools");
 }
 /* 1/24 < 1/15*y < 1/10*x < 2/24 < 2/15*y < 3/24 */
 public static void main(String[] args) throws Exception {
 // [START solver]
 // Create the linear solver with the CBC backend.
 MPSolver solver = new MPSolver(
 "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);
 // [END solver]

 // [START variables]
 double infinity = java.lang.Double.POSITIVE_INFINITY;
 // x and y are float/double variables.
 MPVariable x = solver.makeNumVar(0,1,"x"); //makeIntVar(0.0, infinity, "x");
 MPVariable y = solver.makeNumVar(0,1,"y"); //makeIntVar(0.0, infinity, "y");

 System.out.println("Number of variables = " + solver.numVariables());
 // [END variables]

 // 1/24 < 1/15*y ---> -1/15 * y < -1/24
 MPConstraint c0 = solver.makeConstraint(-1000,-1/24.0,"c0");
 c0.setCoefficient(y,-1/15.0);

 // 1/15*y < 1/10*x ---> 1/15*y - 1/10*x < 0
 MPConstraint c1 = solver.makeConstraint(-1000,0,"c1");
 c1.setCoefficient(y,1/15.0);
 c1.setCoefficient(x,-1/10.0);

 // 1/10*x < 2/24 ---> 1/10*x < 2/24
 MPConstraint c2 = solver.makeConstraint(-1000,2/24.0,"c2");
 c2.setCoefficient(x,1/10.0);

 // 2/24 < 2/15*y ---> -2/15*y < -2/24
 MPConstraint c3 = solver.makeConstraint(-1000, -2/24.0);
 c3.setCoefficient(y,-2/15.0);

 // 2/15*y < 3/24 ---> 2/15*y < 3/24
 MPConstraint c4 = solver.makeConstraint(-1000,3/24.0);
 c4.setCoefficient(y,2/15.0);

 System.out.println("Number of constraints = " + solver.numConstraints());
 // [END constraints]


 // [START solve]
 final MPSolver.ResultStatus resultStatus = solver.solve();
 // Check that the problem has an optimal solution.
 if (resultStatus != MPSolver.ResultStatus.OPTIMAL) {
 System.err.println("The problem does not have an optimal solution!");
 return;
 }
 // Verify that the solution satisfies all constraints (when using solvers
 // others than GLOP_LINEAR_PROGRAMMING, this is highly recommended!).
 if (!solver.verifySolution(/*tolerance=*/1e-7, /*log_errors=*/true)) {
 System.err.println("The solution returned by the solver violated the"
 + " problem constraints by at least 1e-7");
 return;
 }
 // [END solve]

 // [START print_solution]
 System.out.println("Solution:");
 System.out.println("x = " + x.solutionValue());
 System.out.println("y = " + y.solutionValue());
 // [END print_solution]

 // [START advanced]
 System.out.println("\nAdvanced usage:");
 System.out.println("Problem solved in " + solver.wallTime() + " milliseconds");
 System.out.println("Problem solved in " + solver.iterations() + " iterations");
 System.out.println("Problem solved in " + solver.nodes() + " branch-and-bound nodes");
 // [END advanced]
 }
}

[Laurent Perron]

As answered on stackoverflow, no you cannot use strict inequalities with the linear solvers.

Le lun. 5 août 2019 à 05:00, Geo Sallon <geo.s...@gmail.com> a écrit :

Is it possible to formulate such a series of inequalities within or-tools and getting the values for x and y?

1/24 < 1/15*y < 1/10*x < 2/24 < 2/15*y < 3/24

I do not need an objective function for this case. In theory, constraint programming would do the job. 

The problems are: 

1. The class cp_model does not offer a numerical variable (float/double) but only IntVar and BoolVar.
2. Since step one is not possible to my knowledge, I tried the classes MPSolver, MPVariable, MPConstraint. With the class MPConstraint I can only formulate inequalities and not strict inequalities.
   

This is the following code written in Java that I tried:

import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Solves a problem with a time limit. */
public class test {
 static {
 System.loadLibrary("jniortools");
 }
 /* 1/24 < 1/15*y < 1/10*x < 2/24 < 2/15*y < 3/24 */
 public static void main(String[] args) throws Exception {
 // [START solver]
 // Create the linear solver with the CBC backend.
 MPSolver solver = new MPSolver(
 "SimpleMipProgram", MPSolver.OptimizationProblemType.CBC_MIXED_INTEGER_PROGRAMMING);
 // [END solver]

 // [START variables]
 double infinity = java.lang.Double.POSITIVE_INFINITY;

 // x and y are integer non-negative variables.
 MPVariable x = solver.makeNumVar(-100,100,"x"); //makeIntVar(0.0, infinity, "x");
 MPVariable y = solver.makeNumVar(-100,100,"y"); //makeIntVar(0.0, infinity, "y");

--
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-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/766e99c0-5008-4d39-a2ea-7f0a47017634%40googlegroups.com.

[Laurent Perron]

And please multiply everything by 120. It removed further numerical errors.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAPyyUTtMW2ApUnS%2BmasB5ER_Hi8%2BiaW2frKor_9Tb0fCN8cE-w%40mail.gmail.com.

[Laurent Perron]

Here is a working solution using scaled integer values

from __future__ import absolute_import

from __future__ import division

from __future__ import print_function

from ortools.sat.python import cp_model

model = cp_model.CpModel()

scale = 100

x = model.NewIntVar(0, scale, 'x')

y = model.NewIntVar(0, scale, 'y')

# 1/24 < 1/15*y < 1/10*x < 2/24 < 2/15*y < 3/24

model.Add(5 * scale < 8 * y)

model.Add(8 * y < 12 * x)

model.Add(12 * y < 10 * scale)

model.Add(10 * scale < 16 * y)

model.Add(16 * y <= 15 * scale)

solver = cp_model.CpSolver()

solver.parameters.log_search_progress = True

status = solver.Solve(model)

if status == cp_model.FEASIBLE:

    print('x =', solver.Value(x) * 1.0 / scale)

    print('y =', solver.Value(y) * 1.0 / scale)

It outputs:

x = 0.43

y = 0.63

With a scaling of 10, it outputs x = 0.5 and y = 0.7.

Note that this is solved without any branching during search.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Laurent Perron]

replace 

    model.Add(12 * y < 10 * scale)

by

    model.Add(12 * x < 10 * scale)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00