Support for parametric LPs

[chrhansk]

For a research project I need to solve LPs which are parametric in their respective variable bounds, i.e. of the type

min c^T x,
s.t. lhs <= Ax <= rhs
l(a) <= x <= u(a)

where l(a) and u(a) are convex combinations in the parameter a in [0, 1]. Essentially, I would like to compute all vertices on the piecewise linear solution path over a and use them in a subsequent step.

I started to write a parametric solver based on SoPlex, but I think the API is lacking some functionality that I require.

Notably, it seems that LP bases cannot be directly modified by adding / removing variables or constraints. The enter() method of the solver is private and therefore inaccessible. Getting the Basis, manipulating it and setting it afterwards is likely to be inefficient, since it presumably discards the current factorization of the basis matrix.

Could you make it possible for a user to manually enter variables or constraints into the basis?

[leoneifler]

I'm not 100% sure if SoPlex would complain if you do this since your entering variables/constraints are presumably not always improving, but you could try and write your own SpxPricer that selects the entering variable/constraint.

You are correct that simply setting the basis to something different will trigger a new factorization.

[chrhansk]

I do not think that a custom pricer will help in this scenario:

The toy problem in the link above is the following:

max 3x + 2y, s.t. 2x + 3y <= 12.

The lower bounds are x, y >= 1 and remain constant. The upper bounds on x and y move from (2, 2) to (10, 10).

After I solve the initial problem, the optimal Basis consists of the bounds x <= 2 and y <= 2.
I then compute a primal direction by solving with respect to the Basis matrix for (10, 10) - (2, 2), yielding a primal direction of (8, 8). I then compute a stepsize of 0.05 until the constraint 2x + 3y <= 12 becomes violated when moving in the primal direction.

So I know that for upper bounds ranging from (2, 2) to (2.4, 2.4) (inclusive), the Basis remains optimal. Afterwards, the constraint 2x+3y <= 12 must enter the Basis, causing one of the bounds to leave. The problem is that the Basis is still optimal at that critical point, so now Basis exchanges are necessary. Exchanges becomes necessary only after raising the upper bounds to (2.4 + eps, 2.4 + eps).

I could probably use a pricer after setting the bounds accordingly, but that is kind of an ugly hack and I risk walking past other Bases. Directly changing Bases would be a lot easier in my opinion.

Btw: If you don't want to extend the API, we could hack on SoPlex directly...

[ambros-gleixner]

Let me chime in here, Leon is afk. If the problem is that methods like enter() are private, then one solution I could recommend is to implement the parametric optimize call inside the SPxSolverBase class and rather expose this via the API. The method performSolutionPolishing there could be interesting to look at, since it also changes basis on the optimal hyperplane.

I am not sure whether this is a reasonable way to go for you. But I am not sure we want to invest in exposing efficient basis manipulations to the top level API currently.

[chrhansk]

Hello Ambros,

I actually talked to Leon a little last Friday. He also pointed me towards the solution polishing as a way to switch bases. I have been hacking directly on the SoPlex code itself. One problem from the design aspect is that I need to be able to solve the initial LP pretty much with a black-box simplex and then perform very low-level manipulations afterwards.

Another significant problem is that once I change the upper / lower bound, SoPlex discards the current basis outright, an uninitializes the entire solution process. I think that this is overly pessimistic even in the case of ordinary LPs. After all, the basis matrix is still regular, and possibly even still optimal...

[ambros-gleixner]

Cool. The latter we should definitely change. Can you open a separate specific issue and assign to Leon?