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: . Hence, its optimal points may not be feasible (not Boolean). Even though a solution of the LP relaxation may not necessarily be Boolean, we can often interpret it as a {em fractional} solution to the original problem. For example, in a graph coloring problem, the LP relaxation colors the nodes of the graph not with a single color, but with many. 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 people to tasks, in a one-to-one fashion. The cost of matching person to task is . The problem reads Shortest pathThe shortest path problem has the form where stands for the incidence matrix of the network, and arcs with form a shortest forward path between nodes and . As before the LP relaxation in this case is exact, in the sense that its solution is Boolean. The shortest path problem can be solved very efficiently with specialized algorithms based on the LP relaxation to the above formulation. |