Generating valid inequalities to describe the convex hull of a set

285 Views Asked by At

How to generate the valid inequalities needed to describe the below sets' convex hull?

S := {(x, y) : x + y ≥ b, x ≥ 0 integer, y ≥ 0}

S := {(x, y) : x + y ≥ b, x ≥ d integer}

What are the general guidelines to follow in such cases?

1

There are 1 best solutions below

0
On

The general guideline for two variables is to plot the region.

Because $b$ is not integer, the convex hull of the first one is slightly more complicated than in the comment from @Kavi; there is one more inequality related to $(x,y)=(\lfloor b \rfloor, b - \lfloor b \rfloor)$ and $(x,y)=(\lceil b \rceil, 0)$.

The second one has a couple of cases depending on $b \le d$ or $b > d$.