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() (or con[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 and obj is not 0, one is created.

  • coefficients: a dict from each LpConstraint of 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:

  1. Solve the linear relaxation of the master problem and read the duals pi of the demand constraints.

  2. Solve a knapsack problem to find the pattern with the largest total dual value that fits in a roll.

  3. If that value is more than 1 (the cost of one roll), the pattern improves the master problem: add it with add_column and go back to step 1.

  4. 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_column or add_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_variables included), 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_column are given per LpConstraint, so keep the constraints when you create them (addConstraint returns them), or look them up with prob.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 LpConstraintVar and LpVariable(..., e=...). Both were removed in 4.0; add_column replaces them.