Originally posted by: VivekPeriaraj

Hello,

 

I have few constraints (< 200) which are of type >=. Initially these constraints would be empty as I would be adding more columns to it later. I couldn't leave it as empty because it would be '0 >= +ve' and so would be infeasible. Is there anyway to remodel this constraint such that it would be feasible all the time until I add columns to it?

 

Example:

c1:  >= 5

c2: >= 10

 

I couldn't create a surplus variable as that would be '-s1 = 5' and '-s2 = 10' would still be infeasible.

 

Regards,

Vivek.

#CPLEXOptimizers
#DecisionOptimization

Create a single artificial variable, add it to the LHS of each of those constraints, and penalize the daylights out of it in the objective function?

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Hi Paul,

 

I tried something similar but without penalizing the objective. I didn't want to change the duals from this change so I had the objective as 0. And I selectively set the UB of those variables to 0 as each constraint start to fill up with columns. Ugly trick but still not working as expected. I will elaborate a bit more. This constraint is a demand constraint of the form:

 

K1 * X1 + K2 * X2 >= D * Y1

 

Where K1, K2, ...  are capacities and D is the demand. And Xs and Ys are binary. I relaxed this when I solve it as LP. When I model the constraint as follows, I get favorable duals:

 

K1 * X1 + K2 * X2 >= D

 

But this has one drawback. In the beginning, when no columns are added, it becomes infeasible (0 >= +ve) plus when not many columns are added, it becomes infeasible (which is alright but I would like to avoid this too because I have to now get an extreme ray to handle this situation and I get too many infeasibilities until the model 'stabilizes')

 

I have tried the following:

 

1) K1 * X1 + K2 * X2 + A1 >= D

2) K1 * X1 + K2 * X2 >= D * Y1

3) K1 * X1 + K2 * X2 >= D

 

In Method 3, I begin with RHS as -1 and then change it to D as and when I add columns. Method 3 outperforms 1 and 2 for smaller instances but too many infeasibilities as I don't want to deal with extreme rays for now. I would like to do this without affecting the duals much.

 

Thanks,
Vivek.

 

 

 

 

 

#CPLEXOptimizers
#DecisionOptimization

A reasonably standard practice in column generation would be to generate enough columns to make the demand constraint feasible before solving the relaxation for the first time. Sometimes there are obvious choices for columns that, while undesirable from an objective viewpoint, at least guarantee feasibility. (For instance, in a warehouse location problem, start with a column that utilizes every possible warehouse.) In other cases, you can start with a Phase I problem (artificials in the demand constraints, minimize the sum of artificials) and use your column generation technique to produce enough columns to drive the Phase I objective value to zero; then delete the artificials and go back to the original objective function.

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Thanks Paul. I should be able to get a feasible solution that uses all of my demand constraints. This way my master problem would be tagged at this solution until more columns are added. Also, would like your thoughts on why formulation 3 is better - is it because my 'b' vector is reduced in other formulations (1 and 2) and so dual objective is slightly worse than 3?

 

Regards,
Vivek.

#CPLEXOptimizers
#DecisionOptimization

Sorry, no idea why (3) would outperform (1) or (2). Might be by design, but my guess would be just luck of the draw -- but that's just a guess.

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: VivekPeriaraj

Thank you. It could be just the luck. I haven't been able to do full test on it.

 

Regards,

Vivek

#CPLEXOptimizers
#DecisionOptimization