highs-sys 1.14.0

Rust binding for the HiGHS linear programming solver. See http://highs.dev.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# Example of a shortest path network flow in a graph
# Shows integration of highspy with networkx

import highspy
import networkx as nx

orig, dest = ('A', 'D')

# create directed graph with edge weights (distances)
G = nx.DiGraph()
G.add_weighted_edges_from([('A', 'B', 2.0), ('B', 'C', 3.0), ('A', 'C', 1.5), ('B', 'D', 2.5), ('C', 'D', 1.0)])

h = highspy.Highs()
h.silent()

x = h.addBinaries(G.edges, obj=nx.get_edge_attributes(G, 'weight'))

# add flow conservation constraints
#                        {  1  if n = orig
#   sum(out) - sum(in) = { -1  if n = dest
#                        {  0     otherwise
rhs  = lambda n: 1 if n == orig else -1 if n == dest else 0
flow = lambda E: h.qsum((x[e] for e in E))

h.addConstrs(flow(G.out_edges(n)) - flow(G.in_edges(n)) == rhs(n) for n in G.nodes)
h.minimize()

# Print the solution
print('Shortest path from', orig, 'to', dest, 'is: ', end = '')
sol = h.vals(x)

n = orig
while n != dest:
    print(n, end=' ')
    n = next(e[1] for e in G.out_edges(n) if sol[e] > 0.5)

print(dest)