# When is a formulation with min function an ILP problem?

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 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. Commented Oct 18, 2021 at 0:55

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

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)