2
$\begingroup$

I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis.

Most of the algorithms that I have found were branch and bound-based, but I am trying to find an analytical solution using KKT conditions.

$\endgroup$
1
  • 1
    $\begingroup$ For almost all LPs (and MIPs) there are no analytical solutions. $\endgroup$ Jun 28 at 11:33
2
$\begingroup$

Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP).

Generally, there is no easy algorithm that is guaranteed to find the optimal solution of MIP problems quickly. My reason to believe that is: I can implement a boolean satisfiability (b-sat) problem as a mixed integer programming problem. That means mixed integer programming problems is a super-set of b-sat problems. Since b-sat is NP-complete, mip is NP-hard.

I think KKT condition is more like a check to see if a solution is a local optimum. I don't expect NP-hard problems to have simple analytical solution in general.

Of course, some problems with Boolean constraints can have analytical solution. But there is no general easy way to solve all MIP problems.

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