# Backbone

### From Glossary

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

where is a vector of binary variables in the IP formulation and 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.