1

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?

KGM
  • 2,265
  • 7
  • 23

3 Answers3

6

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.

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • I am not talking about transforming MIP into an LP without any loss. Once we relax the binary to continuous, what kind of penalty we can add to objective? – KGM Aug 03 '22 at 12:42
  • 1
    You can't, that doesn't really make sense. To save you some trouble, if your goal is to transform the MIP to an LP so that you can solve it more easily, it's not going to work - any MIP solver will do a much better job than any such formulation. If MIP solvers can't solve it, you just need to get good at MIP formulations. – Nikos Kazazakis Aug 04 '22 at 10:57
4

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

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
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/.

prubin
  • 39,078
  • 3
  • 37
  • 104