Integration with optimization modeling/solver software

[N-Wouda]

In openjournals/joss-reviews#5028, @skadio wrote:

How you considered the integration of ALNS library with Optimization Modeling/Solving technology? For example, ALNS is well-known to be great complement to Constraint Programming, see e.g., the famous P. Shaw paper from 1998 https://link.springer.com/chapter/10.1007/3-540-49481-2_30

These ideas have found concrete implementations in libraries, e.g.,

• In Choco Constraint Solver (in java) https://choco-solver.org/docs/solving/lns/#:~:text=LNS%20is%20a%20two%2Dphase,their%20value%20in%20the%20solution.
• In Google OR-Tools Solver (available in Python) https://acrogenesis.com/or-tools/documentation/user_manual/manual/metaheuristics/jobshop_lns.html
• And even as solver-independent LNS modeling languages e.g. MiniLNS (similar to the larger MiniZinc language/ecosystem)
  https://people.eng.unimelb.edu.au/pstuckey/papers/MiniLNS.pdf

Here, the ALNS part is "generic" whereas the problem specific details are left to the user. Beyond vanilla problems, where there are a lot of side constraints, the user might have trouble "modeling" the state, in the first place.

What would be amazing is IF one could take ALNS, and then in the STATE description to use an off-the-shelf solver to model and solve the problem. This is probably easier said than done, but I believe there is a tremendous potential if we could build out the path for such integration.

Let's take Google OR-Tools for instances, since it is a great performing solver, has a high-level modeling language with support for many interesting constraints and available in Python. I imagine the STATE can be the initial Constraint model. Notice that, by solving it (potentially without an objective function), IMMEDIATELY generates an initial solution. So this initial construction comes for free (alleviating the user further). In some problems, especially with many constraints, even finding this solution can be tricky. In the Documentation I noticed, some simple/clever tricks are used like setting the first variable to 1, for instance. Then the relax/repair operators need to work off of the solvers variables.

I think this should be doable, and would give best of both worlds: ability to solve optimization problems at scale (thanks to local search) as opposed to exact solutions (which might not scale, e.g., mixed integer programs) BUT with the modeling support (as opposed to tradition local search where the user must implement everything from scratch).

I think there is vital gap in the Optimization community for this, especially within the Python tech stack which also is the main technology powering Data Science/ML/AI community. Feel free to connect with me later on, if this research directions sounds interesting. I would be happy to brainstorm.

[N-Wouda]

Solving general mathematical programming problems should also be possible. There has been some work on this in recent years (e.g., Hendel (2022)), but more can be done to simplify/improve the integration of heuristic methods for general optimization problems.

[N-Wouda]

Returning to this issue, I think it can be interesting if we can solve general CP/MIP problems in standard form. We could 'hijack' Pyomo or OR-Tools to provide the modelling interface, letting users pass such a model into our own ALNS metaheuristic to solve them. Implementing a performant ALNS for general CPs/MIPs is a significant amount of (research) work, but could be very worthwhile for the reasons Serdar already explained above.

@leonlan and @skadio: would either/both of you be interested in working with me on this? Timewise it'd probably be no earlier than the second half of this year, after the summer.

[leonlan]

Yea I'm definitely interested in working on this!

I'm currently familiarizing myself with constraint programming and I plan to make an LNS-based CP solver for large-scale flow shop scheduling problems. I'm working on this for the next few months, so I'll make sure to add my ideas/prototypes to this thread before we work on this together.

[skadio]

I am very much inclined in this direction --but a few call outs, having re-read the thread and the referenced papers.

Broadly speaking; on one hand we have A)
A1) LNS algorithm on top of CP solvers exists (see Choco for example)
A2) ALNS algorithm on top of MIP solvers exists (see SCIP for example)
(side note I am not aware of ALNS + CP in general sense, except problem specific applications)
In A), for both cases (A)LNS is implemented within/on-top of a specific solver.

On the other hand, in theory, we can have B) where.

• One can repeat the same exercise in A1 and A2 whereby the ALNS tool here is used as the top-level orchestrator, it implements generic CP/MIP neighborhoods in some generic modeling language and the solving phase can be offloaded to different solvers under the hood. In practice, getting B to work take non-trivial amount of work.

A and B differs which part of the solver is fix. A fixes the constraint solver, B fixes the ALNS solver.

But at the end of the day, both solutions yield roughly the same result for the user with a trade-off depending of whether the constraint solver is fixed or alns solver is fixed. That is not to say that, there are some nice properties of integrating tightly with a constraint solver (as in A) for efficiency. MiniLNS paper discusses some of this.

So.. the scope here needs to be sharpened to decide whether this will be a practical exercise (some form of reviving A into B) OR whether there is open angle in the research not explored before. The answer is not immediately clear to me.

Happy to brainstorm.

[N-Wouda]

@leonlan @skadio great to hear you're both interested! Since we won't start working on this for a little while longer, I suggest we wait until, say, July/August before planning a brainstorm meeting. In the meantime it's probably a good idea to use this issue to:

1. See what @leonlan learns in the context of flow shop scheduling;
2. Read/share more about existing solutions of the form of "A1/A2", and particularly determine if there are any general ALNS + CP tools out there. Possibly also figure out examples of "B", if any;
3. Think about where our ambitions lie, and what a good research gap could be.

The approaches of "A" and "B" are both superficially OK for me, as long as we can make work and make it work sufficiently generally that it is of value to many users.

---

For (3): my own interest here lies mostly in the combination of heuristics (e.g., ALNS) and exact methods. I don't mind if we make this a practical exercise, but in the interest of my (and @leonlan, I assume) PhD a research component with an eventual paper would be easier to 'sell'. We can discuss later what that research component should be. I should have some time next month to collect some readings and develop my own thinking on the research aspect further. I will report back here then.

One high-level idea I like is doing something with leaf fathoming in branch-and-bound trees. If we explore a leaf heuristically rather than exactly, we might be able to do things much faster without sacrificing too much quality.

[skadio]

All sounds good!

[leonlan]

Sounds good to me as well!

I don't mind if we make this a practical exercise, but in the interest of my (and @leonlan, I assume) PhD a research component with an eventual paper would be easier to 'sell'.

Yes, the same holds for me :-)

[N-Wouda]

See here for some ideas!

[leonlan]

See https://github.com/skadio/balans for a realization of this idea! @skadio nice work :)

Balans is a meta-solver for Mixed-Integer Programming problems (MIPs) using multi-armed bandit-based adaptive large neighborhood search.

[skadio]

@leonlan thank you!! It was great to brainstorm on this in its inception. We considered CP back then, but MIP turned out to be what works for Balans. I am still thinking this can also run over, say MiniZinc, and then a CP meta-solver is also a possible in future :)