icedagecs

Answered

2022-06-30

Sign of a Linear Expression in Mixed Integer Linear Programming

I have a question about a system in mixed integer programming I am trying to solve using GLPK though the question mathematical and is software agnostic.

I have converted the whole problem to linear equations and inequalities except for one part. Suppose I have a real number $x$ and a binary variable $b$ (either 0 or 1). How can I "tie them together" such that $x>0$ if and only if $b=1$?

I have a question about a system in mixed integer programming I am trying to solve using GLPK though the question mathematical and is software agnostic.

I have converted the whole problem to linear equations and inequalities except for one part. Suppose I have a real number $x$ and a binary variable $b$ (either 0 or 1). How can I "tie them together" such that $x>0$ if and only if $b=1$?

Answer & Explanation

Ordettyreomqu

Expert

2022-07-01Added 22 answers

$0.001b\le x\le Ub$

where I assume $0\le x\le U$.

I don't see how this particular formulation is related to NP-completeness. If you are worried about the complexity of this don't use a MIP model at all but rather use a heuristic (even this may be overstating things as state-of-the-art MIP solvers actually use lots of heuristics internally).

where I assume $0\le x\le U$.

I don't see how this particular formulation is related to NP-completeness. If you are worried about the complexity of this don't use a MIP model at all but rather use a heuristic (even this may be overstating things as state-of-the-art MIP solvers actually use lots of heuristics internally).

Most Popular Questions