Backbone

From Glossary

Jump to: navigation, search

Originally, this was a set of propositions that must be true in every solution of a satisfiability problem. If there is no solution, one seeks a set of truth values that maximizes the number of clauses that are true. Then, the backbone is the set of propositions that must be true in every optimal solution. This has been extended to various combinatorial programs, for which the backbone is

LaTeX: 
\{j : x_j = 1 \mbox{ for all } x \in X^* \},

where LaTeX: x is a vector of binary variables in the IP formulation and LaTeX: X^* is usually the optimality region, although it could allow some ball around the objective value. Some results suggest that the difficulty of an NP-hard problem can be further analyzed by the size of itsbackbone.


Views
Personal tools