Search code examples
pythonnetworkxpyomodirected-graphundirected-graph

Sparse sets in Pyomo for representing arc / edge sets in graph/network models

I have no clue how to define an edge set in pyomo.

I have a very-low-density (sparse) network (aka graph), where the number of edges is much less than a fully-connected graph.

I want to define an edge set so I can construct constraints that have to do with the edges. However I cannot wrap my mind around what pyomo expects me to do, and everything I do results in incredibly-unhelpful error messages.

import pyomo
import pyomo.environ as pe
edges = [(0,1),(0,2),(1,2),(2,3),(2,4),(3,4)]

model = pe.ConcreteModel()
model.E = pe.Set(initialize=lambda _,i : edges[i]) # Edge set

The above code throws the error 

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\block.py", line 568, in __setattr__
    self.add_component(name, val)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\block.py", line 1008, in add_component
    val.construct(data)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\sets.py", line 1221, in construct
    self.add(val)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\sets.py", line 821, in add
    self._verify(tmp)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\sets.py", line 772, in _verify
    raise ValueError("The value="+str(element)+" is a tuple for set="+self.name+", which has dimen="+str(self.dimen))
ValueError: The value=(0, 2) is a tuple for set=E, which has dimen=1

A given edge is completely identified by a tuple. The edge connecting node 0 and node 1 should be (0,1). That tuple should be its identifier. A list of such identifiers has dimension 1. So I'm not sure what pyomo expects me to do.

Solution

  • So it turns out that dim is the dimensionality of the set itself. dimen is the number of elements that each set element must contain, not the dimensionality of the set. Pyomo assumes as default that dimen=1, which means that Set will not accept a tuple as a set element because it has more than one element. Setting dimen=None disables this argument checking.

    Thus one way is to pass a list of edges for initialize, with dimension 2 or None.

    model.E = pe.Set(initialize=edges, dimen=2)

    The set constructor does not know the number of elements so this doesn't actually work:

    model.E = pe.Set(initialize=lambda _,i: edges[i], dimen=2) # Edge set

    error: 

    Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\block.py", line 568, in __setattr__
    self.add_component(name, val)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\block.py", line 1008, in add_component
    val.construct(data)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\sets.py", line 1223, in construct
    val = apply_indexed_rule(self, self.initialize, self._parent(), ctr)
  File "C:\Users\Joey\Python37\lib\site-packages\pyomo\core\base\misc.py", line 61, in apply_indexed_rule
    return rule(model, index)
  File "<stdin>", line 1, in <lambda>
IndexError: list index out of range

    So you would have to use

    model.E = pe.Set(initialize=
    (edges[i] for i in range(len(edges))), dimen=2) # Edge set