Source code for picos.constraints.con_flow

# ------------------------------------------------------------------------------
# Copyright (C) 2012-2017 Guillaume Sagnol
# Copyright (C) 2018-2019 Maximilian Stahlberg
#
# This file is part of PICOS.
#
# PICOS is free software: you can redistribute it and/or modify it under the
# terms of the GNU General Public License as published by the Free Software
# Foundation, either version 3 of the License, or (at your option) any later
# version.
#
# PICOS is distributed in the hope that it will be useful, but WITHOUT ANY
# WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
# A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along with
# this program.  If not, see <http://www.gnu.org/licenses/>.
# ------------------------------------------------------------------------------

"""Implementation of :class:`FlowConstraint`."""

from collections import namedtuple

from ..apidoc import api_end, api_start
from ..caching import cached_property
from .constraint import Constraint, ConstraintConversion

_API_START = api_start(globals())
# -------------------------------


[docs]class FlowConstraint(Constraint): """Network flow constraint. .. note :: Unlike other :class:`~.constraint.Constraint` implementations, this one is instanciated by the user (via a wrapper function), so it is raising exceptions instead of making assertions. """
[docs] class Conversion(ConstraintConversion): """Network flow constraint conversion."""
[docs] @classmethod def predict(cls, subtype, options): """Implement :meth:`~.constraint.ConstraintConversion.predict`.""" from ..expressions import RealVariable from . import AffineConstraint numNodes, numEdges, flowCons, hasCapacities = subtype V, E = numNodes, numEdges # Capacity and non-negativity constraints. yield ("con", AffineConstraint.make_type(dim=1, eq=False), 2*E if hasCapacities else E) if len(flowCons) == 1: yield ("con", AffineConstraint.make_type(dim=1, eq=True), V - 1) else: for k in flowCons: yield ("var", RealVariable.make_var_type(dim=1, bnd=0), E) for addition in cls.predict((V, E, (k,), False), options): yield addition yield ("con", AffineConstraint.make_type(dim=1, eq=True), E)
[docs] @classmethod def convert(cls, con, options): """Implement :meth:`~.constraint.ConstraintConversion.convert`.""" from ..modeling import Problem P = Problem() return cls._convert(con, P) # Allow for recursion.
@classmethod def _convert(cls, con, P): from ..expressions import new_param, sum G = con.graph f = con.f source = con.source sink = con.sink flow_value = con.flow_value capacity = con.capacity graphName = con.graphName # Add capacity constraints. if capacity is not None: c = {} for v, w, data in G.edges(data=True): c[(v, w)] = data[capacity] c = new_param('c', c) P.add_list_of_constraints([f[e] <= c[e] for e in G.edges()]) # Add non-negativity constraints. P.add_list_of_constraints([f[e] >= 0 for e in G.edges()]) # One source, one sink. if not isinstance(source, list) and not isinstance(sink, list): # Add flow conversation constrains. P.add_list_of_constraints([ sum([f[p, i] for p in G.predecessors(i)]) == sum([f[i, j] for j in G.successors(i)]) for i in G.nodes() if i != sink and i != source]) # Source flow at S P.add_constraint( sum([f[p, source] for p in G.predecessors(source)]) + flow_value == sum([f[source, j] for j in G.successors(source)])) # One source, multiple sinks. elif not isinstance(source, list): # Add flow conversation constrains. P.add_list_of_constraints([ sum([f[p, i] for p in G.predecessors(i)]) == sum([f[i, j] for j in G.successors(i)]) for i in G.nodes() if i not in sink and i != source]) for k in range(0, len(sink)): # Sink flow at T P.add_constraint( sum([f[p, sink[k]] for p in G.predecessors(sink[k])]) == sum([f[sink[k], j] for j in G.successors(sink[k])]) + flow_value[k]) # Multiple sources, one sink. elif not isinstance(sink, list): # Add flow conversation constrains. P.add_list_of_constraints([ sum([f[p, i] for p in G.predecessors(i)]) == sum([f[i, j] for j in G.successors(i)]) for i in G.nodes() if i not in source and i != sink]) for k in range(0, len(source)): # Source flow at T P.add_constraint(sum( [f[p, source[k]] for p in G.predecessors(source[k])]) + flow_value[k] == sum([f[source[k], j] for j in G.successors(source[k])])) # Multiple sources, multiple sinks. # TODO: Recursion adds redundant non-negativity constraints. elif isinstance(sink, list) and isinstance(source, list): SS = list(set(source)) TT = list(set(sink)) if len(SS) <= len(TT): ftmp = {} for s in SS: ftmp[s] = {} sinks_from_s = [ t for (i, t) in enumerate(sink) if source[i] == s] values_from_s = [v for (i, v) in enumerate(flow_value) if source[i] == s] for e in G.edges(): ftmp[s][e] = P.add_variable( '__f[{0}][{1}]'.format(s, e), 1) # Immediately convert another FlowConstraint so that the # reformulation created from this conversion doesn't # need to be run twice in a row. cls._convert(cls( G, ftmp[s], source=s, sink=sinks_from_s, flow_value=values_from_s, graphName=graphName), P) P.add_list_of_constraints([ f[e] == sum([ftmp[s][e] for s in SS]) for e in G.edges()]) else: ftmp = {} for t in TT: ftmp[t] = {} sources_to_t = [ s for (i, s) in enumerate(source) if sink[i] == t] values_to_t = [v for (i, v) in enumerate(flow_value) if sink[i] == t] for e in G.edges(): ftmp[t][e] = P.add_variable( '__f[{0}][{1}]'.format(t, e), 1) # Immediately convert another FlowConstraint so that the # reformulation created from this conversion doesn't # need to be run twice in a row. cls._convert(cls( G, ftmp[t], source=sources_to_t, sink=t, flow_value=values_to_t, graphName=graphName), P) P.add_list_of_constraints([ f[e] == sum([ftmp[t][e] for t in TT]) for e in G.edges()]) else: assert False, "Dijkstra-IF fallthrough." return P
[docs] def __init__( self, G, f, source, sink, flow_value, capacity=None, graphName=""): """Construct a network flow constraint. :param G: A directed graph. :type G: `networkx DiGraph <http://networkx.lanl.gov/index.html>`_. :param dict f: A dictionary of variables indexed by the edges of ``G``. :param source: Either a node of ``G`` or a list of nodes in case of a multi-source flow. :param sink: Either a node of ``G`` or a list of nodes in case of a multi-sink flow. :param flow_value: The value of the flow, or a list of values in case of a single-source/multi-sink flow. In the latter case, the values represent the demands of each sink (resp. of each source for a multi-source/single-sink flow). The values can be either constants or :class:`~picos.expressions.AffineExpression`. :param capacity: Either ``None`` or a string. If this is a string, it indicates the key of the edge dictionaries of ``G`` that is used for the capacity of the links. Otherwise, edges have an unbounded capacity. :param str graphName: Name of the graph as used in the string representation of the constraint. """ if len(f) != len(G.edges()): raise ValueError( "The number of variables does not match the number of edges.") if isinstance(sink, list) and len(sink) == 1: source = source[0] if isinstance(sink, list) and len(sink) == 1: sink = sink[0] if isinstance(source, list) and len(source) != len(flow_value): raise ValueError("The number of sources does not match the number " "of flow values.") if isinstance(sink, list) and len(sink) != len(flow_value): raise ValueError("The number of sinks does not match the number " "of flow values.") if isinstance(source, list) and isinstance(sink, list) \ and len(sink) != len(source): raise ValueError("The number of sinks does not match the number " "of sources.") self.graph = G self.f = f self.source = source self.sink = sink self.flow_value = flow_value self.capacity = capacity self.graphName = graphName # Build the string description. if isinstance(source, list): sourceStr = "(" + ",".join(source) + ")" else: sourceStr = str(source) if isinstance(sink, list): sinkStr = "(" + ",".join(sink) + ")" else: sinkStr = str(sink) if isinstance(flow_value, list): valueStr = "values " + ", ".join([v.string if hasattr(v, "string") else str(v) for v in flow_value]) else: valueStr = "value " + flow_value.string \ if hasattr(flow_value, "string") else str(flow_value) self.comment = "{}{}-{}-flow{} has {}.".format( "Feasible " if capacity is not None else "", sourceStr, sinkStr, " in {}".format(graphName) if graphName else "", valueStr) super(FlowConstraint, self).__init__("Flow")
Subtype = namedtuple("Subtype", ("lenV", "lenE", "flowCons", "hasCapacities")) @classmethod def _cost(cls, subtype): return subtype.lenE # Somewhat arbitrary. def _subtype(self): s = len(self.source) if isinstance(self.source, list) else 1 t = len(self.sink) if isinstance(self.sink, list) else 1 V = len(self.graph.nodes()) E = len(self.graph.edges()) if s == 1 or t == 1: flowCons = (max(s, t),) else: flowCons = [] S, T = self.source, self.sink A, B = set(S), set(T) if len(A) > len(B): S, T = T, S A, B = B, A for s in A: flowCons.append(S.count(s)) flowCons = tuple(flowCons) assert sum(flowCons) == max(s, t) return self.Subtype(V, E, flowCons, self.capacity is not None) def _expression_names(self): return yield # HACK: The variables are not stored in named expressions but in a # dictionary. To make prediction work, they must be considered part # of the problem that the flow constraint was added to.
[docs] @cached_property def mutables(self): # noqa return frozenset(self.f.values())
# HACK: See above.
[docs] def replace_mutables(self, mapping): # noqa f = {key: mapping[var] for key, var in self.f.items()} return FlowConstraint(self.graph, f, self.source, self.sink, self.flow_value, self.capacity, self.graphName)
def _str(self): return self.comment def _get_slack(self): raise NotImplementedError
[docs] def draw(self): """Draw the graph.""" G = self.graph import networkx as nx import matplotlib.pyplot as plt pos = nx.spring_layout(G) edge_labels = dict([((u, v,), d["capacity"]) for u, v, d in G.edges(data=True)]) nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) nx.draw(G, pos) plt.show()
# -------------------------------------- __all__ = api_end(_API_START, globals())