1
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ or.stackexchange.com/questions/3203/… $\endgroup$
    – 1137h4xor
    Aug 3 at 10:50
  • 2
    $\begingroup$ Your BIP is called the generalized set packing problem. $\endgroup$
    – RobPratt
    Aug 3 at 12:56
  • $\begingroup$ @RobPratt in my problem $\bf u$ is utility vector. It can be all 1 vector or different. $\endgroup$ Aug 3 at 14:27
  • $\begingroup$ Yes, that is the generalized part. $\endgroup$
    – RobPratt
    Aug 3 at 14:57
  • 1
    $\begingroup$ And you want this "efficient" penalty function to be linear? Because if it's not, it won't be an LP. $\endgroup$ Aug 5 at 0:33

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Aug 3 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 4 at 10:57
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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/.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.