In a linear program, how to add a conditional bound to x?

Question

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!

Answer 1

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$.

Answer 2

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.