Finding Eulerian Path in a Directed Graph With Minimal Edge Addition

回答済み

Stuart Horine

2021年07月11日 11:43

• 
• 
• 

Hi All,

I am trying to find an Eulerian Path within a directed graph by duplicating edges, at minimum cost.

To try to get this working I've manufactured a digraph with such a path.
In the below:
var_edges = the number of edges in my graph
var_nodes = the number of nodes
gr_csr is an oriented sparse incidence matrix i.e. gr_csr(i,j) = 1 if edge j leaves node i and gr_csr(i,j) = -1 if edge j enters node i
x is a vector variable that specifies how many of each edge I need
y is the result of the matrix multiplication with x

So x is what I am trying to minimise.
And the constraints are:
I expect the sum of the resulting vector y to be 0
I can have at most 2 odd degree vertices, one +1 one -1. (I expressed this by multiplying the vector by itself and so the result will be at most 2 (-1*-1 + 1*1).
I must have at least one of each edge (I'm only duplicating not removing any edge)

This is the code:

m = gp.Model("Eulerian Path")
x = m.addMVar(shape=var_edges, vtype=GRB.INTEGER, name="x")
y = m.addMVar(shape=var_nodes, vtype=GRB.INTEGER, name="y")

m.addConstr(gr_csr @ x == y, name="MatrixMul")
m.addConstr(y.sum() == 0, name="SumEqZero")
m.addConstr(y @ y <= 2, name="TwoOnesOnly")
for i in range(var_edges):
   m.addConstr(x[i] >= 1, name="row"+str(i))

m.setObjective(x.sum(), GRB.MINIMIZE)
m.optimize()

However, when fed my graph it says the "Model is infeasible".
I have looked at the LP file and it makes sense apart from the MatrixMul constraint..

Subject To
MatrixMul[0]: - x[0] - x[1] + x[3] - y[0] = 0
MatrixMul[1]: x[0] - x[2] - y[1] = 0
MatrixMul[2]: x[2] - x[3] - y[2] = 0
MatrixMul[3]: x[1] - x[4] - y[3] = 0
MatrixMul[4]: x[4] - x[5] - y[4] = 0
MatrixMul[5]: x[5] - x[6] - y[5] = 0
MatrixMul[6]: x[6] - x[7] - y[6] = 0
MatrixMul[7]: x[7] - x[8] - y[7] = 0
MatrixMul[8]: x[8] - x[9] - y[8] = 0
MatrixMul[9]: x[9] - y[9] = 0

Can anyone help me to understand why this does not work?
Many thanks

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年06月23日 02:51 編集済み

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  2021年07月12日 10:25

  Hi Stuart,

  You might be interested in the Knowledge Base article How do I determine why my model is infeasible?

  Moreover, note that the default lower bound for variables is 0. If I understand correctly, your \(\texttt{y}\) variables can also be negative, so redefining them as

  y = m.addMVar(shape=var_nodes, lb= -GRB.INFINITY, vtype=GRB.INTEGER, name="y")

  should help.

  Best regards,
  Jaromił

  0
• 

  Stuart Horine

  2021年07月12日 14:35

  • 
  • 
  • 

  You hero! Thanks very much.

  0

投稿コメントは受け付けていません。