written by Abremod, LLC on 2019-07-01

Using a column-wise formulation

Often, is it more convenient to think of the contraints that a variable participates in instead of the variables that are part of a constraint. Also, in a column-generation procedure, this is required. To support this, Gurobi has a Column object that can be used to when defining a model. Let's create the same model as before.

model = grb.Model()
c0 = model.addConstr(0, '>', 10, name='c0')
c1 = model.addConstr(0, '<', 4, name='c1')
model.update()
x = model.addVar(name='x', obj=2, column=grb.Column([1,  1], [c0, c1]))
y = model.addVar(name='y', obj=3, column=grb.Column([1, -1], [c0, c1]))
model.update()
model.optimize()

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 1e+00]
  Objective range [2e+00, 3e+00]
  Bounds range    [0e+00, 0e+00]
  RHS range       [4e+00, 1e+01]
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   1.000000e+01   0.000000e+00      0s
       2    2.3000000e+01   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.01 seconds
Optimal objective  2.300000000e+01

commentary

The column-wise approach often looks awkward. Linear programming formualtions are almost always documented in a row-wise format and it is natural to think in terms of the variables being added to constraints. Because of that, this method of creating models is often restricted to column-generation proceedures, where they are required and are probably under-utilized in other cases.

Obtaining the dual solution

When computing the solution to a linear problem (with no integer constraints), gurobi will also compute dual prices for the contraints. This has the economic interpretation as the change in the value of the objective as the right hand side of the contraint is increased or decreased, and it is used in Column Generation procedures. The attribute is Pi

constr_names = model.getAttr('ConstrName', model.getConstrs())
constr_values = model.getAttr("Pi", model.getConstrs())
zip(constr_names, constr_values)

[('c0', 2.5), ('c1', -0.5)]

commentary

In this example, the dual price of c0 ($x + y \ge 10$) was 2.5. That means, increasing the right hand side from 10, to say 10.1 and resolving would increase the objective from 2.3 to at least 2.55, and reducing the right hand side from 10 to 9.9 would reduce the objective by at most .25 to at least 2.05. We say at least 2.55 because we are minimizing.