Valid Inequalities and Strong Inequalities

Question

Consider the following mixed-integer set: \begin{equation} P(A, b ; S) \stackrel{\text { def }}{=}\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\} \end{equation}

where $A$ is a real $m \times n$ matrix $, b \in \mathbb{R}^{m}, S \subseteq\{1, \ldots, n\}$.

A valid inequality (in an LP/MIP) is defined as an inequality that is valid for some set if all points from this set satisfy this inequality. Let the inequalities $a^\top x \leq u$ and $\alpha^\top x \leq v$ hold for all points in $P(A, b ; S)$.

It is said that the inequality $a^\top x \leq u$ is stronger than the inequality $\alpha^\top x \leq v$ (or the inequality $a^\top x \leq u$ dominates the inequality $\alpha^\top x \leq v$) if

$$ P(A, b) \cap H_{ \leq}(a, u) \subset P(A, b) \cap H_{ \leq}(\alpha, v). $$ AFAIK, valid inequalities appear in the cutting planes method (please, correct me if I'm wrong). Indeed, many optimization models have their own definition such that sets, data and constraints have been interpreted with regards to the real limitations of the problem (for instance, in many cases a capacity constraint is written as $A x \leq b$ and it seems that it works fine in the real situation).

According to the mentioned definition, what are your thoughts on the following questions:

• What exactly does "valid inequality" mean?
• What does "Strong Inequalities" mean?
• How can we find them in our optimization model or replace the constraints of the model with whose valid?
• How can I figure out whether one inequality is stronger than other (especially in the scheduling models)?

Answer 1

Usually in the context of LP/MIP you make statements about the convex hull of the mixed-integer set that you defined $P = \text{conv}(\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\})$. Branch-and-bound techniques work by relaxing the integrality constraint and compute lower bounds of the problem (when you minimize). The problem is to find a compact representation of the convex hull of the feasible (mixed-)integer points. Cutting planes are valid inequalities that are valid for the convex hull of the feasible points which try to remove some part of the relaxed set $\tilde{P}=\left\{x \in \mathbb{R}^{n} : A x \leq b\right\}$. Ideally you want to have facet defining inequalities for $P$.

A face $F\subseteq P$ is a subset of a polyhedron $P$ if there exists a valid inequality $a^Tx\leq \alpha$ for $P$ such that $F=\left\{x\in P \mid a^\top x = \alpha \right\}$.
A facet $F$ is an inclusion-wise maximal face of $P$ (while $\emptyset\neq F\neq P$). Note that, equivalently, a facet is a nonempty face of $P$ with dimension $\text{dim}(P)-1$.
Taken from Grötschel, Lovasz, Schrijver - Geometric Algorithms and Combinatorial Optimization.

What exactly does "valid inequality" mean?

You already give a definition which is correct. You could write a bit more mathematically that an inequality $a^\top x \leq $ is valid for a polyhedron $P$ if $P\subseteq \left\{x\in\mathbb{R}^n \mid a^\top x \leq u \right\}$ which means that the polyhedron $P$ is included in the halfspace defined by the inequality.
Note that a valid inequality does not necessarily need to cut off non-integral points. In fact a inequality can be valid for a polyhedron does not even to have a nonempty intersection between the induced hyperplane and the polyhedron.

What does "Strong Inequalities" mean?

Again, you already give a definition. A valid inequality is stronger than another (or dominates it) if the induced halfspace intersected with the polyhedron is included in the halfspace (intersected with the polyhedron) induced by the other one.

As I've written in the introduction paragraph, facets are the inequalities that are inclusion-wise maximal. If you are able to find facets for your problem it is a very good thing as these inequalities cannot be dominated by other inequalities.

How can we find them in our optimization model or replace the constraints of the model with whose valid?

There are many investigations about the structure of the underlying polyhedron for different problems. Sometimes it is possible to find (and prove) facet inducing inequalities and in some cases one is even able to state the precise description of the convex hull of the (mixed-)integer points. Some examples for well-known polyhedrons are the (perfect) matching polytope, cut polytope, boolean quadric polytope and many more...

Besides analysis by hand (or rather brain) there exist software packages (e.g. polymake) that can compute facets of (small instances) of polyhedrons. If you are lucky you can generalize these to make statements about the polyhedron.

Answer 2

What exactly does "valid inequality" mean?

Valid Inequalities are constraints that reduce your feasible space without removing integer solutions. In other words, Valid Inequalities approximate your feasible space to the integer convex hull.

What does "Strong Inequalities" mean?

There are many Valid Inequalities and the best of them are called Strong Valid Inequalities. In this case, there is no any Valid Inequality dominate a Strong Valid Inequality. To clarify, Strong Valid Inequality is a non-dominated Valid Inequality.

How can we find them in our optimization model or replace the constraints of the model with whose valid?

For a generic MIP, my suggestion is Gomory¹. But you can read about cover cuts applied to the knapsack problem.

How can I figure out whether one inequality is stronger than other (especially in the scheduling models)?

You need to analyze many papers about your scheduling problem version. After that, you need to study the ideas of the main papers to ​​adapt good ideas or to take an original idea. For example, check out this paper² on Strong Valid Inequalities.

---

_References

_{[1] Gomory, R. (1958). Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society. 64(5):275-278.}

_{[2] Hardin, J. R., Nemhauser, G. L., Savelsbergh, M. (2008). Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements. Discrete Optimization. 5(1):19-35.}