0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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