Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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.
