0
$\begingroup$

I want to solve the problem of minimizing $$\mathbf{c}^T\mathbf{x}$$ subject to the condition that $$A\mathbf{x} = \mathbf{b}\text{,}$$ where $\mathbf{b},\mathbf{c}$ are given vectors in $\mathbb{F}_2^n$, $A$ is a given matrix in $\mathbb{F}_2^{n\times n}$ and $\mathbf{x}$ is a vector of unknowns in $\mathbb{F}_2^n$.

After a little research I now know that this is called a Binary Integer Programming problem, and lots of literature has been written on it. Unfortunately I lack any background on optimization or linear programming, therefore I'm having a hard time understanding which results can I use to implement a Python program that solves this particular problem.

Which algorithms, methods or techniques can I use to solve this kind of problem?

If it helps, the matrix $A$ has the same shape of this other question of mine, reproduced here for convenience:

$$ \begin{bmatrix} J_n & I_n & \dots & I_n \\ I_n & J_n & \ddots & \vdots \\ \vdots & \ddots & \ddots & I_n \\ I_n & \dots & I_n & J_n \end{bmatrix} $$

where $I_n$ is the identity matrix of side $n$ and $J_n$ is the matrix of all ones of the same side.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm not an expert on IP by any stretch of the imagination. However, most of the algorithms I've seen are either cutting plane algorithms or branch and bound algorithms. It is really worthwhile to have some understanding of polyhedral theory first, though.

A cutting plane algorithm is an inequality $a^{T}x \leq b$ that is valid for our polyhedron. We then floor $b$ and cut off portions of the Polyhedron to reduce our search space. This is called a Chvatal-Gomory Cut.

Branch and bound looks at components of the solution vector to the LP relaxation. It then takes a component that is a fraction and considers cases in which that component is either a $0$ or $1$, fixes the value, and then solves the LP relaxation again.

If you can prove that the matrix is totally unimodular (TU), then you can simply solve the LP and that will give you an integer solution. Note that $A$ is iff it has all entries in $\{0, -1, 1\}$ and the determinant of every minor of $A$ is in $\{0, 1, -1\}$.

These lecture notes are worthwhile to work through: http://optimierung.mathematik.uni-kl.de/~krumke/Notes/ip-lecture-new.pdf

I'm finishing up an IP class now, and I will say that there isn't a lot of material I've found that really does a good job with examples. The material is also quite tough. My understanding is a bit weak, so hopefully someone can add more insight. Regardless, I hope this helps in some way! Best of luck. :-)

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. Unfortunately my matrices are not unimodular (for instance, $\text{det}(A_2) = -3$), therefore standard LP methods don't apply. Branch and Bound algorithms look promising, and Chapter 8 of your notes looks nice. Thank you! $\endgroup$ Commented Dec 11, 2014 at 10:59

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.