When is a formulation with min function an ILP problem?

Question

Consider a simple formulation like the one below. \begin{align} \max&\quad\sum_i x_i\\ \text{s.t.}&\quad x_i \leq \underset{\forall j<i}{\text{min}}\ f(x_j) \end{align}

I am just wondering if I can consider such formulation an ILP problem.

I intentionally kept things undefined to understand if this is general. Hope it sounds.

Because you are using min (which is a concave function of affine (linear) arguments) in a convexity preserving fashion, @RobPratt 's answer applies. If the inequality constraint were in the other direction ($\ge$ rather than $\le$ ), the min would appear in a non-convex fashion, and that would require binary (integer) variables to model; hence trinng what would otherwise be an LP into an ILP. Details: Concave expression $ \ge$ affine (linear) expression is a convex constraint. Concave expression $ \le$ affine (linear) expression is a non-convex constraint. — Mark L. Stone, Oct 18 '21 at 00:55

score 11 · Accepted Answer · answered Oct 17 '21 at 18:16

11

Your constraint is equivalent to $$x_i \le f(x_j) \quad \text{for $j<i$},$$ so it is linear if $f$ is linear.

answered Oct 17 '21 at 18:16

RobPratt

32,006
1
44
84

score 3 · Answer 2 · answered Oct 18 '21 at 15:42

Extending Robs answer slightly, taking into account that you asked about ILP (which I interpret as mixed-integer linear program), the constraint is MILP-representable as long as $f$ is MILP-representable (thus allowing you to have piecewise affine functions such as min/max/abs/general pwa etc)

When is a formulation with min function an ILP problem?

2 Answers2