Columnwise formulation

[Kuifje02]

Hi,

I am working on a columnwise formulation with pulp and am encountering a problem. The difficulty comes from the fact that iteratively, new constraints are added to the master problem, and these constraints include variables (or columns) from the previous iterations, and the current iteration. For example,

• at iteration 1, the master problem reads as follows:

$$min z s.t. 2x <= z (C1) x = 1 (C2)$$

• at iteration 2, a new column y is found, and the master problem becomes:

$$min z s.t. 2x <= z (C1) x + y = 1 (C2) y <= z (C3) [new constraint with new variable (y) and old variable (z)]$$

Here is how I tried to do this:

from pulp import *
--
prob = LpProblem("test", LpMinimize)
obj = LpConstraintVar("obj")
prob.setObjective(obj)     
C1 = LpConstraintVar("C1", LpConstraintLE, 0)    
C2 = LpConstraintVar("C2", LpConstraintEQ, 1)
prob += C1  
prob += C2
z = LpVariable("z", 0, None, LpContinuous, 1*obj - C1) 
x = LpVariable("x", 0, 1, LpBinary,  2C1 + C2)      

This properly initializes the masterproblem.

Here is where I am stuck: I tried to create the new variable y and the new new constraint (C3) as follows:

C3 = LpConstraintVar("C3", LpConstraintLE, 0)
prob += C3
y = LpVariable("y", 0, 1, LpBinary, C2 + C3)`

But in this case, constraint C3 does not include the old variable z. And when I define z, I cannot use something like
z = LpVariable("z", 0, None, LpContinuous, 1*obj - C1 - C3) because C3 does not exist yet.

So perhaps one way around is to initialize a predefined set of empty constraints {C1,C2,...CN} :

from pulp import *
--
prob = LpProblem("test", LpMinimize)
obj = LpConstraintVar("obj")
prob.setObjective(obj)     
C1 = LpConstraintVar("C1", LpConstraintLE, 0)    
C2 = LpConstraintVar("C2", LpConstraintEQ, 1)
C3 = LpConstraintVar("C3", LpConstraintLE, 0)
...
CN = LpConstraintVar("CN", LpConstraintLE, 0)
prob += C1  
prob += C2
prob += C3
...
prob += CN
z = LpVariable("z", 0, None, LpContinuous, 1*obj - C1-C3 - ... -CN) 
x = LpVariable("x", 0, 1, LpBinary,  2C1 + C2)      

This way, when z is defined (z = LpVariable("z", 0, None, LpContinuous, 1*obj - C1-C3 - ... -CN) ) there is no problem.

But this requires setting the value of N which can be tricky. Is there a better way of doing this ?

Thanks for any help!

[pchtsp]

I haven't tried this functionality so I can't be of much help. Have you checked the example here: https://github.com/coin-or/pulp/blob/master/examples/CGcolumnwise.py?

Having said that, I would say yes: you should initiliaze all constraints at the beginning. As far as I understand, in the classic column generation approach, you should have a fixed set of constraints and then you add your variables with respect to those constraints.

Maybe we should add a documentation on how to use this functionality. I'm also curious on how it actually works.

[Kuifje02]

Thanks for your help! Yes I have check the example, it was definitely very helpful.

Here, I am dealing with a min max problem, and so I am minimizing a variable z subject to z >= x_i, for every variable (column) x_i. And so when a new column is found, I have a new constraint.

But its ok, the approach described above works, I was just wondering if there was a better way to do it, maybe Stuart Mitchell has some trick for this :) If not no problem, you can close the issue.