source: pyomo/trunk/pyomo/core/plugins/transform/dual_transformation.py @ 9475

Last change on this file since 9475 was 9475, checked in by wehart, 4 years ago

Updating the version #.

Renaming transformations to 'base.*' if they didn't have a specific
naming. NOTE: these are in the pyomo.core package ... which seems
odd. But we agreed that 'core' provides a connotation that we don't
intend.

Adding some documentation changes for 'pyomo help -t'.

File size: 6.9 KB
Line 
1from pyomo.util.plugin import alias
2
3from pyomo.core import *
4from pyomo.core.plugins.transform.hierarchy import IsomorphicTransformation
5from pyomo.core.plugins.transform.standard_form import StandardForm
6from pyomo.core.plugins.transform.util import partial, process_canonical_repn
7
8
9class DualTransformation(IsomorphicTransformation):
10    """
11    Creates a standard form Pyomo model that is equivalent to another model
12
13    Options
14        dual_constraint_suffix      Defaults to _constraint
15        dual_variable_prefix        Defaults to p_
16        slack_names                 Defaults to auxiliary_slack
17        excess_names                Defaults to auxiliary_excess
18        lb_names                    Defaults to _lower_bound
19        ub_names                    Defaults to _upper_bound
20        pos_suffix                  Defaults to _plus
21        neg_suffix                  Defaults to _minus
22    """
23
24    alias("base.lagrangian_dual", doc="Create the LP dual model.")
25
26    def __init__(self, **kwds):
27        kwds['name'] = "linear_dual"
28        super(DualTransformation, self).__init__(**kwds)
29
30    def apply(self, model, **kwds):
31        """
32        Tranform a model to its Lagrangian dual.
33        """
34
35        # Optional naming schemes for dual variables and constraints
36        constraint_suffix = kwds.pop("dual_constraint_suffix", "_constraint")
37        variable_prefix = kwds.pop("dual_variable_prefix", "p_")
38
39        # Optional naming schemes to pass to StandardForm
40        sf_kwds = {}
41        sf_kwds["slack_names"] = kwds.pop("slack_names", "auxiliary_slack")
42        sf_kwds["excess_names"] = kwds.pop("excess_names", "auxiliary_excess")
43        sf_kwds["lb_names"] = kwds.pop("lb_names", "_lower_bound")
44        sf_kwds["ub_names"] = kwds.pop("ub_names", "_upper_bound")
45        sf_kwds["pos_suffix"] = kwds.pop("pos_suffix", "_plus")
46        sf_kwds["neg_suffix"] = kwds.pop("neg_suffix", "_minus")
47
48        # Get the standard form model
49        sf_transform = StandardForm()
50        sf = sf_transform(model, **sf_kwds)
51
52        # Roughly, parse the objectives and constraints to form A, b, and c of
53        #
54        # min  c'x
55        # s.t. Ax  = b
56        #       x >= 0
57        #
58        # and create a new model from them.
59
60        # We use sparse matrix representations
61
62        # {constraint_name: {variable_name: coefficient}}
63        A = _sparse(lambda: _sparse(0))
64
65        # {constraint_name: coefficient}
66        b = _sparse(0)
67
68        # {variable_name: coefficient}
69        c = _sparse(0)
70
71        # Walk constaints
72        for (con_name, con_array) in sf.active_components(Constraint).items():
73            for con in (con_array[ndx] for ndx in con_array._index):
74                # The qualified constraint name
75                cname = "%s%s" % (variable_prefix, con.name)
76
77                # Process the body of the constraint
78                body_terms = process_canonical_repn(
79                    generate_canonical_repn(con.body))
80
81                # Add a numeric constant to the 'b' vector, if present
82                b[cname] -= body_terms.pop(None, 0)
83
84                # Add variable coefficients to the 'A' matrix
85                row = _sparse(0)
86                for (vname, coef) in body_terms.items():
87                    row["%s%s" % (vname, constraint_suffix)] += coef
88
89                # Process the upper bound of the constraint. We rely on
90                # StandardForm to produce equality constraints, thus
91                # requiring us only to check the lower bounds.
92                lower_terms = process_canonical_repn(
93                    generate_canonical_repn(con.lower))
94
95                # Add a numeric constant to the 'b' matrix, if present
96                b[cname] += lower_terms.pop(None, 0)
97
98                # Add any variables to the 'A' matrix, if present
99                for (vname, coef) in lower_terms.items():
100                    row["%s%s" % (vname, constraint_suffix)] -= coef
101
102                A[cname] = row
103
104        # Walk objectives. Multiply all coefficients by the objective's 'sense'
105        # to convert maximizing objectives to minimizing ones.
106        for (obj_name, obj_array) in sf.active_components(Objective).items():
107            for obj in (obj_array[ndx] for ndx in obj_array._index):
108                # The qualified objective name
109
110                # Process the objective
111                terms = process_canonical_repn(
112                    generate_canonical_repn(obj.expr))
113
114                # Add coefficients
115                for (name, coef) in terms.items():
116                    c["%s%s" % (name, constraint_suffix)] += coef*obj_array.sense
117
118        # Form the dual
119        dual = AbstractModel()
120
121        # Make constraint index set
122        constraint_set_init = []
123        for (var_name, var_array) in sf.active_components(Var).items():
124            for var in (var_array[ndx] for ndx in var_array._index):
125                constraint_set_init.append("%s%s" %
126                                           (var.name, constraint_suffix))
127
128        # Make variable index set
129        variable_set_init = []
130        dual_variable_roots = []
131        for (con_name, con_array) in sf.active_components(Constraint).items():
132            for con in (con_array[ndx] for ndx in con_array._index):
133                dual_variable_roots.append(con.name)
134                variable_set_init.append("%s%s" % (variable_prefix, con.name))
135
136        # Create the dual Set and Var objects
137        dual.var_set = Set(initialize=variable_set_init)
138        dual.con_set = Set(initialize=constraint_set_init)
139        dual.vars = Var(dual.var_set)
140
141        # Make the dual constraints
142        def constraintRule(A, c, ndx, model):
143            return sum(A[v][ndx] * model.vars[v] for v in model.var_set) <= \
144                   c[ndx]
145        dual.cons = Constraint(dual.con_set,
146                               rule=partial(constraintRule, A, c))
147
148        # Make the dual objective (maximizing)
149        def objectiveRule(b, model):
150            return sum(b[v] * model.vars[v] for v in model.var_set)
151        dual.obj = Objective(rule=partial(objectiveRule, b), sense=maximize)
152
153        return dual.create()
154
155
156class _sparse(dict):
157    """
158    Represents a sparse map. Uses a user-provided value to initialize
159    entries. If the default value is a callable object, it is called
160    with no arguments.
161
162    Examples
163
164      # Sparse vector
165      v = _sparse(0)
166
167      # 2-dimensional sparse matrix
168      A = _sparse(lambda: _sparse(0))
169
170    """
171
172    def __init__(self, default, *args, **kwds):
173        dict.__init__(self, *args, **kwds)
174
175        if hasattr(default, "__call__"):
176            self._default_value = None
177            self._default_func = default
178        else:
179            self._default_value = default
180            self._default_func = None
181
182    def __getitem__(self, ndx):
183        if ndx in self:
184            return dict.__getitem__(self, ndx)
185        else:
186            if self._default_func is not None:
187                return self._default_func()
188            else:
189                return self._default_value
190
Note: See TracBrowser for help on using the repository browser.