Coverage for picos/constraints/con_flow.py: 57.14%
154 statements
« prev ^ index » next coverage.py v6.5.0, created at 2023-03-26 07:46 +0000
1# ------------------------------------------------------------------------------
2# Copyright (C) 2012-2017 Guillaume Sagnol
3# Copyright (C) 2018-2019 Maximilian Stahlberg
4#
5# This file is part of PICOS.
6#
7# PICOS is free software: you can redistribute it and/or modify it under the
8# terms of the GNU General Public License as published by the Free Software
9# Foundation, either version 3 of the License, or (at your option) any later
10# version.
11#
12# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
13# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
14# A PARTICULAR PURPOSE. See the GNU General Public License for more details.
15#
16# You should have received a copy of the GNU General Public License along with
17# this program. If not, see <http://www.gnu.org/licenses/>.
18# ------------------------------------------------------------------------------
20"""Implementation of :class:`FlowConstraint`."""
22from collections import namedtuple
24from ..apidoc import api_end, api_start
25from ..caching import cached_property
26from .constraint import Constraint, ConstraintConversion
28_API_START = api_start(globals())
29# -------------------------------
32class FlowConstraint(Constraint):
33 """Network flow constraint.
35 .. note ::
36 Unlike other :class:`~.constraint.Constraint` implementations, this one
37 is instanciated by the user (via a wrapper function), so it is raising
38 exceptions instead of making assertions.
39 """
41 class Conversion(ConstraintConversion):
42 """Network flow constraint conversion."""
44 @classmethod
45 def predict(cls, subtype, options):
46 """Implement :meth:`~.constraint.ConstraintConversion.predict`."""
47 from ..expressions import RealVariable
48 from . import AffineConstraint
50 numNodes, numEdges, flowCons, hasCapacities = subtype
51 V, E = numNodes, numEdges
53 # Capacity and non-negativity constraints.
54 yield ("con", AffineConstraint.make_type(dim=1, eq=False),
55 2*E if hasCapacities else E)
57 if len(flowCons) == 1:
58 yield ("con", AffineConstraint.make_type(dim=1, eq=True), V - 1)
59 else:
60 for k in flowCons:
61 yield ("var", RealVariable.make_var_type(dim=1, bnd=0), E)
63 for addition in cls.predict((V, E, (k,), False), options):
64 yield addition
66 yield ("con", AffineConstraint.make_type(dim=1, eq=True), E)
68 @classmethod
69 def convert(cls, con, options):
70 """Implement :meth:`~.constraint.ConstraintConversion.convert`."""
71 from ..modeling import Problem
72 P = Problem()
73 return cls._convert(con, P) # Allow for recursion.
75 @classmethod
76 def _convert(cls, con, P):
77 from ..expressions import new_param, sum
79 G = con.graph
80 f = con.f
81 source = con.source
82 sink = con.sink
83 flow_value = con.flow_value
84 capacity = con.capacity
85 graphName = con.graphName
87 # Add capacity constraints.
88 if capacity is not None:
89 c = {}
90 for v, w, data in G.edges(data=True):
91 c[(v, w)] = data[capacity]
92 c = new_param('c', c)
94 P.add_list_of_constraints([f[e] <= c[e] for e in G.edges()])
96 # Add non-negativity constraints.
97 P.add_list_of_constraints([f[e] >= 0 for e in G.edges()])
99 # One source, one sink.
100 if not isinstance(source, list) and not isinstance(sink, list):
101 # Add flow conversation constrains.
102 P.add_list_of_constraints([
103 sum([f[p, i] for p in G.predecessors(i)])
104 == sum([f[i, j] for j in G.successors(i)])
105 for i in G.nodes() if i != sink and i != source])
107 # Source flow at S
108 P.add_constraint(
109 sum([f[p, source] for p in G.predecessors(source)])
110 + flow_value ==
111 sum([f[source, j] for j in G.successors(source)]))
113 # One source, multiple sinks.
114 elif not isinstance(source, list):
115 # Add flow conversation constrains.
116 P.add_list_of_constraints([
117 sum([f[p, i] for p in G.predecessors(i)])
118 == sum([f[i, j] for j in G.successors(i)])
119 for i in G.nodes() if i not in sink and i != source])
121 for k in range(0, len(sink)):
122 # Sink flow at T
123 P.add_constraint(
124 sum([f[p, sink[k]] for p in G.predecessors(sink[k])])
125 == sum([f[sink[k], j] for j in G.successors(sink[k])])
126 + flow_value[k])
128 # Multiple sources, one sink.
129 elif not isinstance(sink, list):
130 # Add flow conversation constrains.
131 P.add_list_of_constraints([
132 sum([f[p, i] for p in G.predecessors(i)])
133 == sum([f[i, j] for j in G.successors(i)])
134 for i in G.nodes() if i not in source and i != sink])
136 for k in range(0, len(source)):
137 # Source flow at T
138 P.add_constraint(sum(
139 [f[p, source[k]] for p in G.predecessors(source[k])])
140 + flow_value[k] ==
141 sum([f[source[k], j] for j in G.successors(source[k])]))
143 # Multiple sources, multiple sinks.
144 # TODO: Recursion adds redundant non-negativity constraints.
145 elif isinstance(sink, list) and isinstance(source, list):
146 SS = list(set(source))
147 TT = list(set(sink))
149 if len(SS) <= len(TT):
150 ftmp = {}
151 for s in SS:
152 ftmp[s] = {}
153 sinks_from_s = [
154 t for (i, t) in enumerate(sink) if source[i] == s]
155 values_from_s = [v for (i, v)
156 in enumerate(flow_value) if source[i] == s]
158 for e in G.edges():
159 ftmp[s][e] = P.add_variable(
160 '__f[{0}][{1}]'.format(s, e), 1)
162 # Immediately convert another FlowConstraint so that the
163 # reformulation created from this conversion doesn't
164 # need to be run twice in a row.
165 cls._convert(cls(
166 G, ftmp[s], source=s, sink=sinks_from_s,
167 flow_value=values_from_s, graphName=graphName), P)
169 P.add_list_of_constraints([
170 f[e] == sum([ftmp[s][e] for s in SS])
171 for e in G.edges()])
172 else:
173 ftmp = {}
174 for t in TT:
175 ftmp[t] = {}
176 sources_to_t = [
177 s for (i, s) in enumerate(source) if sink[i] == t]
178 values_to_t = [v for (i, v) in enumerate(flow_value)
179 if sink[i] == t]
181 for e in G.edges():
182 ftmp[t][e] = P.add_variable(
183 '__f[{0}][{1}]'.format(t, e), 1)
185 # Immediately convert another FlowConstraint so that the
186 # reformulation created from this conversion doesn't
187 # need to be run twice in a row.
188 cls._convert(cls(
189 G, ftmp[t], source=sources_to_t, sink=t,
190 flow_value=values_to_t, graphName=graphName), P)
192 P.add_list_of_constraints([
193 f[e] == sum([ftmp[t][e] for t in TT])
194 for e in G.edges()])
196 else:
197 assert False, "Dijkstra-IF fallthrough."
199 return P
201 def __init__(
202 self, G, f, source, sink, flow_value, capacity=None, graphName=""):
203 """Construct a network flow constraint.
205 :param G: A directed graph.
206 :type G: `networkx DiGraph <http://networkx.lanl.gov/index.html>`_.
208 :param dict f: A dictionary of variables indexed by the edges of ``G``.
210 :param source: Either a node of ``G`` or a list of nodes in case of a
211 multi-source flow.
213 :param sink: Either a node of ``G`` or a list of nodes in case of a
214 multi-sink flow.
216 :param flow_value: The value of the flow, or a list of values in case of
217 a single-source/multi-sink flow. In the latter case, the values
218 represent the demands of each sink (resp. of each source for a
219 multi-source/single-sink flow). The values can be either constants
220 or :class:`~picos.expressions.AffineExpression`.
222 :param capacity: Either ``None`` or a string. If this is a string, it
223 indicates the key of the edge dictionaries of ``G`` that is used for
224 the capacity of the links. Otherwise, edges have an unbounded
225 capacity.
227 :param str graphName: Name of the graph as used in the string
228 representation of the constraint.
229 """
230 if len(f) != len(G.edges()):
231 raise ValueError(
232 "The number of variables does not match the number of edges.")
234 if isinstance(sink, list) and len(sink) == 1:
235 source = source[0]
237 if isinstance(sink, list) and len(sink) == 1:
238 sink = sink[0]
240 if isinstance(source, list) and len(source) != len(flow_value):
241 raise ValueError("The number of sources does not match the number "
242 "of flow values.")
244 if isinstance(sink, list) and len(sink) != len(flow_value):
245 raise ValueError("The number of sinks does not match the number "
246 "of flow values.")
248 if isinstance(source, list) and isinstance(sink, list) \
249 and len(sink) != len(source):
250 raise ValueError("The number of sinks does not match the number "
251 "of sources.")
253 self.graph = G
254 self.f = f
255 self.source = source
256 self.sink = sink
257 self.flow_value = flow_value
258 self.capacity = capacity
259 self.graphName = graphName
261 # Build the string description.
262 if isinstance(source, list):
263 sourceStr = "(" + ",".join(source) + ")"
264 else:
265 sourceStr = str(source)
267 if isinstance(sink, list):
268 sinkStr = "(" + ",".join(sink) + ")"
269 else:
270 sinkStr = str(sink)
272 if isinstance(flow_value, list):
273 valueStr = "values " + ", ".join([v.string if hasattr(v, "string")
274 else str(v) for v in flow_value])
275 else:
276 valueStr = "value " + flow_value.string \
277 if hasattr(flow_value, "string") else str(flow_value)
279 self.comment = "{}{}-{}-flow{} has {}.".format(
280 "Feasible " if capacity is not None else "", sourceStr, sinkStr,
281 " in {}".format(graphName) if graphName else "", valueStr)
283 super(FlowConstraint, self).__init__("Flow")
285 Subtype = namedtuple("Subtype",
286 ("lenV", "lenE", "flowCons", "hasCapacities"))
288 @classmethod
289 def _cost(cls, subtype):
290 return subtype.lenE # Somewhat arbitrary.
292 def _subtype(self):
293 s = len(self.source) if isinstance(self.source, list) else 1
294 t = len(self.sink) if isinstance(self.sink, list) else 1
295 V = len(self.graph.nodes())
296 E = len(self.graph.edges())
298 if s == 1 or t == 1:
299 flowCons = (max(s, t),)
300 else:
301 flowCons = []
302 S, T = self.source, self.sink
303 A, B = set(S), set(T)
304 if len(A) > len(B):
305 S, T = T, S
306 A, B = B, A
307 for s in A:
308 flowCons.append(S.count(s))
309 flowCons = tuple(flowCons)
311 assert sum(flowCons) == max(s, t)
313 return self.Subtype(V, E, flowCons, self.capacity is not None)
315 def _expression_names(self):
316 return
317 yield
319 # HACK: The variables are not stored in named expressions but in a
320 # dictionary. To make prediction work, they must be considered part
321 # of the problem that the flow constraint was added to.
322 @cached_property
323 def mutables(self): # noqa
324 return frozenset(self.f.values())
326 # HACK: See above.
327 def replace_mutables(self, mapping): # noqa
328 f = {key: mapping[var] for key, var in self.f.items()}
329 return FlowConstraint(self.graph, f, self.source, self.sink,
330 self.flow_value, self.capacity, self.graphName)
332 def _str(self):
333 return self.comment
335 def _get_slack(self):
336 raise NotImplementedError
338 def draw(self):
339 """Draw the graph."""
340 G = self.graph
342 import networkx as nx
343 import matplotlib.pyplot as plt
345 pos = nx.spring_layout(G)
346 edge_labels = dict([((u, v,), d["capacity"])
347 for u, v, d in G.edges(data=True)])
348 nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
349 nx.draw(G, pos)
350 plt.show()
353# --------------------------------------
354__all__ = api_end(_API_START, globals())