1
$\begingroup$

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?

$\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.