21
$\begingroup$

Recently, I came across the below paper and found it very interesting.

Solving Mixed Integer Programs Using Neural Networks; https://arxiv.org/abs/2012.13349

The idea is to use (train with neural network models) similar problem instances to help the solver finding better incumbent solutions and branching strategies during branch-and-bound.

Has anyone tested this approach on a real world business problem? Is it practical or even worth to invest?

I have some doubts; SCIP is chosen as the base solver and they compare their results with tuned SCIP solver. However, to my experience, SCIP is a much slower solver than commercial solvers like Cplex, Gurobi. I understand the reason why they choose to use SCIP as the base solver as explained in the paper. However, I am still looking for an answer for the below question:

Can this approach will improve the solution time of Cplex solver as much as it does for SCIP solver? Because, SCIP is a much slower solver than Cplex and has more parts to be improved. Would it worth to use such an approach for Cplex?

Improve this question
$\endgroup$
1
  • $\begingroup$ Does this paper offer the reader with codes for reproducibility ? $\endgroup$
    – Tuong Nguyen Minh
    Jun 19 at 4:57

3 Answers 3

Reset to default
21
$\begingroup$

Regarding the paper, it's important to remember that general purpose MIP solvers are meant to be general purpose, hence it's not surprising that they can be improved by tailoring them to the test set, either using ML or some other form of automatic tuning. MIP solvers make many decisions while solving a problem and I guess it's quite natural to assume that machine learning can help designing better algorithms to make these decisions. To the best of my knowledge, state-of-the-art solvers don't use trained neural networks inside for anything yet. There is no lack of trying, I guess, considering how hot the topic is.

That does not mean that ML is not used to tune solvers. Decision trees come to mind as a technology that can be used to tune aspects of MILP solvers to deliver good default performance.

A key problem for ML in MIP is the lack of large enough test sets that are actually representative. This is already a problem when benchmarking, but gets worse if you want to train things like a neural net.

There is currently a competition ongoing (ML4CO, see link below) that encourages to solve optimization problems using ML/AI, the results of which might give some insight into how ML can be used in MIP solvers:

https://www.ecole.ai/2021/ml4co-competition/

Improve this answer
$\endgroup$
5
  • $\begingroup$ The competition link helped a lot. Thanks. $\endgroup$
    – alamaranka
    Aug 23, 2021 at 15:49
  • $\begingroup$ Cplex 12.10+ is already using machine learning as mentioned by Xavier Nodet in this post. $\endgroup$
    – rasul
    Aug 24, 2021 at 0:19
  • $\begingroup$ @r.beigi Yes, but I think that is something different from what we discuss here. $\endgroup$
    – alamaranka
    Aug 24, 2021 at 7:55
  • $\begingroup$ @alamaranka As others have mentioned, a solver is a collection of various algorithms for different tasks. The question is whether machine learning could replace or improve these algorithms? The comment informs that CPLEX is already utilizing and benefiting from machine learning at least in one case. This is quite relevant and informative. $\endgroup$
    – rasul
    Aug 24, 2021 at 10:06
  • $\begingroup$ @r.beigi As I wrote, as far as I know no solver uses neural nets. Other methods of machine learning are used as by the example you pointed out. $\endgroup$
    – Philipp Christophel
    Aug 24, 2021 at 11:02
13
$\begingroup$

SCIP is not slow. SCIP's code is roughly as fast as the commercial alternatives. What makes SCIP seem slower to the user is that, by comparison, the commercial solver heuristics (cuts, primal heuristics, branching, tuning) are superior.

Therefore, that paper actually makes a very sound comparison: "What if we had a machine figure out the heuristics instead of humans?". Specifically they did this for primal heuristics (Neural Diving) and branching (Neural Branching).

The result was matching GUROBI/CPLEX with SCIP and even solving open problems. Not too shabby.

Application-wise people have been trying to do this for ages with little success. It seems like Deepmind might have been the first to crack the problem, so we could start seeing applications in the next year or two.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks. But, SCIP is slower for "whatever reason." The approach developed in the paper helps SCIP on its drawback, heuristics. I think we can agree on that. My question remains unanswered. As commercial solvers' heuristics are already strong, can this approach help them for even better heuristics? The answer might be "yes", but would it worth to invest on this? $\endgroup$
    – alamaranka
    Aug 23, 2021 at 9:52
  • 5
    $\begingroup$ I would say a tentative "yes", in the sense that existing solvers could get more heuristics in their arsenal. Would it be worth to invest on this? That really depends on one's objective, but Deepmind seem to think so. $\endgroup$
    – Nikos Kazazakis
    Aug 23, 2021 at 10:52
  • 1
    $\begingroup$ @alamaranka to put in my 5 cents, it depends on wether training sets actually contain [results of applying] those heuristics themselves, so it depends rather on the quality of data - whoever/whatever generated the dataset must have known a particular heuristic that ML deduced. ML is not able to “invent” something that is not in the dataset. $\endgroup$
    – dk14
    Aug 24, 2021 at 6:03
  • 1
    $\begingroup$ @dk14 I wonder if "data augmentation" would work here. If you are solving an MIP problem on daily basis and only some of its parameters change, you may create "similar" problem instances to be used for training. $\endgroup$
    – alamaranka
    Aug 24, 2021 at 7:58
9
$\begingroup$

Has anyone tested this approach on a real world business problem?

If the question is, more generally, "for a practical optimization problem, can ML somehow accelerate the performance of a state-of-the-art MIP solver, given that we have already solved a large number of similar instances in the past?", then the answer is yes. In the reference below, for example, we show that ML can significantly accelerate the performance of CPLEX (with default settings) on realistic, large-scale instances of the Security-Constrained Unit Commitment problem. We achieve this, however, not through ML-based branching rules, but by predicting good warm starts and redundant constraints in the formulation.

  • Álinson S. Xavier, Feng Qiu, and Shabbir Ahmed. "Learning to solve large-scale security-constrained unit commitment problems." INFORMS Journal on Computing 33.2 (2021): 739-756. DOI:10.1287/ijoc.2020.0976

If the question is, more strictly, "for a practical optimization problem, can a MIP solver equipped with ML-based branching rules outperform a state-of-the-art MIP solver with default settings, given that we have already solved a large number of similar instances in the past?", then the answer is less clear. To the best of my knowledge, this has not been clearly demonstrated yet.

Can [Neural Branching] improve the solution time of [commercial MIP solvers] as much as it does for SCIP solver?

I don't think we have the answer for this question yet; someone would need to implement this branching rule within a commercial MIP solver and run benchmarks, which may not be possible without assistance from the company that developed the solver. That being said, I don't see why would this method work only for SCIP and not the other solvers.

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.