25
$\begingroup$

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two formulations of a problem that use different sets of decision variables are compared. Can we just compare the LP-relaxation bounds?

For example, a route-based formulation for a vehicle routing problem (using an exponential number of variables) is usually considered to provide a better LP-relaxation bound. However, such a formulation employs a completely different set of decision variables. What is the right way to show that such a formulation is better? Is there a standard definition?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Can I suggest that you remove the last sentence and write that up as a separate question? "How do you compare two different formulations?" and "Are route-based models always better?" are two distinct, and valid, questions. $\endgroup$
    – LarrySnyder610
    Aug 19, 2019 at 21:33
  • 6
    $\begingroup$ Possibly related question: Tightness of an LP relaxation without using objective function. $\endgroup$
    – Kevin Dalmeijer
    Aug 19, 2019 at 21:36

6 Answers 6

Reset to default
20
$\begingroup$

Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping.

Take for example a flow formulation and a route formulation for a vehicle routing problem (minimization). Typically, the folllowing argument can be made:

  1. Given (fractional) values for the route variables, we can find values for the flow variables that result in the same objective value.
  2. Given (fractional) values for the flow variables, there may not be values for the route variables that result in the same or a lower objective value.
  3. It follows that the route formulation always provides a bound that is at least as high as that of the flow formulation, and sometimes higher.
  4. So the route formulation is stronger.

For vehicle routing problems, step 1 is often trivial, and step 2 may require a little bit of work.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The conjecture that one formulation is stronger than another often comes from computational experiements. Thus, if you can show that model M1 is not weaker than model M2 in Step 1, and you have an example where M1 is strictly better than M2, then you have the classical: M1 is at least as good as M2, and sometimes strictly better (LP-wise). $\endgroup$
    – Sune
    Aug 20, 2019 at 9:11
15
$\begingroup$

I'm not sure there is a single, definitive best way to compare models, and if there is I likely have never seen it applied. I lean toward computational comparisons if properly done, but "properly done" is in the eye of the beholder. The most obvious criteria for computational comparisons are that they use the same test problems (not selected because they favor one model over the other) and that they use the same hardware. The next criterion is that, ideally, the test problems are both realistic (comparable to real-world versions of the problem) and span a reasonable range of sizes. You are correct that the MTZ algorithm for TSP has looser relaxations than DFJ, but about the time you are running out of memory trying to look at all node subsets of cardinality greater than two, the MTZ formulation starts to look pretty darn good.

Also, some formulations may benefit from specific features of certain solvers, which needs to be made clear if those features are used in the comparisons.

Improve this answer
$\endgroup$
11
$\begingroup$

I agree with most of the comments here; Even if the decision variables are different, you may use proof by construction, for example, with appropriate mapping to prove that a formulation is stronger than another one. When comparing two different (yet equivalent) formulation for the same problem, I often use three criteria: (1) LP relaxation/tightness, (2) sizes of the formulations (in terms of number of variables and constraints; a larger size often suggests an increase in solution time for the LP relaxations), (3) the existence of artificial/logical/etc Big-M constraints. You can check our recent paper (https://www.sciencedirect.com/science/article/pii/S0377221719304989), in which we compare different (equivalent) SMILP formulation for single server stochastics sequencing and scheduling. Then after comparing the formulation theoretically, you may consider comparing them computationally using a wide range of realistic problem instances.

Improve this answer
$\endgroup$
6
$\begingroup$

I would like to add some criteria for the computational comparison, that I think is appropriate and common. As mentioned, the experiments should be performed on standard benchmarks, and if available, on more than one benchmark. Then, the metrics can be:

  • Number of feasible solutions,
  • Number of best found solutions,
  • Number of optimal solutions,
  • Gap to the best found solution,
  • Computational time,
  • LP relaxation bound.

I think the number of constraints and/or variables do not always reveal the superiority of models. Nevertheless, the comparison is very dependent to the size of the inputs when time-index models (models with discretization of the time horizon) are among the comparing models.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Number of constraints is particularly questionable as a criterion. CPLEX allows you to specify "lazy constraints" as part of a model, which add to the model size but I think impact performance less than regular constraints (when nonbinding). Also, modern solvers may use "active set" methods that hold nonbinding constraints off to the side to a significant extent. So a model with a large number of nonbinding constraints may not be as hard to solve as it looks on paper. $\endgroup$
    – prubin ♦
    Aug 20, 2019 at 17:44
2
$\begingroup$

Generally I see on the papers, at first comparison according to number of variables and equations, after then experimental performance comparison on test problems.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ I'm not sure why someone downvoted this. It's arguably not the best way to compare, but I agree that it is somewhat common in papers. $\endgroup$
    – prubin ♦
    Aug 19, 2019 at 20:21
-1
$\begingroup$

It is not really fair to compare formulations with different decision variables because the two models essentially describe different things, hence performance is tied to how well the problem is described. An example would be coarse-graining a problem with say 1000 products into 10 chunks of 100 products to improve runtime. Sure, the second formulation is more powerful (because it's tractable), but it's up to the modeller to determine whether the loss of modelling accuracy is acceptable. Sometimes it will be (and the coarse-grained formulation wins) and sometimes it won't. The same goes for modelling time as a set of integer variables vs one continuous variable.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ But in that case, I wouldn't say the two models actually model the same problem. And yes, then we are comparing apples and bananas $\endgroup$
    – Sune
    Aug 23, 2019 at 16:54
  • $\begingroup$ You are correct, this is what I am trying to convey: once the decision variables change, we are describing something subtly (or even wildly) different. $\endgroup$
    – Nikos Kazazakis
    Aug 23, 2019 at 16:57
  • 3
    $\begingroup$ Take the CVRP as an example: you can model it in at least two different ways, namely using a vehicle flow or a rute based formulation. In the first, the variables describe whether a vehicle traverse a specific arc or not, in the other we decide to use a specific rute or not. However, its the same problem we model $\endgroup$
    – Sune
    Aug 23, 2019 at 17:02

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.