5
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

4
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ Are you assuming that the graph is eulerian (meaning that such a cycle does exist) ? If it does not exist, edges can be "duplicated", or in terms of flows, we can have $x_{ij}>1$. In which case the constraint $x_{ij}+x_{ji}=1$ would be too restrictive I believe. The optimal solution could be $x_{ji}=0$ and $x_{ij}=2$ ? $\endgroup$
    – Kuifje
    Jan 8 at 20:39
  • $\begingroup$ I'm assuming that either an Eulerian cycle exists or the problem does not have a feasible solution. Since the question specifies a minimum cost Eulerian cycle, I assume any solution that is not a E-cycle would be unacceptable. $\endgroup$
    – prubin
    Jan 8 at 22:15
  • $\begingroup$ fair enough! :) $\endgroup$
    – Kuifje
    Jan 8 at 22:23
  • $\begingroup$ @Kuifje I upvoted your solution for the more general case. $\endgroup$
    – prubin
    Jan 8 at 23:34
  • $\begingroup$ needless to say I upvoted yours. $\endgroup$
    – Kuifje
    Jan 9 at 8:32
1
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.