The old Google Groups will be going away soon, but your browser is incompatible with the new version.
zero dual variables for +ve primal objective
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 2 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 11 2012, 3:25 pm
From: enhany75 <enhan...@yahoo.com>
Date: Sun, 11 Nov 2012 12:25:13 -0800 (PST)
Local: Sun, Nov 11 2012 3:25 pm
Subject: zero dual variables for +ve primal objective

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;

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 11 2012, 5:33 pm
From: Paul <parubi...@gmail.com>
Date: Sun, 11 Nov 2012 14:33:01 -0800 (PST)
Local: Sun, Nov 11 2012 5:33 pm
Subject: Re: zero dual variables for +ve primal objective

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