0

I have a linear programming problem of the form

$\max_{x_1,\ldots,x_N} \mathbf{c}^T\mathbf{x}$
such that

$\mathbf{Ax}\leq \mathbf{b}$ and
($x_{\text{min}}\leq x_i\leq x_{\text{max}}$ or $x_i=0$)

where $x_{\text{max}}, x_{\text{min}} > 0$

So the catch is that I want to allow an interval plus a point value for variables $x_i$

Is this still solvable using standard LP solvers?

Thanks for the help

tenticon
  • 230

1 Answers1

2

This is called a semicontinuous variable and can be modeled with mixed-integer programming (MIP), more specifically as $$z_ix_{min}\leq x_i\leq z_ix_{max}$$ where $z_i$ are binary variables ($z_i\in\{0,1\}$). Most popular LP solvers are also MIP solvers, but you should keep in mind that solving a MIP to optimality is much harder (slower) than solving an LP. Some solvers will also allow you to declare a semicontinuous variable without explicitly declaring the auxiliary binary variable.

https://docs.mosek.com/modeling-cookbook/mio.html#semi-continuous-variables

Michal Adamaszek
  • 4,018