17
$\begingroup$

I'm doing a project about the estimation of the difficulty of mixed-integer programming problems. The MIP instances are from MIPLIB 2017. And there are three categories of MIPs provided by MIPLIB 2017, which are "Easy", "Hard" and "Open", which represent the solving difficulty of MIPs. My project aims to figure out the characteristics of MIPs in different categories and tries to build a predictive model to predict the difficulty of a MIP.

But when I'm doing this project, I get more and more confused about the practical meaning of estimating the difficulty of a MIP. What does it help of knowing the difficulty of a MIP?

Improve this question
$\endgroup$
1
  • 8
    $\begingroup$ Before running a race, wouldn't you rather know if its a 100m or a marathon ? The same applies here. Different difficulties can imply different tools, different parameters, etc. $\endgroup$
    – Kuifje
    Commented Mar 16, 2020 at 12:29

2 Answers 2

Reset to default
13
$\begingroup$

The performance of an exact (or heuristic) solver on an instance will depend on some intrinsic characteristics, normally called features. And different solvers, or different configurations of a solver, will obtain different results on instances with different characteristics. For NP-hard problems, this might mean that an instance solved by solver X in a few minutes can take hours using solver Y, and the opposite situation can happen for another instance.

To know whether you should use X or Y to solve an instance, you can run the two algorithms in parallel and see which one terminates first, or you can try to look at the instance characteristics and predict which solver will terminate first. If you have to solve multiple instances, the second approach will save you a lot of time (hopefully).

For example, by knowing that an instance is "easy" you can choose to use an exact solver (ideally, you'll also be able to tell which solver to choose), while for an instance that is or looks like an "open" one you can save time and use a heuristic approach from the start.

In addition to the links provided by Marco Lübbecke in his answer, you can take a look at the Algorithm Selection library paper, this recent survey on algorithm selection, or this portfolio selector for SAT.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your answer, Alberto! I pretty agree with what you've said, and the papers you shared really help a lot! I understand only the prediction is not enough, it's more important to find out the efficient ways to solve those hard and open MIPs. $\endgroup$
    – Karen Jin
    Commented Mar 17, 2020 at 3:45
  • $\begingroup$ Yes, consider prediction as a preliminary step for solving a model more efficiently, which is what matters in practice. $\endgroup$
    – Alberto Franzin
    Commented Mar 17, 2020 at 8:46
11
$\begingroup$

What you are looking for may already exist. E.g., here is a paper on Predicting the Solution Time of Branch-and-Bound Algorithms for Mixed-Integer Programs, and another one on Algorithm runtime prediction: Methods & evaluation. Already years ago, researchers tried to predict the size of the B&B tree and it has been a topic also recently.

There is also a thread about it on research gate.

If this is not exactly what you are looking for, then these papers at least are worthwhile reading for their motivations, which then again may answer your question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, Marco! These papers are really helpful! $\endgroup$
    – Karen Jin
    Commented Mar 17, 2020 at 3:48

Your Answer

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

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