XPRESS support in MathOpt

[pet-mit]

Hello everyone,

We (RTE) have started the development of the "XpressSolver" interface to allow the use of MathOpt with the FICO XPRESS solver.
The development will probably take a few months, and we'll implement features gradually (starting with LP, MIP, etc).

We created this discussion so that we can have a place to chat about this topic.

(People from RTE involved in the developments: @pet-mit , @sgatto , @flomnes , @klorel )
(For your information: @djunglas )

[pet-mit]

Question: Would you prefer that we open several small pull requests to merge these features into the main branch one at a time, or would you prefer that we merge everything at once?
(@lperron @Mizux)

[rma350]

There are a few key differences in adding a solver for mathopt:

(1) The expectations of each solver on the input and output are higher (solver indepenent parameters, solver independent termination reasons) and there are integration tests that check that the behavior of the solvers is consistent. It is generally somewhat challening to get these tests working, but in the end it lets you do more complex things where you need these features (e.g. decomposition) in a solver indepent way. The tests can be a little brittle (the solvers are not actually the same/do not really offer strong contracts on there behavior). The tests need to be working from the start on whatever features you have. You may need to ask for help on getting everything working. Sometimes we need to change the tests.

(2) We try not to program directly against the C API, as it ends up being very verbose, and the code already is quite long. See gurobi (or the pull request for mosek) as good examples of wrapping the C API with an ABSL based C++ API (using Status for error propagation, and absl::span instead of double*, etc. Try and keep the code as close to the C API as possible/document any behavior changes if we really need to do them. And test this file directly (just make sure each codepath is covered by the tests, you do not need to test xpress itself.)

(3) In some situations, there is not a 1:1 mapping between the mathopt model and the underlying solver model. E.g. with Gurobi, they do not natively support linear constraints with upper and lower bounds (range constraints), you need to add an auxiliary variable to model this. These model transformations, combined with (a) incrementalism (b) variable deletion and (c) duality, ends up adding quite a bit of complexity. To get started, I would recommend just not supporting incrementalism and solving from scratch each time, and most of these issues go away. If things eventually get too complicated with the model transformations, you can break them out into a separate file and unit test the transformations directly.

I would recommend starting with something as small as possible, and just trying to get the integration tests to pass, e.g. just LP (maybe no basis, no rays, minimial/no solver parameters). You can look at the glop tests for an example:

https://github.com/google/or-tools/blob/stable/ortools/math_opt/solvers/glop_solver_test.cc

(just focus on the LP tests, you can ignore the rest to get started). Internally, we use bazel for running the tests. I am not sure if the tests work with cmake yet. If you want the mathopt team to be able to reproduce any problems you are having, the team is generally more familiar with bazel (lperron and mizux do more with both bazel and cmake).

I think that any code which is in a clean state (everything tested, nothing commented out) can probably be merged. I do not know which branch you should be on, I guess lperron and mizux will. Working in smaller pieces will probalby result in faster reviews. I think we need to have a quick discussion internally about merging this/who will be responsible, it will need to wait until after Thanksgiving (next week) as too many people are out.

[pet-mit]

Thank you for your very detailed answer.

I have spent a few hours familiarizing myself with the MathOpt code, especially with the Gurobi interface.
In fact, I tried to replicate the same design choices you made for Gurobi to implement XPRESS (although I think I can simplify a few things, like the constraint creation that I replicated, but that can be simplified for XPRESS).

I have enabled the LP simple tests for XPRESS and am working on getting them to pass (they do compile with CMake).

However, I have not yet created a bazel file for the XPRESS wrapper (g_xpress) and would not know how to do so without your help.

I have opened a draft PR in our fork here. It's pretty simple if you want to take a look already (the simplest of LP tests pass currently): rte-france#137

I have taken note of all your points, we will open small pull requests with the cleanest possible code to implement features one by one (under the condition that their tests pass, of course).

[rma350]

I looked through your change, I think this is all going on the correct direction. The Gurobi code is a good reference, but in particular, gurobi_solver.h/cc is a bit complex, you can/should probably do something simpler if possible.

I think the bazel part will be straight forward as well. We can figure it out once the code is working.

[pet-mit]

Thank you Ross for your valuable feedback

[pet-mit]

Hello
I'm struggling to make the test here pass for XPRESS, when using the primal simplex algorithm:

or-tools/ortools/math_opt/solver_tests/lp_incomplete_solve_tests.cc

Line 111 in 82914bc

ASSERT_TRUE(result.solutions[0].dual_solution.has_value());

How do we know for sure that there is a dual solution available (can we even know if dual is feasible?) when solving using primal simplex, if we interrupt it before the end?

@djunglas I don't know if you can help here: XPRESS seems to say that it has no dual solution in this case after interruption (XPRS_SOLSTATUS_NOTFOUND), when I use XPRSgetduals to get the dual status

[rma350]

I think it is likely that when running dual simplex, you will be in the reversed situation if you stop early, your solution is dual feasible but not primal feasible.

Also in both cases, if you stop in "Phase 1" (before finding a primal or dual feasible soltuion), you may not be able to return anything. I do not know if xpress lets you get at the phase 1 solution/basis (I don't think all solvers let you do this, but I do not remember the details from when we did this for GLOP or Gurobi).

[pet-mit]

I verified this case, XPRESS does return a primal solution

[djunglas]

@pet-mit, as far as I can tell, the failing test only checks that there is any dual value. It does not check that the dual values are correct or even reasonable, right?
I am wondering whether values returned by other solvers (that pass this test) are reasonable or whether these are just "some" values that happened to be in internal vectors at that time.

[pet-mit]

@djunglas you are right

FYI I have managed to make the test pass by providing the dual values returned by XPRSgetlpsol
I opened the first PR here: #4505

[djunglas]

The situation with Xpress is a bit tricky:

• For an interrupted primal simplex run, functions like XPRSgetduals() or XPRSgetsolution() will always return XPRS_SOLSTATUS_NOTFOUND (0)
• In this case you can use XPRSgetlpsol() (just like you did) to get the current values (you have to know what you are doing and which values you can expect to be valid)
• In all other cases you should use XPRSgetduals() and friends.

[pet-mit]

@djunglas
On a seperate topic, I have noticed that when the primal is unbounded, LPSTATUS is equal to "XPRS_LP_UNBOUNDED", but the dual "status" fetched through XPRSgetduals is equal to "XPRS_SOLSTATUS_UNBOUNDED".

Is this the expected behavior, or should the dual status be "XPRS_SOLSTATUS_INFEASIBLE"?

[djunglas]

This is a known issue and we are working on it. At the moment it is best to check the status returned by XPRSoptimize(), or, when using XPRSlpoptimize() to check the LPSTATUS.