Compact formulation

From Glossary

Jump to: navigation, search

In integer programming, this refers to having a polynomial number of constraints. For example, look at the travelling salesman formulations. The linear form has an exponential number of "subtour elimination consgtraints," so it is not compact. The

quadratic assignment formulation is compact.

Personal tools