5
$\begingroup$

I am working with a standard linear program:

$$\text{min}\:\:f'x$$ $$s.t.\:\:Ax = b$$ $$x ≥ 0$$

Goal: I want to enforce all nonzero solutions $x_i\in$ x to be greater than or equal to a certain threshold "k" if it's nonzero. In other words, I want to add a conditional bound to the LP: if any $x_i$ is > 0, enforce $x_i$ ≥ k.

Main issue: Is there a way to set up this problem as an LP? Any alternate approaches? Any input would be appreciated and I'm happy to provide any additional info as needed! Thanks!

$\endgroup$
  • 3
    $\begingroup$ This is not possible in linear programming. If you consider $k=1$ and add another linear constraint $x\le1$, the problem becomes $0$-$1$ integer linear programming, which is NP-hard. $\endgroup$ – Rahul Mar 20 '15 at 18:28
  • $\begingroup$ A constraint like that is no longer linear, so it cannot be formulated as a linear program (of any kind). $\endgroup$ – TravisJ Mar 20 '15 at 18:33
  • $\begingroup$ @TravisJ no. An ILP is not an LP, but an LP is an ILP. $\endgroup$ – Michael Grant Mar 20 '15 at 19:14
  • 1
    $\begingroup$ Linear programs permit linear objectives and linear equations and inequality constraints---and that's it. Integer linear programs allow all of these, plus integrality constraints on the variables. It is a larger modeling space. And as you rightly point out, models with integer constraints cannot be solved with standard LP machinery (simplex or interior-point methods). $\endgroup$ – Michael Grant Mar 20 '15 at 19:39
  • 1
    $\begingroup$ I just realized that... My understanding was that an LP had linear objective + linear constraints (which is correct). However, adding the integer constraint is not linear. $\endgroup$ – TravisJ Mar 20 '15 at 19:40
5
$\begingroup$

This cannot be solved with linear programming, but it can be solved with mixed-integer linear programming (MILP). What you are looking for is something called a semicontinuous variable in the MILP community. A semicontinuous variable $x$ is constrained to the disjoint set $$x\in\{0\}\cup[\ell,u] \qquad\text{or}\qquad x\in\{0\}\cup[\ell,+\infty),$$ where $0<\ell<u$.

This kind of construct occurs commonly in practice. For example, consider a portfolio design problem in which a particular investment can only be purchased if you are willing to allocate a certain minimum amount to it---say, 10K USD. Any amount above that minimum is permissible: so 9.9K is not acceptable, but 10.1K and 100K are. This kind of constraint is naturally modeled with a semicontinuous variable.

Many MILP solvers such as CPLEX, Gurobi, and even lp_solve handle them explicitly. The method for specifying semicontinuity and the bounds $\ell,u$ depend on the specific solver, so you'll need to consult the documentation for the solver of your choice.

With solvers like, say, MOSEK that do not specifically handle semicontinuity, the case with the upper-bound is readily handled with the pair of inequalities $$\ell z\leq x \leq u z$$ where $z\in\{0,1\}$ is an additional binary variable. If you don't have an upper bound, then you must take ChrKroer's approach and select an arbitrary one. Try not to make it any larger than necessary to preserve the solution set.

As you can see, the advantage to handling semicontinuity explicitly is that it can handle the $u=\infty$ case. Computationally both introduce a single branch into the problem, so I suspect there is no consistent performance benefit to one or the other, but I do not have the experience to say for sure.

Google searches for "semicontinuous variables" or "semi-continuous variables" turn up a wealth of useful results. There is also the notion of a semi-integer variable: as its name implies, it combines a semicontinuous constraint with an integrality constraint.

$\endgroup$
4
$\begingroup$

Like Rahul mentioned in a comment to your question, this is not possible (incidentally, I do not agree with TravisJ's comment that an ILP is a special case of an LP. Rather, an LP is a special case of a mixed-integer linear program, of which integer-linear programming is also a special case. But I do not have enough points to comment yet). However, all is not necessarily lost.

If your goal is to solve some practical problem (rather than showing that this can be solved through linear programming), modeling your problem as a mixed-integer linear program and solving that instead might actually work. Solvers such as CPLEX and Gurobi are surprisingly fast.

If you have some a priori upper bound $M_i$ on each $x_i$, you could do the following: for each $x_i$, you can introduce a boolean variable $b_i$ and have the constraints:

$x_i\geq k\cdot b_i$, $x_i \leq M_i\cdot b_i$.

$\endgroup$
  • 1
    $\begingroup$ ... except that you need an a priori bound $M$ for $x_i$. If you don't have that, you could make $b_i$ an integer variable instead, and then have $x_i \le 2 k b_i$ instead of $x_i \le M b_i$. $\endgroup$ – Robert Israel Mar 20 '15 at 18:56
  • $\begingroup$ Yes, that is true. I added that to my explanation. Your solution could lead to more branching, does it usually lead to worse practical performance in your experience? $\endgroup$ – ChrKroer Mar 20 '15 at 19:15

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.