1
$\begingroup$

I hope you can help me out with this. I'm stuck with an integer programming formulation for the so-called Undirected Chinese Postman Problem.

Consider an undirected graph $G=(V,E)$, where $V$ is the vertex set and E is the set of $edges$. Let $E(S)=\{(i,j) : i\in S, j\in V\setminus S\text{, or } i\in V\setminus S, j\in S\}$ be a subset of odd-degree vertices, $S \subseteq V$ is said to be odd if it is a set consisting of an odd number of odd-degree vertices"

This last odd condition is the one that I’m struggling with.

The formulation is as follows: \begin{align} \min \ &\sum_{(i,j)\in E}c_{ij}x_{ij} \\ \text{Subj to }&\sum_{(i,j)\in E(S)} x_{ij}\geq 1,\quad S\subset V,S\text{ odd} \\ &x_{ij}\geq 0,\quad (i,j)\in E \\ &x_{ij}\in \mathbb{Z},\quad (i,j)\in E \end{align}

According to the first constraint, does it mean that if we have a graph with an even number of odd-degree vertices we can’t solve the CPP? or am I getting it totally wrong?

Consider this particular graph. How would be the formulation for this case? It would be very helpful if you explain the formulation for constraint 1. Thanks!

$\endgroup$
1
  • $\begingroup$ I'm not sure what you are quoting, but I think you are quoting it incorrectly. The sentence "[l]et $E(S)=...$ be a subset of odd-degree vertices ..." is inherently goofy, since $E(S)$ is defined to be a set of edges. $\endgroup$
    – prubin
    Oct 27 '17 at 19:35
0
$\begingroup$

In the pictured graph, the odd-numbered vertices have even degree and the even-numbered vertices have odd degree. So the sets $S$ over which the first constraint is iterated consist of the odd-cardinality subsets of $\{2, 4, 6, 8\}$. There are eight such sets, four singletons and four with cardinality three.

The constraint itself says you need to pick at least one copy of at least one edge that has one endpoint in $S$ and one not in $S$. Since all the edges go between an even-numbered node and an odd-numbered node, every edge incident on a node in $S$ qualifies.

So for $S=\{2\}$, the constraint is $x_{(1,2)}+x_{(2,3)}+x_{(2,9)} \ge 1$. For $S=\{2, 6, 8\}$, the left side of the constraint contains nine of the twelve $x$ variables, omitting $x_{(3, 4)}$, $x_{(4,5)}$ and $x_{(4,9)}$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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