2
$\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?

$\endgroup$

1 Answer 1

1
$\begingroup$

Sorry, this cannot be done with a continuous LP solver. As you observed, this construct introduces a non-convexity. However, it can be handled by a Mixed Integer Programming (MIP) solver.

$x=0$ or $\ell\le x\le u$ is what is known as a semi-continuous variable. Many advanced MIP solvers support this variable type directly.

If a MIP solver does not support this, we can introduce a binary variable $\delta \in \{0,1\}$ and use the constraint:

$$ \ell \cdot \delta \le x \le u \cdot \delta $$

to simulate a semi-continuous variable.

COIN-OR has a capable MIP solver called CBC (I believe it supports semi-continuous variables directly).

$\endgroup$
0

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.