Search code examples
ojalgolinear-optimization

Dual and reduced costs using SimplexSolver from ojAlgo

I would like to solve a linear problem using the simplex from ojAlgo (version 51.4.0) and to be able to retrieve its dual variables as well as its reduced costs. I was expecting the method getMultipliers() from Result to return the dual variables but it is not the case in my example (see code below).

My questions are the following:

  1. How to retrieve the dual variables?
  2. How to retrieve the reduced costs?
  3. What is the best way to force the usage of one solver (SimplexSolver in my case)?

For question 3, I have used primModel.options.debug(SimplexSolver.class) as addPreferredSolver() is deprecated. While working, I was wondering if there is a preferred way.

I would like to be able to retrieve those information outside of an ojAlgo fork (the classes PrimalSimplex and DualSimplex seem interesting here but they cannot be used, as they cannot be accessed from outside the package).

/**
 * problem from https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture05.pdf
 *
 * problem: maximize 2 * x1 + 3 *x2
 *      s.t.    4 * x1 + 8 * x2 <= 12
 *              2 * x1 +     x2 <= 3
 *              3 * x1 + 2 * x2 <= 4
 *              x1, x2 >= 0
 */
ExpressionsBasedModel primModel = new ExpressionsBasedModel(); // problem to solve
Variable x1 = primModel.addVariable("X1").lower(0).weight(2); // maximize 2 * x1
Variable x2 = primModel.addVariable("X2").lower(0).weight(3); //            ... + 3 * x2
Expression a1 = primModel.addExpression(); // constraints to respect
Expression a2 = primModel.addExpression();
Expression a3 = primModel.addExpression();
a1.set(x1, 4).set(x2, 8).upper(12); // 4 * x1 + 8 * x2 <= 12
a2.set(x1, 2).set(x2, 1).upper(3);  // 2 * x1 +     x2 <= 3
a3.set(x1, 3).set(x2, 2).upper(4);  // 3 * x1 + 2 * x2 <= 4

// force the use of simplex (question 3)
primModel.options.debug(SimplexSolver.class);
Optimisation.Result result = primModel.maximise();

// does not give the dual variables: no value present within the optional
Optional<Access1D<?>> multipliers = result.getMultipliers();

System.out.println(result.toString());

Any help would be greatly appreciated. Thank you!

Solution

  • The LinearSolver does return the dual variables, but:

    1. When the LP is generated from an ExpressionsBasedModel the reverse mapping, from LP-constraint to lower/upper limits on the variables and expressions of the model, is not implemented. So, the result returned by the ExpressionsBasedModel does not contain the dual variables. To get the dual variables you have to skip using ExpressionsBasedModel and instead us the builders in LinearSolver directly.

    2. In the linear solver/builder code there is logic to handle if the duals are needed or not. Don't remember exactly how this works. I think that when you use the builders you always get the duals. You have to check.

    If you want to control which solver the ExpressionsBasedModel will select you have to code an implementation of ExpressionsBasedModel.Integration and then register that using ExpressionsBasedModel#addIntegration(Integration<?>). This functionality exists to be able to use 3:d party solvers like CPLEX, GUROBI, MOSEK and others.