Example of stronger programming formulation.

Question

So I was revising the course combinatorial optimization and I find the statement $$P_1 \text{ is a stronger formulation than } P_2 \text{ if } P_1 \subset P_2. $$ Can someone give me an example of two formulations for which one is stronger than the other? And why is it usefull?

Answer 1

As you already said, by definition, a formulation $P_1$ is stronger than a formulation $P_2$ if $P_1\subset P_2$.

• why it is useful?

Because a strong formulation yields a better lower bound (for minimization problems). Ideally, we are looking for a formulation $P$ which is equal to the convex hull of the feasible solutions. (Unfortunately, we could not do that in all cases.)

Refer to the following figure (which I get from Farkas' lemma, projection of PP, comparing formulations, (dis)aggregated formulation(s), sharp formulation, convex hull).

In this picture, the set $S$ represents the set of feasible solutions and $P_3$ is the convex hull of $S$. All others $P_1$, $P_2$ and $P_4$ are alternative formulations of $S$.

You can see that $P_1$ is better (stronger) than $P_4$ because $P_1$ is contained in $P_4$. Obviously, you can see why it is useful? In some sense, we get close the convex hull of $S$. And, indeed, $P_3$ is the strongest formulation for $S$.

• Can someone give me an example of two formulations for which one is stronger than the other?

You can refer to the PDF above that I attach to find simple examples of such formulations. I remember one good example myself which is about the facility location problem. Here is two formulations:

\begin{align}\tag{$E_1$} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum_{j=1}^nc_jy_j+\sum_{i=1}^m\sum_{j=1}^nd_{ij}x_{ij}\\ & \text{subject to} & & \sum_{j=1}^nx_{ij}=1, \forall\, i,\\ & & & x_{ij} \leqslant y_j, \forall\,i,j,\\ & & & x_{ ij }, y_j \in\{0, 1\}, \forall\,i,j. \end{align} and \begin{align}\tag{$E_2$} & {\underset{\mathbf{ x }, \mathbf{ y }}{\text{minimize}}} & & \sum_{j=1}^nc_jy_j+\sum_{i=1}^m\sum_{j=1}^nd_{ij}x_{ij}\\ & \text{subject to} & & \sum_{j=1}^nx_{ij}=1, \forall\, i,\\ & & & \sum_{i=1}^m x_{ij} \leqslant m y_j, \forall\,j,\\ & & & x_{ ij }, y_j \in\{0, 1\}, \forall\,i,j. \end{align}

Denote the formulation of $(E_1)$ and $(E_2)$ by $P_1$ and $P_2$, respectively.

You can easily see that $P_1\subseteq P_2$. Why? Because given $x_{ij}\leqslant y_j$, you can sum over $m$ to get $\sum_{i=1}^m x_{ij} \leqslant m y_j.$ Hence $P_1$ is at least as strong as $P_2$. To prove that $P_1$ is stronger than $P_2$, it remains to show that the inclusion is strict. Find a point $(\mathbf{x}, \mathbf{y})$ in $P_2\backslash P_1$. Finally, $P_1\subset P_2$ and $P_1$ is a better formulation for the facility location problem than $P_2$. (Even though, $P_1$ has more constraints than $P_2$.)

Answer 2

Usually in combinatorial optimization, for example in integer linear programming, we want to relax the feasible set such that the problem become easier, such as relax it to a linear programming problem.

The feasible set become larger that way. If the relaxed feasible set is too large, the approximation become crude. Hence we want the relaxation to be small.

For example, you want to maximize $x$ such that $x \in P$ where $P=\{x: x<=11.5, x \in \mathbb{Z} \}$

Suppose we relax the integer criteria and solve the problem of maximize $x$ such that $x \in Q$, $Q=\{x: x<=11.5 \}$, then the optimal solution is $11.5$ for this relaxed problem.

In contrast, if we further realize that there is no integer solution between $11$ and $11.5$ and solve the problem of maximize $x$ such that $x \in R$, $R=\{x: x<=11 \}$, then the optimal solution is $11$ for this relaxed problem. We can see that the solution is in fact closer to the original solution of the original problem, in fact they are equal.