library(simplex) showcase: Bin packing using delayed column generation

[triska]

Dear all,

as library(simplex) now ships with Scryer Prolog, I have finally adapted a Prolog solution to a well-known linear programming task, a combinatorial optimization problem called bin packing, to Scryer Prolog:

https://www.metalevel.at/various/colgen/

It's still quite slow at the moment, but at least the task can now be expressed and solved at all already! It can solve a few smaller examples that may even be useful in practice. library(simplex) can be improved in many ways, maybe most notably by changing the implementation to the so-called revised simplex method, where we benefit from sparse matrices. It is my hope that such examples motivate one of you to help me improve the implementation.

Enjoy!

All the best,
Markus

[aarroyoc]

Congratulations! Thanks to you and @mthom to allow it! As a personal note, using this library (in SWI) was one of the first things that I did in Prolog outside the usual Prolog teaching in university. It was a pleasure to write my linear programming problems and solve them with a clean syntax.

[triska]

With the latest rebis-dev development branch and its improved inlining, each of the sample instances is now solved 10 times faster! I have updated the timings. Wow!

[triska]

And the much faster nth0/3 implementation that is now available in rebis-dev (see #1593) yields another quite noticeable improvement of about 40% for each instance! I have again updated the timings!

[gruhn]

Hi Markus, I'm very interested in working on this but I'm very busy with work and my studies. However, since you mentioned that this could be turned into a thesis project I'm considering to do just that. I'm planning to start my master thesis in summer 2023 (at RWTH Aachen). I don't know what the process is to get such a project approved or if I can find an advisor who will go along with this, so no big promises. But if it doesn't work out I hope I can still help after I finished my degree 🙂

[triska]

Wow, that would be awesome!

Reportedly one of the best references for implementing the revised simplex method is the book Introduction to Linear Optimization by Dimitris Bertsimas and John Tsitsiklis. You may want to at least glimpse through the relevant sections before committing fully to this project. The first 200 pages (Chapters 1-4) ought to suffice for this project.

Papadimitriou and Steiglitz also discuss the method, albeit more tersely, in Combinatorial Optimization: Algorithms and Complexity.

To me, the main motivation for implementing library(simplex) were exactly such delayed column generation tasks that often arise in practice. The key feature that library(simplex) provides over CLP(Q) for this is that it lets us reason about the so-called shadow prices. I am not even sure how they can be read off when using the revised simplex method. So, implementing the revised simplex method in this library also has a theoretically interesting aspect that may involve some consideration and matrix algebra.

[gruhn]

Nice 👍 thanks for the references

[gruhn]

Bad news. It's not going to work out, sorry. But as I said: I'd like to come back to it, if this is still open after I'm done with my thesis.