Dual Generation

Description

In this problem, you'll write a function to generate a representation of the dual of a given LP. That is, you'll use your Python knowledge to answer a custom question which is difficult to answer even with powerful tools like Gurobi. (Indeed, as far as we're aware, Gurobi does not provide this functionality.)

If the primal describes a resource allocation problem, the dual describes a resource valuation problem. The dual enables sensitivity analysis like the direct computation of shadow prices. This motivates your pursuit of the dual in this exercise.

We'll use the sponge/butter cake problem from 15.066, reproduced below, as our running example.

We'll work with a Python LP format which would represent this LP like so¹:

lp = {'min': False,
      'obj': [5,6], 
      'A_ub': [[3,6],
               [6,4.5],
               [1,0],
               [0,1]],
      'b_ub': [420,
               465,
               90,
               60],
      'bounds': [(0, None), (0, None)]}

We describe this representation in more detail now. Call the number of variables in the LP num_vars.

• The 'min' entry in the dictionary describes whether or not the LP is a minimization (True) or maximization (False) problem.
• The 'obj' entry is a list of length num_vars, each element of which is the coefficient of the associated variable in the objective function.
• The 'A_ub' entry is a list of lists. Each list has length num_vars, and contains coefficients of the asociated variables in a <= constraint.
• The 'b_ub' entry is a list of the same length as A_ub, and contains the right hand side values of the 'A_ub' constraints.
• The 'bounds' entry is a list of length num_vars, containing one (lower_bound, upper_bound) tuple for each variable. A bound of None represents the absence of a bound.²

Recall that an = or >= constraint can be represented as two <= constraints or as a <= constraint with negative coefficients (respectively). So our representation is sufficiently encompassing.

The dual of the cake problem is:

which we would represent like:

dual = {'min': True,
        'obj': [420, 465, 90, 60], 
        'A_ub': [[-3, -6, -1, 0],
                 [-6, -4.5, 0, -1]],
        'b_ub': [-5,
                 -6],
        'bounds': [(0, None), (0, None), (0, None), (0, None)]}

Your Task

Your task is to write a function get_dual which takes in a dictionary representing an LP in standard form (a maximization, with all <= constraints, and all variables nonnegative), and returns a dictionary representing its dual. There are many equivalent representations of the dual in our form. Any are acceptable, but we encourage you to stick with that which comes most naturally from the primal. The dual need not be in standard form.

Test your function on the above and a few other manual test cases, then upload it below for checking.

Select File  No file selected

Loading...

Next Exercise: Electric Bill

Back to exercises