Search code examples
pythonlinear-programminginteger-programmingbranch-and-bound

Is there a good option for creation of custom branching rules in branch-and-bound for MILPs in Python?

Basically, I want to recreate the conceptual results from the paper "Learning to Branch in Mixed Integer Programming" by Khalil, et al, at the same time avoiding, if possible:

1)The necessity of obtaining an academic license for CPLEX (which was used in the paper) or similar serious commercial solver

2)The necessity of using C based API. This is not a strict requirement, but Python has the benefit of having good and very accessible ML libraries, which seems like a great advantage for this specific goal

I am aware, that there is a great number of open source Python based MILP solvers, but a lot of them focus on the end-to-end solution of relatively simple problems in their presentation and, if we also consider, that a lot of them (if not all) hook up to other C based solvers, it is highly non-obvious to judge, which ones actually have needed customization potential.

So, if anyone has more in-depth experience with trying to customize Python solvers for their highly specific needs, I would appreciate the advice.

Solution

  • I'm afraid you will hit a roadblock at some point there. It's really hard to do that without doing C/C++ work (imho).

    Python-way

    I only know three projects with some low-level functionality (and it's still hard to say if those fit your needs).

    • https://github.com/coin-or/python-mip
      • relatively new
      • promises interactive cut-gen
      • has a chapter Developing Customized Branch-&-Cut algorithms
      • but i'm not sure if there is enough freedom for your task (seems to focus on cuts for now)
      • build around open-source solver Cbc/Clp (besides Gurobi)
    • https://github.com/coin-or/CyLP
      • not much develeopment for years now
        • the whole python-3 dev was sad (see issues; pull-request not processed for years; it's a resource problem: the maintainers are nice people!)
      • was designed to research pivoting
      • but it also says: For example, you may .. define cut generators, branch-and-bound strategies
        • hard to see how to achieve what you look for except for abstract LP-relax - fix - resolve
        • might be hard to control specifics (warm-start vs. hot-start)
        • build around open-source Cbc/Clp
    • https://github.com/SCIP-Interfaces/PySCIPOpt
      • basic docs show more high-level usage
      • but it's internal code at least has entries for branchexeclp and co.
        • maybe it's ready to use (maybe not)
        • raw list of interface classes
        • as those things (maybe) wrap the original C-API, there is a lot of good documentation in the parent-project!
      • build around open-source solver SCIP
      • easier to grab the solver in academic setting, but by no means free (i'm not a lawyer and won't try to find the right words)
      • at least one developer of it is active on StackOverflow

    Alternative: C++

    If trying to get full-control; which might be needed, with minimal need for understanding the underlying solver in all it's details, you probably want to use C/C++ within Coin OSI. Sadly the Cbc part is unmaintained, but depending on your exact task, you might only need Clp for example.

    Alternative: Julia

    I did not follow the recent developments there, but the language did have a strong early focus on Mathematical Optimization (driven by a big group of people) surpassing python even in it's early days (imho!).

    But i'm not sure if MathOptInterface is fine-grained enough for your task.