Mfcttrf

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?

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.

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.

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.

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