LP Relaxations of Boolean Problems
Boolean problemsA Boolean optimization problem is one where the variables are constrained to be Boolean. An example of Boolean problem is the so-called Boolean LP ![]() Such problems are usually very hard to solve exactly: this would require a complete enumeration of all the exponential number of possible points in LP relaxationThe LP relaxation takes the form ![]() The relaxation provides a lower bound on the original problem: Exact solutionsBoolean problems are not always hard to solve. Indeed, in some cases, one can show that the LP relaxation provides an exact solution to the Boolean problem, as optimal points turn out to be Boolean. A few examples in this category: Weighted bipartite matchingThe weighted bipartite matching problem is to match ![]() Shortest pathThe shortest path problem has the form ![]() where |