1
$\begingroup$

I am trying to solve an optimisation problem and come up with two Integer Linear Programming models. For each model, I am able to find a function that calculate the number of possibilities based on different variables, e.g. problem sizes.

I cannot directly conclude that one model has a smaller search space than the other. Instead, I develop an application that compares the actual numbers of possibilities between 2 models based on different values of the variables.

My application tries millions of different variables and shows that the number of possibilities of one model is less than the other 99% of the time. Is it enough to conclude that it is likely for one model to have the smaller search space, and to be solved faster than the other?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ what is the optimisation problem ? What are the two models you are trying to compare ? $\endgroup$ – sashas Aug 14 '16 at 11:50
  • $\begingroup$ Why would one model have a smaller search space? It would model a different problem then, indicating that one of your models is wrong, or your "possibility counter" is wrong. $\endgroup$ – Raphael♦ Aug 14 '16 at 12:07
  • 1
    $\begingroup$ @Raphael The same problem can be modeled differently, like say graph coloring as a SAT instance. $\endgroup$ – Juho Aug 14 '16 at 12:28
  • $\begingroup$ I see. Solutions of the original problem may correspond to multiple solutions in a modelling. $\endgroup$ – Raphael♦ Aug 14 '16 at 14:26
  • 1
    $\begingroup$ In short, the answer is generally no: you cannot infer hardness from the size of a search space. It is the structure of an instance that counts. $\endgroup$ – Juho Aug 14 '16 at 15:45
1
$\begingroup$

There is no easy way to predict which ILP model will be faster to solve. Counting the number of variables is not a reliable predictor. Estimating the size of the "search space" (the number of feasible solutions) is not a reliable predictor. There is, in general, no fully reliable way to tell which model will be faster -- short of actually trying both.

Instead, my recommendation is that you try experiments. Try solving both models, and see which takes longer to solve. If your problem is parameterized in size, you can try solving for smaller sizes and see if a pattern emerges.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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