Is this arc routing formulation correct?

Question

Let $G=(V,E)$ be a graph. I would like to identify an eulerian cycle in $G$ with minimum cost, with an integer programing approach:

$x_{ij}$ are integer variables that denote the number of times that edge $(i,j)$ is used.

$$ \min \; \sum_{(i,j)\in E}c_{ij}x_{ij} $$ subject to: \begin{align} \sum_{i,(i,j)\in E}x_{ij}&=\sum_{i,(j,i)\in E}x_{ji} \quad \forall j \in V \tag{1}\\ x_{ij} &\ge 1 \quad \forall (i,j)\in E \tag{2} \end{align}

Is this a valid formulation? Can I relax the variables to be continuous?

Answer 1

If OP wants an Eulerian cycle, then refer to @prubin's answer. If the graph is not eulerian, then the problem will be infeasible. If the graph is eulerian, then the solution to the problem will give you the direction of each edge in the eulerian circuit. Note that you don't have to go through integer programming to know if the graph is eulerian or not, you can just check if vertices have even degree.

Assuming OP accepts cycles with duplicated edges (in this case we are dealing with the route inspection problem), then replace constraints (2) with: $$ x_{ij}+x_{ji}\ge 1 \quad \forall i\neq j $$ which enforce that edge $(i,j)$ must be used at least once, in any direction (possibly in both).

Answer 2

An Eulerian cycle crosses every edge exactly once (see Wikipedia entry). So in your formulation, which appears to assume a directed graph, for any $(i,j)\in E$ you would need to allow $x_{ij}$ to be either 0 or 1, and add the constraint that $$x_{ij} + x_{ji} = 1 \quad \forall i\neq j.$$ I am assuming that the graph is symmetric ($(i,j)\in E \implies (j,i) \in E$) and contains no self-loops (no $(i,i)\in E$). If the graph is asymmetric, you can set $x_{ij}=1$ whenever $(i,j)\in E$ but $(j,i)\notin E$. If there are self-loops, $(i,i)\in E \implies x_{i,i} = 1.$

Just to clarify, this is only a partial answer. You still have to add a sequencing component (in what order are the edges traversed) and rule out "subpaths" (compositions of disjoint paths, with cycles that do not include the starting/ending node).

Answer 3

In Eulerian circuit, you've to take in all edges, atleast and atmost once. Here cost may be associated with the vertex, as all edges will be included. So cost minimization will depend upon how many times the nodes/vertices are visited/not visited. So for node $v \in\ V$, $S_v \in\ Z^+$
Test for Eulerian cycle first: degrees of all vertices should be even i.e. $\sum_{v \in\ V} E_{u,v} \mod 2 =0 \ \ \forall u \in\ V$

Parameters:
If directed, $Deg_v = \sum_{(u,v)} (E_{u,v}+ E_{v,u})$:
Otherwise: $Deg_v = \sum_{(u,v)} E_{v,u}$:
$(u,v) \in\ $ Edges

Min $\sum_v Cost_v S_v $
s.t.
$1 \le S_v \le Deg_v$
$S_v + \sum_{u\in\ E} S_u \le Deg_v+\sum_{u\in\ E} Deg_u - \sum E_{u,v} \ \ \forall v \in\ $V and E$=E_{u,v}$