Column-wise Modeling in Python using PuLP Solver

3 min readApr 30, 2021

There are several articles about modeling linear and integer programs in Python. Please refer to this article that solves a simple problem using PulP.

There are two ways of building an LP model and most of the articles only illustrate row-wise modeling where the constraints are built one row after another creating all the variables upfront. In column-wise modeling empty constraints (with RHS) are created first and the matrix is built by adding columns one by one.

In a majority of the problems we have complete set of variables available while building model. So the user of the model can either use row-wise modeling (most used) or column-wise modeling (very rarely used).

However when user does not have all columns available while building the model. These columns are obtained one by one after model is built and so the only way to interact with the model is to use column-wise modeling . In this article I will illustrate this technique using PuLP solver.

I typically create Model class to hold constraints, objective and variables. This class is also useful to hold dictionaries between domain objects and the corresponding variables and constraints. The word “self” refers to this Model class and the steps below are performed to build LP Model while populating dictionaries between domain objects and model objects.

self.prob = LpProblem("MyLPProblem", LpMinimize)
self.obj = LpConstraintVar("Obj")

For example lets say we are solving set partitioning problem where one column is sequence of flights for each crew. In this path flow formulation each column is sequence of flights for given crew

Add Constraints for flights

for o in self.flights: #example: constraint per flight
    self.constraints[o.id] = LpConstraintVar("Constraint" + str(o.id), LpConstraintEQ, 1)
    self.prob += self.constraints[o.id] 
    self.slacks += [LpVariable("Slack " + str(o.id), 0, None, LpContinuous, 10000 * self.obj + self.constraints[o.id])] #this adds slack column - we will use same syntax again for adding variables

Add Constraints for crew

for o in self.crews: #example: constraint per flight
    self.constraints[o.id] = LpConstraintVar("Constraint" + str(o.id), LpConstraintEQ, 1)
    self.prob += self.constraints[o.id] 
    self.slacks += [LpVariable("Slack " + str(o.id), 0, None, LpContinuous, 10000 * self.obj + self.constraints[o.id])] #this adds slack column - we will use same syntax again for adding variables

This code will examine the column and add variable to model with appropriate coefficients in appropriate rows.

#Adding variable for one column (sequence of flights)
#Assume each column of list of flights (col.flights) and single crew (col.crew)#Need to populate column with coefficient for each constraint related to col.flights and col.crew
coeff1 = 1
coeff2 = 1     col_id = "V" + get_string(column.flights,col.crew) 
    col_cost = self.get_cost(col.flights,var.crew)
    self.vars += [LpVariable(col_id, 0, None, LpBinary,  col_cost * self.obj + lpSum([coeff1*self.constraints[o.id]  for o in var.domainObjList1]+ [coeff2*self.constraints[col.crew.id] ))]

After this you model is complete and ready to solve. Please note that if you generate more columns you can always add them at any time (for example in a column generation scheme — you will add few columns at start and keep adding columns with attractive reduce cost until you can find none).

Column-wise Modeling in Python using PuLP Solver

Written by Ram Thiruveedhi