4
$\begingroup$

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)?

$\endgroup$

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.