NEED HELP - BENDERS DECOMPOSITION

[Rakesh Reddy]

I am trying to solve a problem using benders decomposition. I problem I have is that the solution in the first iteration is infeasible and I keep getting infeasible solutions. Could someone please help me out.

Here is the code. 

# MEM Problem using Bender's Decomposition

#MEM_BD.mod

##### SUB PROBLEM #####

param m;

param n;

param t;

   

set W := {1..m}; #influencer set

set V:= {1..n}; #follower set

param F{V} <= 0;

param a{W,V} >= 0;

param p{W,V} >= 0;

param b{W,V} <= 0;

param x_b{W} binary; #x_b is x bar which is assumed to be known in the sub problem

var y{V} >=0;

minimize second_level: sum {j in V} F[j]*y[j];

s.t. Constraint_s2 {j in V}:

sum {i in W} p[i,j] * x_b[i] = y[j];

s.t. Constraint_s3 {j in V}:

y[j] >= 1;

##### MASTER PROBLEM #####

param nCUT >= 0 integer;

param cut_type {1..nCUT} symbolic within {"point","ray"};

param C1_cut {V,1..nCUT};# <= 0.000001;

param C2_cut {V,1..nCUT};

var x{W} binary;

var z >= 0;

minimize Total:

sum {i in W, j in V} b[i,j] * a[i,j] * x[i] + z;

 

s.t. Constraint_s1:

sum {i in W} x[i] <= t;

s.t. Cut_Defn {k in 1..nCUT}:

if cut_type[k] = "point" 

then

z >= sum {i in W, j in V} C1_cut[j,k] * p [i,j] * x[i] + sum{j in V} C2_cut[j,k] * 1;

#RUN;

reset;

model MEM_BD.mod;

data MEM_BD.dat;

option omit_zero_rows 1;

option display_eps .000001;

problem Master: x, z, Total, Cut_Defn, Constraint_s1;

   option display_1col 20;

   option solver cplex1, cplex_options '';

problem Sub: Constraint_s2, second_level, y, Constraint_s3;

   option presolve 0;

   option display_1col 0;

   option solver cplex1, cplex_options 'netopt 2 netfind 2';

   

   

let nCUT := 0;

let z := 0;

let {i in W} x_b[i] := 1;

param GAP default Infinity;

suffix dunbdd;

repeat { printf "\nITERATION %d\n\n", nCUT+1;

   solve Sub;

   printf "\n";

   if Sub.result = "infeasible" then {

      let nCUT := nCUT + 1;

      let cut_type[nCUT] := "ray";

      let {j in V} C1_cut[j,nCUT] := Constraint_s2[j].dunbdd;

      let {j in V} C2_cut[j,nCUT] := Constraint_s3[j].dunbdd;

      expand Cut_Defn[nCUT];

      }   

   else {

     let GAP := min (GAP, -second_level + z);

display z;

display second_level;    

     display GAP, y;

      if -second_level < z + 0.00001 then break;

      let nCUT := nCUT + 1;

      let cut_type[nCUT] := "point";

  let {j in V} C1_cut[j,nCUT] := Constraint_s2[j].dual;

      let {j in V} C2_cut[j,nCUT] := Constraint_s3[j].dual;

      }

   

   

   printf "\nRE-SOLVING MASTER PROBLEM\n\n";

   solve Master;

   printf "\n";

   display x;

   let {i in W} x_b[i] := x[i];

};

option display_1col 0;

display x_b, second_level, x, y;   

#MEM_BD.dat

param m := 5;

param n := 25;

param t := 2;

param: F := 

1 -2

2 -26

3 -48

4 -45

5 -30

6 -39

7 -3

8 -21

9 -47

10 0

11 -16

12 -43

13 -35

14 -34

15 -19

16 -16

17 -40

18 -35

19 -38

20 -43

21 -26

22 -42

23 -27

24 -33

25 -41;

param a: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25:=

1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1

2 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1

3 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0

4 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0

5 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0;

param b: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25:=

1 -0 -5 -0 -8 -10 -0 -0 -6 -6 -0 -1 -1 -1 -0 -0 -0 -7 -0 -0 -11 -0 -0 -8 -5 -9

2 -6 -0 -0 -0 -6 -0 -5 -0 -8 -11 -2 -9 -8 -0 -4 -0 -0 -3 -9 -10 -0 -0 -13 -8 -6

3 -2 -3 -7 -1 -3 -5 -5 -7 -3 -11 -7 -7 -1 -13 -7 -7 -8 -11 -8 -2 -14 -5 -7 -15 -5

4 -11 -5 -3 -7 -8 -2 -1 -6 -4 -14 -15 -9 -4 -3 -7 -8 -7 -13 -13 -4 -3 -14 -5 -10 -13

5 -8 -5 -9 -1 -13 -3 -3 -10 -11 -9 -14 -1 -2 -14 -2 -13 -1 -14 -4 -13 -1 -5 -1 -4 -7;

param p: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25:=

1 0.1 0.1 0.1 0.1 0.1 0 0 0.1 0.1 0.1 0.1 0 0 0.1 0.1 0 0.1 0 0.1 0.1 0.2 0.2 0.2 0 0.2

2 0 0.1 0.1 0.1 0 0 0.1 0.1 0.1 0 0 0.1 0 0 0 0.1 0.1 0.1 0.1 0 0.2 0.2 0.2 0 0.2

3 0 0.1 0 0 0 0.1 0 0.1 0 0 0.1 0 0.1 0 0 0 0 0.1 0.1 0 0 0 0.2 0 0

4 0.9 0.2 0 0.1 0.1 0 0.1 0.1 0 0.1 0 0.1 0.1 0.1 0.1 0 0 0 0 0 0 0 0 0.2 0

5 0.9 0.9 0 0 0 0.1 0 0.1 0.1 0.1 0 0.1 0 0.1 0 0 0 0 0 0.1 0.2 0.2 0 0.2 0;

[Robert Fourer]

You are already executing "expand Cut_Defn[nCUT];" so you can examine the cuts that are being generated, to see if they are sensible. The first cut should be a feasibility cut, and it can happen that several feasibility cuts are generated before the subproblem becomes feasible. If the same feasibility cut is generated more than once then there is an error in the model or the logic of the decomposition script.

(Of course the master problem should be feasible since if it is not feasible to begin with, adding cuts will never make it feasible.)

Bob Fourer
am...@googlegroups.com

=======