How to transform this BIP into LP with the help of penalty function?

Question

I have an BIP problem as below

$$\underset{\bf b}{\max}{\bf u}^T\bf b$$ $$\text{subject to}$$ $${\bf Ab}\le1$$

Here, ${\bf b}=\{b_1,b_2,\cdots,b_N\}$ is a column vector of decision/optimization variables

${\bf u}=\{u_1,u_2,\cdots,u_N\}$ is a known column vector with $u_n\ge 0$

${\bf A}\in\{0,1\}^{M\times N}$ is a known binary matrix.

How can I transform this into LP? What would be an efficient relaxation of the binary variables.

Making the binary variables continuous and then rounding doesn't do a good job for my problem.

I want to have some formulation as below

$$\underset{\bf b}{\max}{\bf u}^T\bf b+\text{penalty function}$$ $$\text{subject to}$$ $${\bf Ab}\le1$$ $$0\le b_n\le1$$

What could be an efficient penalty function?

Answer 1

You can't. If there were a way to transform a MIP to an LP it would mean MIPs can be solved in polynomial time among many other things (edit: not exactly, see below). You can relax the binaries to continuous to get a lower bound, but that's about it. Just use a MIP solver.

From @1137h4xor's comment it seems like there is a method, which will add exponentially many variables to your problem (so complexity is still not polynomial as expected). In practice, the new problem will be at least as hard to solve as the original MIP.

Answer 2

If $A$ is totally unimodular, you can replace the binary restrictions on $b$ with $0 \le b_i \le 1$, and solve as an LP. See https://mathoverflow.net/questions/31367/proving-that-a-binary-matrix-is-totally-unimodular for sufficient conditions on the binary matrix $A$ to be totally unimodular.

Otherwise, see the comment by @1137h4xor

Answer 3

This might be a candidate for a binary decision diagram (BDD) approach. It involves building a layered digraph. Each layer involves deciding whether a particular variable $b_i$ will be 0 or 1. Each node represents the state of the system after a partial solution, which in this case could be the set of remaining variables that can still be set to 1.

This approach on the surface is similar (equivalent?) to using dynamic programming. If the digraph gets to big, it is possible to restrict the graph width (and hence the node count) in one of two ways. One way is a "relaxed" BDD, which does not remove any feasible solutions but does introduce infeasible solutions. The other is a "restricted" BDD, which does not introduce any infeasible solutions but does remove some feasible solutions. The solution to a relaxed BDD is like the best bound at a node in a branch-and-bound tree; the solution to a restricted BDD is an incumbent (not necessarily optimal) solution. There are researchers building branch-and-bound algorithms around BDDs.

You can find more information about BDDs, including a very informative book about decision diagrams, at https://www.andrew.cmu.edu/user/vanhoeve/mdd/.