# Linear programming with variables in piecewise intervals

Problem: I am working on a linear programming problem, i.e. a linear objective function to minimize:

$\mathbf{c}\cdot\mathbf{x}$,
where $\mathbf{c},\mathbf{x}\in\mathbb{R}^{N}$

Subject to constraints:

$\mathbf{x}\geq 0$ and $\mathbf{A}\mathbf{x} \leq \mathbf{b}$ where $\mathbf{A}\in\mathbb{R}^{MxN}$ and $\mathbf{b}\in\mathbb{R}^{M}$

I am using CyLP and the COIN-OR simplex solver to perform the optimization.

Question: A feature I would like to be able to build into the problem is the ability to handle some atypical constraints:

Suppose $x_{i}$ is a component of $\mathbf{x}$. I want to apply the following constraints:

$x_{i} = 0$ or $\mathrm{lb} \leq x_{i} \leq \mathrm{ub}$.

In geometric terms, I want $x_{i}\in [0]\cup [\mathrm{lb}, \mathrm{ub}]$. Unlike the original problem, where all $x_{i}$ are bounded within convex sets (i.e. non-piecewise intervals).

Is there a good way to modify an LP for the above atypical constraint?

Apologies if my usage of "convex" is confusing or erroneous.

For each $x_i$ with a constraint like your special one, create an additional binary variable $z_i$. Set the objective function coefficient for $z_i = 0$ (i.e., leave it out of the objective function.) Rewrite the constraints for $x_i$ as (in canonical $\leq$ form):

$$x_i - \text{ub}_iz_i \leq 0$$ $$-x_i +\text{lb}_iz_i \leq 0$$

If $z_i = 1$, then you have $x_i \leq \text{ub}_i$ and $-x_i \leq -\text{lb}_i$, the latter of which is evidently equivalent to $x_i \geq \text{lb}_i$, which, combined, give you $x_i \in [\text{lb}_i, \text{ub}_i]$.

If $z_i = 0$, you have $x_i \leq 0$ and $-x_i \leq 0$, which is evidently satisfied only for $x_i = 0$.

• This looks promising! Will try it out and report back Commented Nov 16, 2017 at 21:57
• Would you know of a collection or wiki of such lp reformulation tricks ? Thanks Commented Jun 5, 2019 at 9:31
• @denis - wouldn't that be nice... unfortunately not. It's an excellent idea, though, if someone else hasn't already done it (and I couldn't find the link to it.) Commented Jun 9, 2019 at 17:26

I see two possible approaches.

(1)

You can solve the quadratic programming problem:

Minimize: $$\bf{c \cdot b \cdot x}$$ such that $$\bf{A x \le b}$$ and $$\text{lb} \le \textbf{x} \le \text{ub}.$$

In this case, $\bf x$ and $\bf b$ are the variables to be optimized and everything else is constant. $\bf x$ is continuous and $\bf b$ is binary.

The standard form of the objective function in QP is, $$\frac{1}{2} z^T Q z + c^T z,$$

where $z$ is the $n \times 1$ vector to be optimized, $Q$ is a constant $n \times n$ matrix and $c$ is a constant $n \times 1$ vector. Because you only have quadratic terms, $c$ is zero. Let $z = \{x, b\}$ where the continuous vector $x$ has $n/2$ elements and the binary vector, $b$ has $n/2$ elements as well. The block matrix form of $Q$ is then, $$\bf Q = \begin{bmatrix} \bf 0 & \bf q \\ \bf 0 & \bf 0 \end{bmatrix}$$ where $\bf 0$ is an $n/2 \times n/2$ matrix of all zeros, and $\textbf{q} = \text{diag}( q_1, q_2, \dots, q_{n/2} )$ are the constants (corresponding to your $\bf c$). This ensures that the objective function has the same form as the one I wrote at the beginning.

(2)

You can solve the linear programming problem with mixed continuous and binary variables:

Minimize: $$\textbf{c} \cdot (\textbf{x} - \text{ub} \times \textbf{b})$$ where, again, $\bf x$ is continuous and $\bf b$ is binary. You use the same constraints as before, however, you add the following additional $n/2$ constraints to the matrix $\bf A$: $$x_i - \text{ub} \times b_i \ge 0.$$ This constraint ensures that if $b_i = 1$ then $x_i = \text{ub}$ so that, as desired, the $i'$th component of the objective function contributes $0.$ Otherwise, if $b_i = 0$ then $x_i \in [\text{lb}, \text{ub}]$ as desired. (I'm assuming $\text{lb} > 0.$ Otherwise, if the bounds are negative, then fix the constraint accordingly.)