1
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This looks promising! Will try it out and report back $\endgroup$ Commented Nov 16, 2017 at 21:57
  • $\begingroup$ Would you know of a collection or wiki of such lp reformulation tricks ? Thanks $\endgroup$
    – denis
    Commented Jun 5, 2019 at 9:31
  • $\begingroup$ @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.) $\endgroup$
    – jbowman
    Commented Jun 9, 2019 at 17:26
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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