Originally posted by: prasenjit mandal
I am able to figure out what are cuts cplex itself is generating over different nodes.
But, I have questions regarding this.
1) Suppose, I try to solve a simple binary knapsack problem
max 4x1+6x2+5x3
s.t. 3x1+8x2+5x3 <=9
x1,x2,x3 are binary
At root node, CPLEX runs the following LP relaxation problem:
max 4x1+6x2+5x3
s.t. 3x1+8x2+5x3 <=9
3x1+5x3 -x4 =0
0=<x1<=1
0=<x2<=1
0=<x3<=1
0=<x4<=8
Now, from where this new variable x4 comes into picture? What is significance of 3x1+5x3 -x4 =0 ??What I am assuming cplex intelligently generates cover inequality and lifts it. It looks like 3x1+5x3 -x4 =0. Ultimately, it boils down to the valid inequality 3x1+5x3 <=8. Is it correct what I am assuming?
However, when I am retrieving the cuts using a CPLEX Callable Library program (C program), can I get to know what kinds of cuts (whether it is cover or lift-and-project cover or clique etc.) are these? Can I get more information about each node??
2) Then, I ran another knapsack problem:
Maximize
obj: 79 x1 + 70 x2 + 61 x3 + 52 x4
Subject To
c1: 35 x1 + 51 x2 + 67 x3 + 100 x4 <= 150
x1, x2, x3, x4 are binary
The original optimal objective function value is 149 (if you solve "Problem.lp", you will get the objective function value is 149 and solution is [1,1,0,0]). I retrieved the CPLEX-generated cuts from each node. Then, I tried to solve each and every LP file (i.e., the relaxed LP programming formulation for a node) that the C program returns.
Firstly, none of the single node returns me the value of 149. For example,at node indexed by 6, CPLEX runs the following LP relaxation problem:
Maximize
obj: 79 x1 + 70 x2 + 61 x3 + 52 x4
Subject To
c1: 35 x1 + 51 x2 + 67 x3 + 83 x4 <= 118
c2: 3 x2 + 4 x4 - x5 = 0
v0: x2 + x3 <= 1
i1: x3 + 0.25 x5 <= 1
Bounds
x1 = 1
x2 = 0
x3 = 1
x4 = 0
x5 = 0
If I solve it, I get a different solution (nothing but a feasible solution to the problem, where objective function value is 140 and solution is [1,0,1,0]). Why it is like that? Why I am not getting the objective function value 140 and corresponding solution [1,1,0,0] by solving any of the linear programs retrieved from those nodes?
Any help will be highly appreciated.
#CPLEXOptimizers#DecisionOptimization