How to model column-wise
Usually a model is written row by row: create the variables, then add each constraint as an expression over them. Some models are easier to write column by column: each new variable comes with its coefficient in the objective and in the constraints that already exist. The typical case is column generation, where a problem is solved, new variables (columns) are priced from the dual values, and the problem is solved again with those columns added.
PuLP supports this on one problem object, without rebuilding it:
add_column()creates a variable together with its objective coefficient and its coefficients in existing constraints.set_coefficient()(orcon[x] = value) sets one coefficient of an existing constraint.remove_variables()takes variables out of the model.x.cat = ...changes a variable’s category, for example to make the final problem integer.resolve()solves the problem again. With the solvers that support it (HiGHS, GUROBI, CPLEX_PY, XPRESS_PY, COPT, CyLP, PYGLPK) it updates the solver’s model in place and restarts from the previous basis (see Re-solving without rebuilding).
Adding a column
Create the constraints first and keep them; addConstraint returns each one
as stored in the problem. A constraint may start with no terms at all:
from pulp import LpProblem, LpMinimize, lpSum
prob = LpProblem("column_wise", LpMinimize)
x = prob.add_variable("x", 0, 1)
c1 = prob.addConstraint(x >= 1, "c1")
c2 = prob.addConstraint(lpSum([]) >= 1, "c2") # empty for now
prob += x
y = prob.add_column("y", lowBound=0, upBound=1, obj=2, coefficients={c1: 1, c2: 1})
z = prob.add_column("z", lowBound=0, upBound=1, obj=3, coefficients={c2: 1})
# c1: x + y >= 1
# c2: y + z >= 1
# objective: x + 2*y + 3*z
add_column takes the same name, lowBound, upBound and cat as
add_variable(), plus:
obj: the coefficient in the objective (default 0). If the problem has no objective yet andobjis not 0, one is created.coefficients: a dict from eachLpConstraintof this problem to the coefficient of the new variable in it. Constraints that are not in the dict do not get the variable. A coefficient of 0 is skipped.
Everything is checked before the variable is created. If a coefficient is
infinite or NaN, add_column raises ValueError and the problem is left as
it was.
The new term goes at the end of each constraint, so a problem built column by column writes the same LP and MPS files as the same problem built row by row.
Setting one coefficient
To put an existing variable into a constraint, or change its coefficient, set it on the constraint:
c1[z] = 0.5 # c1: x + y + 0.5*z >= 1
del c1[x] # c1: y + 0.5*z >= 1
See How to edit constraints for everything you can change on a constraint.
Removing columns
prob.remove_variables(variables) takes the variables out of every
constraint, the objective and every SOS group:
prob.remove_variables([z])
The variables stay valid: you can still read them and put them back with
c[z] = value. A variable that no constraint and no objective uses is left
out of the LP and MPS files and is not sent to most solvers. The solvers that
resolve() updates in place are the exception: they get
every variable, an unused one as an empty column, so that new ones can be
appended (see Re-solving without rebuilding).
Example: cutting stock by column generation
Rolls of width 100 are cut into pieces to meet the demand for four widths. Each variable is a pattern: how many pieces of each width are cut from one roll. There are too many patterns to list, so the problem starts with one simple pattern per width and adds a better pattern while one exists:
Solve the linear relaxation of the master problem and read the duals
piof the demand constraints.Solve a knapsack problem to find the pattern with the largest total dual value that fits in a roll.
If that value is more than 1 (the cost of one roll), the pattern improves the master problem: add it with
add_columnand go back to step 1.Otherwise, make the patterns integer and solve once more.
from pulp import LpInteger, LpMaximize, LpMinimize, LpProblem, getSolver, lpSum
roll_width = 100
orders = {"w45": (45, 97), "w36": (36, 610), "w31": (31, 395), "w14": (14, 211)}
solver = getSolver("HiGHS", msg=False) # any solver that returns duals
# Master problem: one pattern per width, as many pieces as fit in a roll.
master = LpProblem("cutting_stock", LpMinimize)
patterns = []
demand = {}
for item, (width, quantity) in orders.items():
x = master.add_variable(f"pattern_{len(patterns)}", lowBound=0)
patterns.append(x)
demand[item] = master.addConstraint(
(roll_width // width) * x >= quantity, f"demand_{item}"
)
master += lpSum(patterns)
master.solve(solver)
while True:
duals = {item: c.pi for item, c in demand.items()}
# Pricing: the pattern with the largest total dual value.
pricing = LpProblem("pricing", LpMaximize)
n = pricing.add_variable_dicts("n", orders, lowBound=0, cat=LpInteger)
pricing += lpSum(duals[i] * n[i] for i in orders)
pricing += lpSum(width * n[i] for i, (width, _) in orders.items()) <= roll_width
pricing.solve(solver)
if 1 - pricing.objective.value() >= -1e-9:
break # no pattern improves the master problem
pattern = {i: round(n[i].varValue) for i in orders}
new = master.add_column(
f"pattern_{len(patterns)}",
lowBound=0,
obj=1,
coefficients={demand[i]: k for i, k in pattern.items() if k},
)
patterns.append(new)
master.resolve() # only the new column is sent to the solver
print("LP bound:", master.objective.value()) # 452.25
# Make the patterns integer and solve the final problem.
for x in patterns:
x.cat = LpInteger
stats = master.solve(solver)
print("rolls:", stats.objective) # 453.0
The loop adds two patterns before no further improvement is possible. The same
master problem is solved each time: it is never rebuilt, and the demand
constraints found in step 1 are the ones the new columns are added to.
master.resolve() hands HiGHS only the new column and lets it start from the
previous optimal basis. The final master.solve(solver) builds the model
again, which is what you want once the categories have changed.
Re-solving without rebuilding
solve() loads the whole problem into the solver every
time. resolve() does that too, except with the solvers
that keep the model in memory and can edit it: HiGHS, GUROBI,
CPLEX_PY, XPRESS_PY, COPT, CyLP and PYGLPK. After a first solve, they
record every edit to the problem, and resolve sends only those edits to the
model they hold in prob.solverModel:
new variables (from
add_columnoradd_variable) and new constraints;changed coefficients, right-hand sides and senses of existing constraints;
changed bounds and categories of variables, and removed variables;
a changed objective or objective sense.
The solver keeps its basis, so after adding a few columns or a cut it usually
needs only a few simplex iterations, and none if the old solution is still
optimal. The duals, reduced costs and values are read back as after solve.
prob.solve(getSolver("HiGHS", msg=False)) # builds the model
model = prob.solverModel
prob.add_column("y", 0, 1, obj=2, coefficients={c1: 1})
prob += x + y <= 1, "cut"
prob.resolve() # updates it in place
assert prob.solverModel is model
resolve builds the model from scratch, like solve, when it cannot
update it:
on the first solve, or when the last solve used another solver (or another instance of the same solver);
on a copy of the problem (
prob.copy()): a copy is not tracked;after adding or removing SOS groups;
with CyLP, after changing a coefficient of an existing variable in an existing constraint (
remove_variablesincluded), since Clp cannot change an entry of its matrix, and for a MIP, which Cbc solves;with any other solver, which always rebuilds. MOSEK could update its model too, but does not yet.
The solver’s options (time limit, gaps, msg, log file) are applied again on
every resolve. warmStart only applies when the model is built: on a resolve
the previous basis is the warm start. A degenerate LP has several optimal bases,
so a resolve can return other (equally valid) duals than a solve from scratch.
Notes
The coefficients of
add_columnare given perLpConstraint, so keep the constraints when you create them (addConstraintreturns them), or look them up withprob.get_constraint_by_name(name).Duals and slacks are only available from solvers that return them, and only for linear problems. Solve the relaxation (continuous variables) while generating columns, then change the category with
x.cat = LpInteger.Editing a constraint, adding a column or changing a category keeps the values (
varValue,pi,slack) of the last solve until the next one.In PuLP 3.x column-wise modelling used
LpConstraintVarandLpVariable(..., e=...). Both were removed in 4.0;add_columnreplaces them.