6533b86ffe1ef96bd12cd3e3

RESEARCH PRODUCT

The Linear Ordering Polytope

Rafael MartíGerhard Reinelt

subject

CombinatoricsConvex hullLinear programmingBirkhoff polytopeComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONConvex polytopeCross-polytopeMathematicsofComputing_NUMERICALANALYSISUniform k 21 polytopeEhrhart polynomialVertex enumeration problemMathematics

description

So far we developed a general integer programming approach for solving the LOP. It was based on the canonical IP formulation with equations and 3-dicycle inequalities which was then strengthened by generating mod-k-inequalities as cutting planes. In this chapter we will add further ingredients by looking for problem- specific inequalities. To this end we will study the convex hull of feasible solutions of the LOP: the so-called linear ordering polytope.

yearjournalcountryeditionlanguage
2010-09-12
https://doi.org/10.1007/978-3-662-64877-3_6