Polytope analysis#
Computing kernel basis#
The graph edge kernel describes the degree of freedom of the feasible matching rates, if any.
Stochastic Matching provides tools to compute and display the edge kernel.
Examples of 1-D kernels#
Diamond#
[1]:
import stochastic_matching as sm
diamond = sm.CycleChain(names=[str(i) for i in [1, 2, 3, 4]])
diamond.kernel
[1]:
Kernels of a graph with 4 nodes and 5 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[ 1 -1 0 -1 1]]
[2]:
diamond.show_kernel(disp_rates=False)
Note
The edge without value does not belong to the support of the kernel, i.e. for a given problem \((G, \lambda)\), its matching rate is the same for all stable policies.
Unbalanced Kayak Paddle#
[3]:
kayak = sm.KayakPaddle(k=3,l=2,m=5, names=[str(i+1) for i in range(9)])
kayak.kernel
[3]:
Kernels of a graph with 9 nodes and 10 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[-1 1 1 -2 2 -1 -1 1 -1 1]]
[4]:
kayak.show_kernel(disp_rates=False)
Hypergraphs#
The simplest 1-D hypergraph is two connected nodes with abandonment. The degree of liberty is then: match items or not.
Note
For hypergraphs, the kernel algorithm is optimized in a generic way, not using the edge-cycle algorithm, which only works on simple graphs.
[5]:
two_nodes = sm.Model(incidence=[[1, 0, 1],[0, 1, 1]], names=["1", "2"])
two_nodes.kernel
[5]:
Kernels of a graph with 2 nodes and 3 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[-0.57735027 -0.57735027 0.57735027]]
[6]:
two_nodes.show_kernel(disp_rates=False)
Note
For hypergraphs, we use the standard representation as a bipartite graph with nodes on what side and hyperedges on the other side. However, by default, we do not enforce a physical separation with actual left and right parts. This is a deliberate choice as we find the hypergraphs easier to read without a physical separation, especially if there are close to a simple graph. However, the option exists. You can for example compare the following hypergraph, which is a regular two-way triangle with one additional multi-way match involving 6 items (1 of type \(A\), 2 of type \(B\), 3 of type \(C\)), in both representations:
[29]:
import numpy as np
hypertriangle = sm.Model(incidence=np.hstack([sm.Cycle(n=3).incidence, np.array([[1, 2, 3]]).T]), names="alpha")
hypertriangle.show_kernel(disp_rates=False)
[30]:
hypertriangle.show_kernel(disp_rates=False, bipartite=True)
Examples of 2-D kernels#
Co-Domino#
[9]:
codomino = sm.Codomino(names=["1", "2", "6", "5", "3", "4"])
codomino.kernel
[9]:
Kernels of a graph with 6 nodes and 8 edges.
Node dimension is 0.
Edge dimension is 2
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[ 0 0 1 -1 -1 1 0 0]
[ 1 -1 0 -1 1 0 -1 1]]
[10]:
codomino.show_kernel(disp_rates=False)
For multi-dimensional kernels, the possible basis are not unique. However, one can hint at a specific basis by specifying seed edges (cf paper).
[11]:
codomino.seeds = [0, 3]
codomino.kernel
[11]:
Kernels of a graph with 6 nodes and 8 edges.
Node dimension is 0.
Edge dimension is 2
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[ 1 -1 -1 0 2 -1 -1 1]
[ 0 0 -1 1 1 -1 0 0]]
[12]:
codomino.show_kernel(disp_rates=False)
Triamond#
[13]:
triamond = sm.CycleChain(c=3, names=[str(i) for i in [1, 5, 2, 4, 3]])
triamond.seeds = [1, 3]
triamond.show_kernel(disp_rates=False)
[14]:
triamond.seeds = [4, 2]
triamond.show_kernel(disp_rates=False)
Vertices#
Co-domino variations#
Just by changing the arrival rates, one can change a lot the properties of the polytope of feasible matching rates. Using the codomino graph (one of the smallest possible simple graph with a 2-D kernel), one can observe how different the polytope can be.
Mix of injective-only and bijective vertices#
By default, arrival rates are proportional to node degrees. This often yields to many injective-only vertices, as shown by the codomino.
[15]:
codomino.seeds = [1, 2] # We use the seeds to select a kernel basis
codomino.show_kernel(disp_flow=True, disp_rates=False)
[16]:
def show_vertices(model):
for i, v in enumerate(model.vertices):
model.show_vertex(i, disp_rates=False)
print(f"Vertex of coordinates {str(v['edge_coordinates'])} (edge) / {v['kernel_coordinates']} (kernel) is {'bijective' if v['bijective'] else 'injective'}.")
show_vertices(codomino)
Vertex of coordinates [2. 0. 0. 1. 3. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is injective.
Vertex of coordinates [2. 0. 1. 0. 2. 1. 0. 2.] (edge) / [-1. 0.] (kernel) is injective.
Vertex of coordinates [1. 1. 2. 0. 0. 2. 1. 1.] (edge) / [0. 1.] (kernel) is bijective.
Vertex of coordinates [0. 2. 0. 3. 1. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is injective.
Vertex of coordinates [0. 2. 1. 2. 0. 1. 2. 0.] (edge) / [1. 0.] (kernel) is injective.
3 injective-only vertices#
[17]:
codomino.rates = [2, 4, 2, 2, 4, 2]
# We shift the base_flow so coordinates are simpler
codomino.base_flow = codomino.kernel_to_edge([1/3, 0])
codomino.show_kernel(disp_flow=True, disp_rates=False)
[18]:
show_vertices(codomino)
Vertex of coordinates [2. 0. 2. 0. 0. 2. 0. 2.] (edge) / [-1. 1.] (kernel) is injective.
Vertex of coordinates [2. 0. 0. 2. 2. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is injective.
Vertex of coordinates [0. 2. 0. 4. 0. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is injective.
3 bijective vertices#
[19]:
codomino.rates = [4, 4, 4, 3, 3, 4]
codomino.base_flow = codomino.kernel_to_edge([0, -1/4])
codomino.show_kernel(disp_flow=True, disp_rates=False)
[20]:
show_vertices(codomino)
Vertex of coordinates [3. 1. 1. 0. 2. 0. 1. 3.] (edge) / [-1. 0.] (kernel) is bijective.
Vertex of coordinates [2. 2. 2. 0. 0. 1. 2. 2.] (edge) / [0. 1.] (kernel) is bijective.
Vertex of coordinates [1. 3. 1. 2. 0. 0. 3. 1.] (edge) / [1. 0.] (kernel) is bijective.
5 bijective vertices#
[21]:
codomino.rates = [4, 5, 5, 3, 3, 2]
codomino.base_flow = codomino.kernel_to_edge([0, 1/4])
codomino.show_kernel(disp_rates=False, disp_flow=True)
[22]:
show_vertices(codomino)
Vertex of coordinates [3. 1. 1. 1. 3. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is bijective.
Vertex of coordinates [3. 1. 2. 0. 2. 1. 0. 2.] (edge) / [-1. 0.] (kernel) is bijective.
Vertex of coordinates [2. 2. 3. 0. 0. 2. 1. 1.] (edge) / [0. 1.] (kernel) is bijective.
Vertex of coordinates [1. 3. 2. 2. 0. 1. 2. 0.] (edge) / [1. 0.] (kernel) is bijective.
Vertex of coordinates [1. 3. 1. 3. 1. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is bijective.
Pyramid polytope#
Starting from 3-D kernels, it is possible to have an injective-only vertex even if all tight edges are irredundant. One of the simple example is the Egyptian pyramid, where 4 distinct planes intersect at one point (the top of the pyramid). The following model was specifically designed so that its polytope is pyramid-shaped.
[23]:
pyramid = sm.Pyramid(
rates=[4, 3, 3, 3, 6, 6, 3, 4, 4, 4],
names=["9", "2", "1", "8", "7", "3", "4", "5", "6", "10"],
)
pyramid.seeds = [0, 12, 2]
pyramid.base_flow = pyramid.kernel_to_edge([1 / 6, 1 / 6, 1 / 6])
pyramid.show_kernel(disp_flow=True, disp_rates=False)
[24]:
show_vertices(pyramid)
Vertex of coordinates [1. 3. 0. 2. 0. 3. 3. 0. 1. 2. 1. 1. 3.] (edge) / [-1. 1. 0.] (kernel) is bijective.
Vertex of coordinates [1. 3. 0. 2. 0. 3. 1. 2. 3. 0. 1. 3. 1.] (edge) / [-1. -1. 0.] (kernel) is bijective.
Vertex of coordinates [2. 2. 1. 0. 0. 3. 3. 0. 3. 0. 2. 2. 2.] (edge) / [0. 0. 1.] (kernel) is injective.
Vertex of coordinates [3. 1. 0. 0. 2. 1. 3. 2. 3. 0. 1. 3. 1.] (edge) / [ 1. -1. 0.] (kernel) is bijective.
Vertex of coordinates [3. 1. 0. 0. 2. 1. 5. 0. 1. 2. 1. 1. 3.] (edge) / [1. 1. 0.] (kernel) is bijective.