Finding Eulerian Path in a Directed Graph With Minimal Edge Addition

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

Official comment

Simranjit Kaur

Gurobi Staff

June 23, 2025 02:51 Edited

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

July 12, 2021 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ł

Stuart Horine

July 12, 2021 14:35

You hero! Thanks very much.

Finding Eulerian Path in a Directed Graph With Minimal Edge Addition

Comments

Didn't find what you were looking for?