quasi
Posts:
11,718
Registered:
7/15/05


Re: disjunctive constraints in integer linear programming
Posted:
Apr 12, 2013 1:39 AM


d.info.sign wrote: >quasi wrote: >> d.info.sign wrote: >> > >> >I have an integer linear programming problem as follows: >> > >> >The constraints are either >> > >> >x >= 0 >> >y = u >> >z = x + v >> > >> >or >> > >> >x < 0 >> >y = u  x >> >z = v >> > >> >where y, z, u, v range over nonnegative integers. >> > >> >There are other unrelated constraints associated with >> >u, v, y, z. >> > >> >What's the most simple way to encode the disjunctive case? >> >>Why not just run two separate linear programs and choose >>whichever of the two optimal solutions offers a better value >>for the objective function? > >Unfortunately we can't. This form of constraints occur often >in our system. The approach you suggested would lead to >exponential enumeration.
Why would there be exponential explosion? I see times 2, nothing more.
Can you give a complete example with all variables, constraints and the objective function specified?
quasi

