I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject to: $$\begin{align} \sum_{s \in S} k_s^t = 1 \quad &\forall t \in T\\ \sum_{s \in S} k_s^t \gamma_{s,p} = \alpha_{p,t} \quad &\forall p \in P, \forall t \in T \\ k_s^t \in \{0,1\} \quad &\forall s \in S, \forall t \in T \end{align}$$

where $c_s$ is an integral cost vector and $\gamma_{s,p}$, $\alpha_{p,t}$ are 0-1 matrices. There is some structure in the ILP in the sense that $|S| = 2^{|P|}$ (i.e. $S$ represents all the combinations of the elements of $P$).

My first guess was that the constraint coefficient matrix $A$ may be Totally Unimodular (TU). Here an instance of this matrix when $|T|=1$ and $|P|=3$:

$$A = \left[\begin{array}{cccccccc} 1&1&1&1&1&1&1&1\\ 0&1&0&0&1&1&0&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&0&1&1&1\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1\\ \end{array}\right]$$

From the definition of TU it seems that this matrix is not TU: the submatrix $A'$ composed by the 2nd to 4th rows and 5th to 7th columns is:

$$A' = \left[\begin{array}{ccc} 1&1&0\\ 1&0&1\\ 0&1&1\\ \end{array}\right]$$

and its determinant is $|A'| = -2 \not\in\{-1,0,1\}$. Am I missing something here? If not, that is, $A$ is indeed not TU, then I feel that the only reason that my relaxed ILP is always integral is due to some optimality conditions.

I solved the relaxed ILP multiple times with $|T| \geq 10$ and $|P| = 10$, with several cost vector and binary matrices $\alpha_{p,t}$ and the solution is always integral. How could I proceed in analytically showing or disproving this (if the integrality property actually doesn't hold)?


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.