zero dual variables for +ve primal objective

[enhany75]

I am applying Benders decomposition that solves the primal of the sub-problem. The objective function of this primal sub-problem is +ve value and all the dual variables, given by AMPL, are zeros. How this could be possible?

If you run this files, you will find the primal sub-problem is solved with an objective value equals 12. I asked AMPL to display the dual variables associated with the constraints of this primal and it gives me zeros.

Here is the model file

-----------------------------------------------------------------------------------------------------------------------------------

#parameters

param num_attributes_plus1;

param num_attributes;

param double_num_attributes;

param num_observations;

param step default 1;

param start default 1;

set nols := 1..10000;

set nols2 := 1..10000;

param M_Pos default 0; # number of +ve opservations

param M_Neg default 0; # number of -ve opservations

# sets

set N = start .. num_attributes by step; # set of attributes

set S = start .. num_observations by step;# set of observations

set NN = start .. double_num_attributes by step; # double the set of attributes

set S_dot;

set S_dot_bar;

set N1= start .. num_attributes_plus1; # set of attributes +1 column

param a{S,N1} binary;

param c{S} default 0; # = 0 if the +ve observation is not covered, =1 if the +ve observation is covered

param dual_coverage_pos {nols2};

param dual_a_pos{S, nols2};

param dual_y_pos{S, nols2};

param nsoln default 0;

param nsoln2 default 0;

param x_inf{nols,NN};

### variables

var d integer; # degree of the generated pattern

var x{NN} binary;

var y{S} >= 0, integer;

var Gamma;

# Master problem-positive pattern generation

minimize Benders_master : Gamma ;

# Note, in the binarized data, the entity a(i,1) is reserved to show whether observation i is positive or negative

#### constraints

subject to constraint_b_pos {i in S: a[i,1] = 0}: sum{ j in N} a[i,j+1]* x[j] + sum{j in N} (1-a[i,j+1]) * x[num_attributes+j]<= d-1;

subject to constraint_c {j in N}: x[j] + x[num_attributes+j] <= 1;

subject to constraint_d: sum{j in NN} x[j] = d;

subject to constraint_e_1: d >= 1;

subject to constraint_e_2: d <= num_attributes;

subject to feasibility_cut {n in nols: n <= nsoln}: if nsoln > 0 then  

     sum {j in NN: x_inf[n,j]=0} x[j] + sum {j in NN: x_inf[n,j]=1} (1-x[j]) >=1 ;

subject to optimality_cut_pos {m in nols2: m <= nsoln2}: if nsoln2 > 0 then

 

     Gamma >=  sum {i in S: c[i] = 0 and a[i,1] = 1} dual_a_pos[i, m] * d + dual_coverage_pos[m] * ((M_Pos- sum{i in S:a[i,1] = 1 and c[i]=0} c[i]) - 1) + sum {i in S: c[i] = 0 and a[i,1] = 1} dual_y_pos[i, m];

 

 # Sub problem-positive pattern generation

 

 minimize objective_z_pos: sum{i in S: a[i,1] = 1 and c[i]=0} y[i]; # the model tells that when y = 1 it refers to an uncovered observation

 subject to constraint_a_pos {i in S: c[i] = 0 and a[i,1] = 1}: sum{j in N} a[i,j+1] * x[j] + sum{j in N} (1-a[i,j+1]) * x[num_attributes+j] + num_attributes * y[i] >= d;

 subject to coverage_pos: sum{i in S:a[i,1] = 1 and c[i]=0} y[i] <= (M_Pos- sum{i in S:a[i,1] = 1 and c[i]=0} c[i]) - 1; # the generated pattern should cover at least one observation

 

 subject to y_pos {i in S: c[i] = 0 and a[i,1] = 1}: y[i] <= 1;

-----------------------------------------------------------------------------------------------------------------------------------------------

and here is the algorithm

-----------------------------------------------------------------------------------------------

model bender3.mod;

data  ryoo09.txt;

param UB default 0;

param sub_sol_time;

param mas_sol_time;

param Num_pos_patterns default 0;

param Num_neg_patterns default 0;

param Num_covered default 0; #to tell the number of observations covered by the generated pattern.

option solver_msg 0;

option solver cplexamp;

option eexit -500;

option display_precision 0;

option presolve 0;

options cplex_options "presolve 0";

suffix up OUT; 

suffix down OUT; 

suffix dunbdd;

problem master_1_problem_pos: x,d,constraint_b_pos, constraint_c, constraint_d, constraint_e_1, constraint_e_2;   

problem master_problem_pos: x,d,Gamma, constraint_b_pos, constraint_c, constraint_d, constraint_e_1, constraint_e_2, feasibility_cut, optimality_cut_pos, Benders_master;   

problem master_problem_feasible_pos: x,d,constraint_b_pos, constraint_c, constraint_d, constraint_e_1, constraint_e_2, feasibility_cut;   

problem sub_problem_pos: y,constraint_a_pos, coverage_pos, y_pos, objective_z_pos;

let double_num_attributes := 2 * num_attributes;

let num_attributes_plus1 := num_attributes + 1;

for {i in S} 

{ 

 if a[i,1] = 1 then let M_Pos := M_Pos + 1 ;

 else if a[i,1] = 0 then let M_Neg := M_Neg +1 ;

}

display M_Pos, M_Neg;

for {j in NN} let x[j]:=0; for {i in S: a[i,1] = 1} let y[i]:= 0; let d:= 0; # to reset the values of the decision variables

let Gamma := 10000;

################# start of Benders approach

solve master_1_problem_pos;

display x,d;

repeat { 

solve sub_problem_pos;

display sub_problem_pos.result;

display objective_z_pos;

display d;

#expand constraint_a_pos;

let sub_sol_time := sub_sol_time + _solve_time;

if sub_problem_pos.result= "infeasible" then 

{

let nsoln:= nsoln +1;

for {j in NN} let x_inf[nsoln,j] := x[j];

}

else if sub_problem_pos.result = "solved" then {

let nsoln2:= nsoln2 +1;

for {i in S: c[i] = 0 and a[i,1] = 1} let dual_a_pos[i, nsoln2]:= constraint_a_pos[i].dual; 

for {i in S: c[i] = 0 and a[i,1] = 1} let dual_y_pos[i, nsoln2]:= y_pos[i].dual; 

let dual_coverage_pos[nsoln2] := coverage_pos.dual;

display dual_a_pos; display dual_coverage_pos; display dual_y_pos; 

display Gamma; display objective_z_pos;

if abs(Gamma - objective_z_pos) < .001 then break;

}

if nsoln2 = 0 then {solve master_problem_feasible_pos;

#display master_problem_feasible_pos.result;#

let mas_sol_time := mas_sol_time + _solve_time;

if master_problem_feasible_pos.result = "infeasible" then break;}

else if nsoln2 > 0 then {solve master_problem_pos;

#display master_problem_pos.result;#

let mas_sol_time := mas_sol_time + _solve_time;

if master_problem_pos.result = "infeasible" then break;}

} ############### end of Benders approach, this should result in one pattern

----------------------------------------------------------------------------------------------------------------------------------------------

data file;

data;

param num_attributes = 16;

param num_observations = 34;

param a:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17:=

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

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

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

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

5 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

6 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

7 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

8 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0

9 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0

10 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0

11 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

12 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

13 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

14 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

15 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0

16 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0

17 1 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0

18 0 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0

19 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1

20 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1

21 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1

22 1 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0

23 1 1 1 1 0 1 0 1 0 1 0 0 0 1 0 0 0

24 0 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0

25 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1

26 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1

27 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1

28 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0

29 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0

30 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0

31 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

32 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

33 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

34 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1;

[Paul]

Might be my poor eyesight, but I don't see any place where you relax the integrality restriction on y in the subproblem. If y is restricted to integer in the subproblem, then dual variables are largely meaningless.

Paul