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 thata) the formulation is indeed correctb) 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.  
Totally unimodular <=> polynomial time?
complexity theory;graph theory;np complete;integer programming