Originally posted by: BabakArh

hello

I am running a column generation problem.

I realized My sub problem produce same column in each iteration after a while but my master doesn't add it. I checked the reduced cost it should be 0 but subproblem shows a positive value. I start digging and find out one of my constraint should have positive value, but some how in the middle of run it changes to negative value. I checked dual status and it is feasible but tha value doesn't show so. I have these two question:

1- this negative dual disappears when I make my constraint range wider, how should i get rid of this problem? (It happens when my constraint is tight but not impossible)

2-why my dual status is "Optimal", it should be infeasible in this situation?

Originally posted by: BabakArh

I think there is a way this problem happens:

I think the CPLEX return the status by "Complementary slackness", so if the slack is 0 it doesnt check the dual var. so far if i make the constraint range wider, the slack var get value so it sounds correct and return the possible dual var.

Originally posted by: BoJensen

Hi,

I am not sure I completely understand your question.

As I understand, you have a dual value for a constraint, which doesn't have the expected sign, hence you believe the solution status should be infeasible.

First I suggest you write out the problem and the corresponding solution. Load both of them into the interactive command and launch 'display solution quality', which will the show dual infeasibilities.

If the problem persists, could you please give an example i.e what type of row and the level of dual value, if possible attach problem and solution. Also please note, CPLEX operates with absolute tolerances, so tiny values like -1.0e-10 is not considered infeasible pr. default, since the feasibility tolerance is 1.0e-6.

Originally posted by: BabakArh

it is like this

primal:Max CX

Ax<=b

x>=0

Dual:Min By

(transpose)Ay>=C

y>=0

I solve primal, and get dual value, in some constraint y is -50. i check the dual status it gives me optimal.it is infeasible and should be infeasible

Originally posted by: BoJensen

Could you please write out problem and solution and attach if possible. Before doing so, please also load both of them into the interactive command and launch 'display solution quality', which will the show dual infeasibilities.

Originally posted by: BabakArh

Hello, and thank you all for considering my problem.

I am running  large scale instant, and my method is column generation, I couldnt write it here, because if I write you wont be able to trace it.

I have simple question at all:

If my dual variable have to be positive why my model get it negative in some of them (just some of them takes wrong value)?

if you are aware of column generation method you should understand why it is so important (because every time i calculate reduced cost for new column by dual values). if they were wrong, i would not be able to calculate the column cost. so i would never find out I should add this column or not.

Originally posted by: BoJensen

Hi,

I do understand that you need the dual values to calculate a reduced cost for column generation and that these need to be of the right sign. But it's hard to help you if I can not look at the data. Could you add a write to file statement for both the problem and solution, at the point were you inspect the assumed wrong dual. You can see here how to write both the problem and solution file. If possible please send it to bo.jensen (at) dk.ibm.com.

Originally posted by: BabakArh

hi,

let me show you the weirdest thing in the CPLEX, which is happening in CPLEX111 CPLEX 124 and CPLEX 126

I am running the maximization instant. I get the reduced cost from the CPLEX for all my variables. Ihave a positive reduced cost for my base var (which should be ZERO).

and the difference between my dual objective and primal objective is exactly equal that reduced cost.

look ar the picture enclosed.
 

Originally posted by: BoJensen

Sorry to repeat myself, but did you try my suggestion in the first reply :

"First I suggest you write out the problem and the corresponding solution. Load both of them into the interactive command and launch 'display solution quality', which will the show dual infeasibilities."

If the solution quality displayed for this (assumed optimal) solution shows infeasibility, then please post the solution quality output and send the problem to us.

Originally posted by: BabakArh

it is not even about dual variables, this is a fundamental concept. all Base var should have Zero Value.

Sorry I didnt do your suggestion because I thought maybe you didn't understand my problem so I tried to explain it.

can You help me to do what you said?

You mean I should give the solution to see if the problem is feasible or not?  I did it before it is feasible. if you mean something else about write out problem and solution in interactive script, I didnt get that, PLZ help me.

thank you

Originally posted by: BoJensen

You should export the problem and solution by writing it to file. These write statements should be inserted into your source right after the call to the optimizer.

Once you have these two solutions, you can load the problem into the interactive command prompt :

1) 'read problem.mps'

2) 'read solution.sol'

3) 'display solution quality'

Then inspect the result written to screen. Please also post it here.

Originally posted by: BabakArh

Thank you for teaching me how to export the solution, I can Tell you my problem better in this way:

Also I should mention, I couldn't run it in prompt, I didn't know where is the directory of the CPLEX to paste my solution and problem there to give a command to read them.

anyway, I export my model and solution.

If you don't mind plz open files enclosed.

in line 12 it is written dual is feasible.

and the most weirdest part is line 92, which showes the variable is "BASE variable" but with positive reduced cost.

<variable name="Y_n_s3" index="5" status="UL" value="1" reducedCost="21.5555555555556"/>

Originally posted by: BoJensen

Reading in your problem and displaying problem stats, I get :

CPLEX> display prob stat
Problem name         : prob.lp
Objective sense      : Maximize
Variables            :      53  [Box: 53]
Objective nonzeros   :      18
Linear constraints   :      63  [Equal: 63]
  Nonzeros           :     188
  RHS nonzeros       :       0

Notice you have equality constraints in the model i.e of type ==, duals for equality constraints can be of any sign i.e both negative or positive.

Regarding :

"and the most weirdest part is line 92, which showes the variable is "BASE variable" but with positive reduced cost.

<variable name="Y_n_s3" index="5" status="UL" value="1" reducedCost="21.5555555555556"/>"

Then you seem to be confused about what a basic solution is. This variable is on upper bound and has a positive reduced cost, which is dual feasible since the problem at hand is a maximization problem.

I have to correct myself, since loading the solution and printing the solution quality in the interactive is not possible, one has to call the optimizer first for CPLEX to recognize the solution. Sorry about that.

Originally posted by: BabakArh

<constraint name="ov_ass_3157" index="1636" status="LL" slack="0" dual="-9.58998832295371"/>

this is one of my Constraint should be positive value for dual. I attached the problem and solution.

if the variable is in upper bound, how can I take the dual values? how can I calculate the dual OBJ? the exact deference between my dual obj and primal is the reduced cost for the variable which is in upper bound.

if I want to say exactly what is wrong here, I could say:

consider I found the column which has positive reduced cost (=21) for maximization problem, I add the column to my model, then I solve it.

after solve, that column has the RC=21(positive value) no matter. so  I start to find new column, then i exactly find the column which I found before,. I add that column again and again.

Originally posted by: BoJensen

The dual of equality constraint :

 ov_ass_3157:    Y_n_s235 + 6 X_74 - Rgov_ass_3157  = 0

can be of any sign due to duality.

The solution :

<constraint name="ov_ass_3157" index="1636" status="LL" slack="0" dual="-9.58998832295371"/>

tells you the slack/artificial for constraint ov_ass_3157 is at lower bound level (zero) with a dual value of -9.58998832295371. Which is OK since it's a maximization problem.

Also you add variable Rgov_ass_3157, but it's not present in the solution file. I think you have not written the matching solution to your problem.

Originally posted by: BabakArh

I am using RANG for writing my model which is model the constraint in this way:

Y <=1       ===>  Y-rg=0  &    rg<=1

this is how you can add column to constraint every time. for the maximization model the constraint I wrote above should have positive dual value but the model gives me a negative value.

the constraint I mentioned above is in that form. if there is rg (Rgov_ass_3157== rg+"constraint name"), it means this constraint is not in equal form. if it appears in negative form (-rg) means, this is <= constraint, otherwise is >=.

the solution and the problem is for one model

Originally posted by: BoJensen

There's a misunderstanding here regarding duals on constraints.

If you convert a constraint of the form <= into equality == by adding your own slack variable sum(aij*xj)-s == 0 s <= 0, then the dual of the (equality) constraint can now be of any sign. But the reduced cost of your custom created slack variable s must be positive (maximization assumed). If you insist on adding your own slack variables, then you should not fetch the constraint dual, but the reduced cost of s if you want a positive dual.

Originally posted by: BabakArh

Thank you a lot for considering my problem.

no I didnt add my own slack. this is the way of modeling for column generation in CPLEX.

I didnt add the slack variables you mentioned.

for more information, those slacks have a dual values by C_BB^-1 which is exactly equal to dual values. the problem is i have a constraint which is not in equal form however, i have both sign value for this constraint.

Originally posted by: BoJensen

The following transformation :

Y <=1    ===>  Y-rg=0  &    rg<=1

is the same as adding your own slack variable ('rg') and converting the constraint to a equality constraint.

"the problem is i have a constraint which is not in equal form however, i have both sign value for this constraint. "

But the problem you sent me had only equality constraints :

CPLEX> display prob stat

Problem name         : prob.lp
Objective sense      : Maximize
Variables            :      53  [Box: 53]
Objective nonzeros   :      18
Linear constraints   :      63  [Equal: 63]
  Nonzeros           :     188
  RHS nonzeros       :       0

Originally posted by: BabakArh

all problem I have got was about upper bound and lower bound limit

i keep thinking if i limit the upper bound it could give me an optimum solution faster but it changed my problem to another problem. for e.g

if you know y>=0 and if u have sum(y)<=1 ====> it means 0<=sum(y)<=1. however if you use 0<=sum(y)<=1 in your model it gives you another problem which has another dual values

Originally posted by: geffer

Hi.

 I am not quite understand your problem either.....

It is common some constraints' dual variable switch between negative and positive during column generation, so what?

Thanks

Originally posted by: BabakArh

so what?

it would be infeasible.

when u use column generation it is only dependent the dual variables. if they r infeasible means u never gonna rich to optimal value.