[Rule] EulerianPath to ILP

[zhangjieqingithub]

Source

EulerianPath

Target

ILP

Motivation

This rule connects EulerianPath to the existing ILP hub.

It is not the primary algorithmic route, since EulerianPath is already solvable in linear time. But it is still useful because it:

• gives the new model a direct connection into the current reduction graph,
• provides a declarative feasibility formulation for cross-checking witnesses,
• encodes the exact arc-order semantics of the source model, including loops and parallel arcs.

Reference

• J?rgen Ebert, ?Computing Eulerian trails,? Information Processing Letters 28(2):93-97, 1988. https://doi.org/10.1016/0020-0190(88)90170-6
• J?rgen Bang-Jensen, Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd ed., Springer, 2009. https://doi.org/10.1007/978-1-84800-998-1

The concrete ILP below is a direct formulation of the Eulerian-trail witness structure.

Reduction Algorithm

Let the source instance be a directed multigraph
D = (V, A)
with arc occurrences
A = {a_1, ..., a_m}.

For each arc occurrence a, write:

• tail(a) for its tail vertex,
• head(a) for its head vertex.

If m = 0, map to the empty ILP<i32> instance with no variables and no constraints. It is feasible, corresponding to the empty Eulerian trail.

Assume now that m > 0.

Define the compatibility set
P = { (a,b) in A x A : a != b and head(a) = tail(b) }.

Construct an ILP<i32> with the following variables:

1. For each compatible ordered pair (a,b) in P, an integer variable y_ab.
   Intended meaning:

   • y_ab = 1 iff b immediately follows a in the Eulerian trail.

2. For each arc a in A, integer variables s_a and e_a.
   Intended meaning:

   • s_a = 1 iff a is the first arc of the trail,
   • e_a = 1 iff a is the last arc of the trail.

3. For each arc a in A, an integer variable u_a.
   Intended meaning:

   • u_a is the position of a in the trail.

All variables live in the nonnegative-integer domain of ILP<i32>. We force the intended binary behavior with explicit upper bounds.

Constraints

For every arc a in A:

1. Exactly one predecessor or start:
   s_a + sum_{(b,a) in P} y_ba = 1

2. Exactly one successor or end:
   e_a + sum_{(a,b) in P} y_ab = 1

3. Binary upper bounds:

• s_a <= 1
• e_a <= 1
• u_a <= m - 1

For every compatible pair (a,b) in P:

4. Binary upper bound:
   y_ab <= 1

5. Order consistency:
   u_b >= u_a + 1 - m(1 - y_ab)

Finally:

6. Unique start:
   sum_{a in A} s_a = 1

7. Unique end:
   sum_{a in A} e_a = 1

Set the objective to the zero function and use ObjectiveSense::Minimize.

Correctness intuition

• The predecessor and successor equalities force every arc occurrence to appear exactly once in a directed path decomposition.
• The unique start and unique end constraints ensure exactly one distinguished path.
• The compatibility condition is built into the y_ab variables, so consecutive arcs fit head-to-tail.
• Without the order variables, one could still have extra directed cycles disjoint from the main path.
• The order constraints eliminate such cycles: if y_ab = 1, then the position strictly increases from a to b, so a directed cycle is impossible.
• Therefore any feasible ILP solution encodes one directed trail containing every arc occurrence exactly once.
• Conversely, any Eulerian trail defines such variables immediately by reading off its first arc, last arc, immediate-successor relation, and arc positions.

Hence the ILP is feasible iff the source instance is a yes-instance.

Size Overhead

Let

• m = |A| = num_arcs
• p = |P|, the number of compatible ordered arc pairs

Then:

Target metric	Formula
num_vars	3m + p
num_constraints	5m + 2p + 2

Explanation:

• p successor variables,
• m start variables,
• m end variables,
• m order variables,

and constraints:

• m predecessor equations,
• m successor equations,
• 2m upper bounds for s_a, e_a,
• m upper bounds for u_a,
• p upper bounds for y_ab,
• p order constraints,
• 2 global equalities.

Validation Method

• Compare ILP feasibility against the direct Eulerian-path criterion on small instances.
• Include tests with:
  • repeated arcs,
  • loops,
  • isolated vertices,
  • empty-arc instances,
  • yes-instances with open trails,
  • yes-instances with circuits,
  • no-instances failing connectivity,
  • no-instances failing degree balance.
• Extract a source witness by finding the unique start arc and repeatedly following the unique active successor relation.
• Verify that the extracted trail uses every source arc occurrence exactly once.

Example

Take the source instance from the model issue:

• V = {0,1,2}
• A = {a_0, a_1, a_2, a_3}
• a_0 = (0,1)
• a_1 = (0,1)
• a_2 = (1,2)
• a_3 = (2,0)

The compatible ordered pairs are exactly:

• (a_0, a_2)
• (a_1, a_2)
• (a_2, a_3)
• (a_3, a_0)
• (a_3, a_1)

So p = 5.

Variables

• successor variables:
  y_02, y_12, y_23, y_30, y_31
• start variables:
  s_0, s_1, s_2, s_3
• end variables:
  e_0, e_1, e_2, e_3
• order variables:
  u_0, u_1, u_2, u_3

Thus the target has
num_vars = 5 + 12 = 17.

A feasible target solution

Take the Eulerian trail
(a_0, a_2, a_3, a_1).

Set:

• s_0 = 1
• e_1 = 1
• y_02 = 1
• y_23 = 1
• y_31 = 1

and all other s, e, y variables to 0.

Set order variables:

• u_0 = 0
• u_2 = 1
• u_3 = 2
• u_1 = 3

Then:

• every arc has exactly one predecessor or is the start,
• every arc has exactly one successor or is the end,
• all active successor pairs are compatible,
• the order variables increase along active successor links.

So the ILP is feasible, matching the fact that the source instance is a yes-instance.

BibTeX

@book{BangJensenGutin2009Digraphs,
  author    = {J?rgen Bang-Jensen and Gregory Z. Gutin},
  title     = {Digraphs: Theory, Algorithms and Applications},
  edition   = {2},
  publisher = {Springer London},
  year      = {2009},
  doi       = {10.1007/978-1-84800-998-1},
  url       = {https://doi.org/10.1007/978-1-84800-998-1}
}

@article{Ebert1988ComputingEulerianTrails,
  author  = {J?rgen Ebert},
  title   = {Computing Eulerian trails},
  journal = {Information Processing Letters},
  volume  = {28},
  number  = {2},
  pages   = {93--97},
  year    = {1988},
  doi     = {10.1016/0020-0190(88)90170-6},
  url     = {https://doi.org/10.1016/0020-0190(88)90170-6}
}