Complexity Measures for Mathematical Programming

Question

Question:

Are there any complexity measures in use, that allow one to compare mathematical programming formulations of optimization problems on basis of the number of variables that must be subjected to specific integrality or linearity constraints?
To be more specific, I would be interested in how the number of integer variables grows with the size of a problem and also how the number the other types of variables e.g. continuous or bilinear, grows.

From a theoretical point of view, a formulation with fewer integer or bilinear variables would be better, whereas from a practical point of view, the tradeoff may be more interesting.

The restrictive must be for integer or bilinear variables was used to emphasise that the computationally least "expensive" sufficient type of variables has to be assumed in counting the types; totally unimodular problems yield integer solutions without having to constrain any variables to be integral, the same is true for the primal-dual algorithm for matching problems, so for those problems the count for integer variables would have to be zero.

I am hesitant to using the "algorithms" tag, because what I am looking for, is not related to executing a sequence of operations or decisions; "complexity" also doesn't quite seem fit, neither in the temporal nor in the spatial sense.

Answer 1

In both theory and practice, the quality of LP-relaxations of a Mixed Integer Linear Program (i.e., the quality of the polyhedron of the LP-relaxation) is the most important factor when comparing different mathematical programming formulations. In other words, the LP bounds should be as close as possible to the optimal value of the original problem. In practice, however, the quality of the coefficient matrix of LP (which is a function of the number of variables and constraints, as well as the number of non-zero elements) also affects the solution time.

The number of variables (whether continuous or integer) and the number of constraints are not very important. As a classical example in integer programming, we can consider the travelling salesman problem for which there are two well-known formulations (of course there are more formulations but these two are often mentioned). One with a poly number of constraints (MTZ formulation) and the other one with expo number of constraints (DFJ formulation). The DFJ formulation is considered as the stronger formulation because it provides us with better LP relaxations.

Edit: There are a number of good textbooks, but I use the most recent one as a reference.

Integer programming (textbook by Giacomo Zambelli, Gérard Cornuéjols, and Michele Conforti, 2014):

Assume that $\{(x,y): A_1x+G_1y \le b_1, x\ \ {integral}\}$ and $\{(x,y): A_2x+G_2y \le b_2, x\ \ {integral}\}$ represent the same mixed integer set $S$ and consider their linear relaxations $P_1=\{(x,y): A_1x+G_1y \le b_1\}$ and $P_2=\{(x,y): A_2x+G_2y \le b_2\}$. If $P_1 \subset P_2$ the first representation is better. If $P_1 = P_2$ the two representations are equivalent and if $P_1 \setminus P_2$ and $P_2 \setminus P_1$ are both nonempty, the two representations are incomparable.

It is noteworthy to say that before presenting this definition, the authors mention that

the question Which of the two formulations is “better”? has great computational relevance and the answer depends on the method used to solve the problem. In this book we focus on algorithms based on linear programming relaxations (remember Sect. 1.2) and for these algorithms, the answer can be stated as follows $\cdots$

All the theoretical papers I myself have seen use the above criteria.