Nonconvex Region Modelling¶

Definition¶

Nonconvex region modelling represents a union of allowed regions using binary variables that select which region's inequalities are enforced. The selected region must satisfy all its defining inequalities; common constraints remain active for every selection.

Interpretation¶

Some models allow decisions in one of several separate pieces, but not in between. A single system of linear inequalities cannot describe such a region exactly: if two points satisfy a linear inequality, so does every point on the segment between them, so a gap can never be cut out. Binary switches make it possible by enforcing the inequalities of one piece at a time.

Two separate shaded pieces of a feasible region, below x2 = 1 and above x2 = 2 under a shared line x1 + x2 = 3, with the gap between them excluded; their union is not convex.

The two pieces share $x_1+x_2\le3$ and $\boldsymbol{x}\ge\boldsymbol{0}$ but differ in one inequality: $x_2\le1$ below and $x_2\ge2$ above. The points $(0,1)$ and $(0,2)$ are both allowed, while their midpoint $(0,1.5)$ lies in the excluded gap $1<x_2<2$ $2$ . This is what nonconvex means: a segment between allowed points leaves the region.

In the model of the Examples, $y$ selects the piece, each inequality that belongs to only one piece receives a big- $M$ term as in either-or constraints, and the shared restrictions stay outside the switches so that they hold for both choices. With more than two pieces, one indicator per piece and an exactly-one constraint do the selection.

The size of $M$ matters. If it is too small, a switched-off inequality still cuts off allowed points: with $M=1$ and $y=0$ $0$ , the second inequality becomes $x_2\ge1$ $1$ , which together with $x_2\le1$ leaves only the points of the lower piece with $x_2=1$ $1$ . A much larger $M$ than needed is valid but enlarges the region of the LP relaxation, so its bound can only become weaker.

Key Results¶

Use one indicator per region and require exactly one selected region. With only two regions a single binary $y$ suffices: $1-y$ and $y$ act as the two indicators.
Relax every inequality belonging only to an unselected region with a valid big- $M$ constant, as in either-or constraints: $M$ must be large enough that the relaxed inequality cuts off no point the model allows.
Keep nonnegativity and shared boundaries outside the switches.

Examples¶

The illustrated region, the course video example, is $x_1,x_2\ge0$ $0$ , $x_1+x_2\le3$ $3$ , with either $x_2\le1$ or $x_2\ge2$ $2$ . Its switch is $x_2\le1+My$ $M y$ , $x_2\ge2-M(1-y)$ $y)$ , $y\in\{0,1\}$ ${0, 1}$ . With $y=0$ the lower piece $x_2\le1$ is enforced and the second inequality becomes $x_2\ge2-M$ $M$ ; with $y=1$ the upper piece $x_2\ge2$ is enforced and the first becomes $x_2\le1+M$ $M$ . Because $0\le x_2\le3$ on the shared region, $M=2$ is already large enough. The common restrictions $x_1+x_2\le3$ and $\boldsymbol{x}\ge\boldsymbol{0}$ remain active for both choices.

The practice region additionally selects $x_1\in[0,1]$ $[0, 1]$ , $[2,3]$ , or $[4,5]$ under $2x_1+5x_2\le20$ $20$ .

Prerequisites¶

Mixed Integer Program

Sources¶

OR Modelling · Week 3

Symbols: element of

Last updated: 20 October 2026 03:02