3
$\begingroup$

Task / Goal

I'm considering adding some customized problem-specific local-search component on top of a general-purpose MILP solver (= improvement heuristic).

The basic idea is the following:

  • All new feasible integer solutions are extracted upon arrival
  • There is some concurrent code doing some local search procedure
    • (concurrently in regards to the MILP solver)
  • New improvements, if found, are put into some pool and MILP injects these during search
    • (simplified: let's assume there is only a single best new solution)

While conceptionally simple, if we take some LS procedure as given, there are probably tons of implementation-implied road-blocks.

I would be interested to learn about the feasibility and implementation of above using CoinOR Cbc.

Core Question / Problem

The core issue (to me) will be the transformation of the problem within the solver.

The LS-procedure will need:

  • extraction of integer-feasible MILP-provided solutions expressed on the original problem variables / constraints (during optimization)
  • injection of new integer-feasible solutions into the solver using the original problem variables / constraints (during optimization)

I'm not sure how much of a problem this will be with CoinOR Cbc, which i would like to focus on here.

Looking at other MILP solvers

Let's look at other solvers where things might be more clear (at least to me).

Cplex

The solver has what's called generic callbacks. The documentation says:

"It works almost exclusively on the original model; that is, with some exceptions, there is no access to the presolved model nor information available about the presolved model."

which helps a lot as this makes it easy to map solutions in-between our MILP-solver and our secondary component = LS.

I did implement some demo in the past where a CP-based Primal Heuristic was used in a similar manner (task: convert LP-relaxation to integer-feasible solution; no concurrency) and it seemed to work.

SCIP

SCIP, if i interpret it correctly, also looks like it would support this kind of concept.

This StackOverflow Question + Answer indicates, that there are calls:

  • mapping solutions from the solvers transformed problem space to the original problem space
    • -> extraction
  • mapping solutions from the original problem space to the solvers transformed problem space
    • -> injection

I never tried it and it will be probably a bit more complex to implement compared to cplex, but at least there is a clear idea about how to pursue it (or where to look).

Back to our focus: "CoinOR Cbc"

I actually don't know much about Cbcs internals, especially in regards to the components needed to tackle this task.

There is some general "Primal Heuristic" documentation, but it's unclear in which "context" we are working there. I guess, only the "transformed problem" makes sense.

I don't know, and this is the core question here, how i could:

  • extract integer-feasible solutions in original problem space
    • (each time a new one is found)
  • inject integer-feasible solutions from original problem space
    • (we would need some callback / even which is "frequent" enough to allow this -> probably available)

In terms of the abstract idea, i guess the solver should be ready to allow that kind of injection, as it's primal heuristics should also be doing this:

  • proposing new solutions (during search) to consider for follow-up search

The only difference might be the "problem space" they are looking at.

What would be be a viable route to pursue here? Where to look at?

I guess, but you might correct me, that this kind of hybridization might be a good approach when focusing on obtaining good feasible solutions within limited time (if development-resources allow to build a second "solver/perspective").

Update

Thanks to Florian for the comment / links.

Based on that i skimmed the code a bit.

The extraction-part of the questions looks to be solved now and the components to do this are surprisingly "fresh" in regards to Cbc-dev:

  • 2.10 (2019) introduced CbcModel::postProcessedSolver() which is used in the example

  • The code behind this looks also non-trivial (hard to understand without knowledge of solver-internals)

    • I guess there is no easy "just invert this" path

In regards to the injection-part, the most promising resource seems to be hot-start processing but i wouldn't say i'm very optimistic about trying this (because it's hard to understand what's exactly happening and some code-comments are not improving my confidence).

Funny thing: i'm currently failing to follow the MIPStart path through the solver which maybe should be even more promising.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ An advantage of this approach is that on small problems, you can stop the local search early once the MILP proves the optimality; and on large problems, you can still get good solutions quickly. $\endgroup$
    – fontanf
    Sep 14, 2021 at 15:46
  • 1
    $\begingroup$ To extract solutions from Cbc during the search, see example inc.cpp or my example for the GAP here (it's the SolHandler class). To inject a solution, I don't know. You can try asking on the Discussion page of the Github repo of Cbc $\endgroup$
    – fontanf
    Sep 14, 2021 at 15:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.