4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 18 at 0:55
10
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.