CODEWITHSUNDEEP
matlablinear-programmingcplexlpsolve
user3216838
user3216838

Reputation: 1

how to solve integer linear programming when one of the variables belong to a set

I am working on solving optimization problems using integer linear programming, one of the constraints assume that the variable has a value belongs to a set of values like the following

 min 5*x1 + 2*x2
 s.t.
 x1,x2>0
 x1 in {2,4,-5}

how i can represent this problem to solve it using CPLEX or lp_solve in matlab? what are the values of F,A,b arrays?

Thanks

Upvotes: 0

Views: 792

Answers (1)

Ben Voigt
Ben Voigt

Reputation: 283901

You can rewrite a problem where an integer variable takes on a finite discontiguous set of possible integral values as a binary program in more variables. Just write:

2 * b1 + 4 * b2 -5 * b3 - x1 = 0
b1 + b2 + b3 = 1

with b1, b2, b3 constrained as binary. That might be directly supported, or else expressed as

b1, b2, b3 integer
0 <= b1, b2, b3 <= 1

In case you aren't allowed equality constraints, remember that a pair of inequality constraints is equivalent.

 Ax = b;

is the same as

 Ax <= b
-Ax <- -b

But the solution set still has no interior, so interior point methods can't work. You can relax that by:

 Ax - e <= b
-Ax - e <= -b

and minimize e using your objective function.

Upvotes: 1

Related Questions