Linear Programming in Python (2023)

I've used python-mip extensively, though only on problems with up to ~10k variables, and only using basic LP features (no advanced solver callbacks).

python-mip is substantially faster than cvxpy, pulp, and pyomo for constructing _and solving_ a very simple LP with 10k variables. It's on par even with cylp using vectorisation (maybe I haven't used cylp as well as I could (either way cylp is dreadful to use)). I say _and solving_ because for my use case it's the time to construct and solve relatively simple & small problems (like, But keep in mind these kinds of benchmarks can depend a lot on how you're using the library. Like, are you spending almost all time actually solving the model? Then it probably doesn't matter what library you use to construct the model.

python-mip in general is pretty nice. It supports advanced solver features if you're into that sorta stuff. But their typing is a bit whacky (no py.typed file, use numbers.Real for typing which makes type checking a bit whacky). And it relies on a funky pre-compiled CBC binary (I had to compile it from scratch at a very specific commit to get it working on M1). python-mip creates/modifies variables in the underlying solver library (CBC/Gurobi) as you create/modify variables through the python interface (I believe this is an uncommon approach, but good). The internal data model of variables & linear expressions is quite clean and tidy.

Overall would recommend python-mip if you just need to solve MILP problems.

From my scrappy benchmark constructing and solving a very simple LP with 10k variables:

'benchmark_python_mip' took: 40.33 ms

'benchmark_cvxpy' took: 738.11 ms

'benchmark_pulp' took: 152.68 ms

'benchmark_pyomo' took: 191.66 ms

'benchmark_cylp' took: 38.91 ms

In operations and supply chains it is not hard to find *A* solution. Operators literally make these decisions manually every day without the need for any computer.

The main challenge is to optimize these decisions. With optimality guarantees. Consistently. Day in, day out, with various uncertainties.

That is what math optimization has been doing for decades.

And no, RL is nowhere to be seen in production, except from some consulting projects that are abandoned.

> Your response makes me wonder if the idea is not that RL can give more optimal solutions, but perhaps more robust ones?

LP (linear programming), given an optimal solution, has some sensitivity analysis that nicely addresses robustness.

In the LP find x to solve

maximize z = cx

subject to Ax = b, x >= 0,

small changes in c, A, and b can result in large changes in x (below I explain some of how). But, still, due to some continuity in the linear algebra, the changes in z should (I am avoiding doing the derivations) be small, and continuing to use the optimal x from before the changes should (again, some derivations are needed) be not far off (omitting details).

The feasible region is much like a diamond with flat sides and sharp points (the extreme points).

Uh, let set F be the feasible region, i.e.,

F = {x | Ax = b, x >= 0}

Then the feasible region is convex, i.e., for x_1 and x_2 in the feasible region and t in [0,1],

tx_1 + (1 - t)x_2

(intuitively the points on the line between the two points x_1 and x_2) is also in the feasible region F.

So, easily there can be two extreme points x_1 and x_2 in F such that

z = cx_1 = cx_2

and both are optimal.

Then all points on the line between x_1 and x_2 will be feasible and optimal. So, now have infinitely many optimal points.

And it can be that x_1 is the only optimal point but after some small changes both x_1 and x_2 are optimal. And x_2 can be a long way from x_1.

Sooooo, the small changes resulted in a big change in the optimal points. And maybe after the change, x_2 is optimal but x_1 no longer is.

In this case, maybe LP does not look "robust", but that's usually not a big problem since after the small changes, likely in practice can still get by using the old optimal x_1.

I.e., just by continuity, the "small changes" will keep the changes in the feasible region F and the optimal value z small.

Ah, here is the good news: If raising 40,000 chickens (my father in law used to do that) and there is a small change in the prices of some of the feeds, after the small change might change suppliers (big change in x) for a savings in prices. Intuitively, the changes just showed that you are not very dependent on your old suppliers but have some alternatives that involve some big changes in x (maybe drop one supplier for another one) for about the same z. That big change in x looks not "robust" but is good news, right?

Our work was precisely in optimization over massive numbers of possible scenarios amid multi-dimensional uncertainties. Again, significantly outperforms LP. Not surprised that you are an advocate of math optimization. Most people working on optimization in industrial operations and supply chains have an OR background, and this sort of conservatism is common. But there are lots of situations that LP can't optimize while RL can.

"Again, significantly outperforms LP."

No, this is mathematically impossible. You cannot out-optimize a mathematical global optimization solver. Whether that is LP, MILP, or NLP. Exactly because they provide a certificate of optimality.

It is like stating that you found a non-negative number that is smaller than 0. It’s not progressive. It’s flat out wrong.

"But there are lots of situations that LP can't optimize while RL can"

I will be satisfied if you just show us 1.

Stay in your lane, and state that you built a fast heuristic that works (finds good solutions but not optimal) in the problems you tried. Nobody can dispute this. But don't make claims you cannot support.