2
$\begingroup$

Crossposting due to recommendation.

I formulated a MIP problem which I didn't expect to be unimodular. The problem is to find a minimum complete sequence in a strongly connected digraph. That is, minimize the number of edges such that connectivity is preserved, using only previously existant edges. This will be a Hamiltonian cycle if such a cycle exists.

I've verified it with AMPL/CPLEX and it at least seems to be a correct formulation. Solving the LP-relaxation, I found that it consistently provides IP-feasible solutions.

But the issue is that the minimum complete sequence problem is NP-complete. Is it even possible that I have a correct formulation given that I get a TU constraint matrix? Any ideas on how to prove that it's TU (I'm far from an expert on this thing)?

Here's the model (option relax_integrality 1; for the LP-relaxation)

$\begin{align} \min \sum_{i,j} x_{ij} &\\ \sum_j x_{ij} &\geq 1 & \forall i\\ \sum_i x_{ji} &= \sum_i x_{ij} & \forall j \\ \sum_n y_{ij}^n &\geq 1 & \forall i,j \\ y_{ij}^1 &= x_{ij} & \forall i,j\\ x_{ij} &\leq z_{ij} & \forall i,j\\ y_{ij}^n &\leq (y_{ik}^{n-1}+x_{kj} - 1) + M(1-b_{ij}^{nk}) & \forall n \neq 1, i, j, k\\ \sum_k b_{ij}^{nk} &\geq 1 & \forall i,j,n \\ x,y,b &\in \{0,1\} \end{align} $

$y^n_{ij} = 1$ iff there exists a path of length $n$ from $i$ to $j$. $z_{ij} = 1$ implies that the edge $i,j$ exists in the original graph. $b$ is a binary hack to formulate the connectivity constraint.

edit: $i,j,k,n$ all range from $1$ to $N = $ number of nodes. I realize that the constraint matrix actually can't be unimodular due to the presence of $M$ which is some arbitrarily large number. But the LP-relaxation constantly spits out integer feasible solutions, which for smaller graphs actually correspond to known optima and for larger graphs seems to check out as well.

edit: After examining the problem closer, I found that

a) the formulation is indeed correct

b) the linear relaxation consistently provides integer solutions with respect to x and y, but NOT b. It seems as though the b:s are basically conspiring to turn the problem totally unimodular. Setting $M = 10000$, b would constantly set itself to 0.99999 to minimize slack. This makes the x and y variables ONLY take on binary values. This is maybe obvious to experts but I found it extremely surprising. I have yet to see a case where it doesn't find the actual optimum, but this is probably due to a lacking setup of example graphs.

$\endgroup$
  • 1
    $\begingroup$ I have not proof-read the question, but I have a general comment. If the problem is NP-complete, it is "extremely unlikely" that we have found a polynomial time algorithm to solve it. Sometimes a problem might have a seemingly efficient formulation (such as a linear program), but the complexity can still blow up due to the number of constraints (or variables), or the complexity required to form the constraints. $\endgroup$ – megas Mar 11 '15 at 17:24
  • $\begingroup$ Yes, to clarify, I don't believe I have proven P=NP :) $\endgroup$ – Benjamin Lindqvist Mar 11 '15 at 17:27
  • $\begingroup$ But it still seems as if the number of constraints grows as O(n^4)... $\endgroup$ – Benjamin Lindqvist Mar 11 '15 at 17:29
  • 1
    $\begingroup$ Typo in 2nd constraint. Also, 6th constraint, what is $k$ on the right hand side? (The constraint is repeated only for $i,j$. What is $M$? $\endgroup$ – megas Mar 11 '15 at 17:42
  • 2
    $\begingroup$ Cross-posted on Math.SE: math.stackexchange.com/q/1184965/14578. Please don't cross-post, as it violates site rules. For the future: well, you weren't actually recommended to cross-post: saying that a question might be better elsewhere isn't an invitation/suggestion to cross-post, though I realize that could be confusing or unclear, especially to new users. $\endgroup$ – D.W. Mar 11 '15 at 18:08

Your Answer

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

Browse other questions tagged or ask your own question.