Originally posted by: VivekPeriaraj

Hello,

I have a dual vector which I would like to see if it's feasible or not. I have tried the following methods:

1) Create a dual problem object, set the LB and UB of the variables to the dual solution and run CPXpresolve().

2) Create a dual problem object and use CPXgetrowinfeas().

Method 1 works but it takes some time.

I have bounds for all my variables in the primal, so I have to provide the reduced costs as duals along with the duals of the constraints in Method 2.

Is there any other way to do this?

Regards,
Vivek.

Originally posted by: TobiasAchterberg

If all variables are boxed (finite lower and upper bound) then any dual vector is feasible (because you will always find a reduced cost vector that solves the dual equation system).

Your concern that you have to provide reduced costs for Method 2 indicates that you do not want to calculate them and only want to test the dual vector for feasibility. But given my comment above, the answer would then always be "yes". So, what is the reason that you want to do this?

Originally posted by: VivekPeriaraj

Thanks Tobias. I have decomposed (DW) my problem into two - where I get the duals for one set of constraints from one problem and get duals for remaining set of constraints from another problem (both of which are solved separately, so I get the duals from the last iteration of the LP solver). I then combine these two set of duals to get the duals for my original problem. It is this final dual vector that I want to check for feasibility. Like you have mentioned, I have found all my iterations to produce only feasible duals using Method 1 and was looking for Method 2 where I could do this fast. If you could confirm that I have to compute the reduced costs for all my bounded primal variables as well as provide the dual vector itself in Method 2, then I would proceed with Method 2. Is CPXdualwrite() the only way to get the dual problem object? I ask this because after writing out and I use CPXreadcopyprob() to read back the problem and here, I might be messing up the order of the variables.

Regards,
Vivek.

Originally posted by: TobiasAchterberg

If you only check for feasibility (meaning: there exists a reduced cost vector such that the given dual solution extended by the reduced cost vector yields a dual feasible solution) then you do not need to calculate the reduced costs for boxed variables. You just do not need to check the dual equation that corresponds to the boxed variable, because you know in advance that you will always be able to find a reduced cost value that will satisfy the equation.

You only need to check feasibility of your dual solution vector for those variables that have infinite bounds.

CPXdualwrite is one way of getting the dual problem object, but I would say that it is kind of risky to use it, because you do not know exactly what it does for boxed variables or ranged rows. It needs to introduce new variables, and you just don't know how exactly they are defined.

I suggest that you dualize your model manually. Go through the model column by column, and for each column add a row to the dual problem. Then you know exactly how the dual was set up and you know exactly the mapping between primal and dual.

Originally posted by: VivekPeriaraj

Thanks Tobias. I will formulate the dual on my own.

Originally posted by: VivekPeriaraj

I will also try by removing the bounds on the binary variables. I have read that it's customary to have the bounds retained for binary variables. I guess if my constraints force the binary variables to be always less than or equal to 1, then I need not have bounds specified?

Regards,
Vivek.

Originally posted by: TobiasAchterberg

I guess you are still talking about the continuous relaxation of your integer program, so that the binary variables are declared to be continuous variables in the relaxation.

In this case, if a bound of a variable is implied by the constraints, then it is indeed often useful to use an infinite bound instead. This removes degeneracy from the problem and makes sure that you do not have to deal with reduced costs for this variable in your pricing problem.

A very common example is set partitioning. When you have constraints

sum x_i = 1

and each x_i appears in at least one constraint, then you do not need to explicitly include the bounds x_i <= 1 in your model, because these are already implied by the constraints and by the lower bounds x_i >= 0. Thus, without the upper bounds you end up with a text-book form of an LP in equation form

min cx

s.t. Ax = b

x >= 0

This is often easier to think about when it comes to dualizing it. If one includes the upper bounds x_i <= 1 in the formulation, then a common mistake is to ignore the reduced costs for x_i in the pricing problem.

Originally posted by: VivekPeriaraj

I got it. Thanks.