I need to solve the following binary integer linear program: $$ \max \textbf{c}^T \textbf{x} $$ Subject to: $$ \textbf{Ax} \le \textbf{b} $$ Where $ \textbf{b} \in \mathbb{Z}^n $, $\textbf{A} \in \mathbb{Z}^{m \times n} $, all the entries of $\textbf{c}$ are equal to $1$ and all the entries of $\textbf{x}$ are either $0$ or $1$. I thought about relaxing the problem by allowing the entries of $\textbf{x}$ to be real numbers between $0$ and $1$, and then solving the relaxed problem using Simplex. However, in order to ensure integral solutions from Simplex, the program must be Totally Dual Integral (TDI). Total unimodularity is unfeasible because $\textbf{A}$ can have entries different from $\pm 1$. I read that a linear program can be converted into a TDI one by adding sufficiently many redundant inequalities, as long as the polyhedron defined by $\textbf{Ax} \le \textbf{b}$ is rational (Giles-Pulleyblank theorem). However, I have not found an algorithmic way of defining these redundant constraints. Is it possible to convert the relaxed problem into a TDI one, by using a general construction of redundant inequalities?


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.