Polyhedral combinatorics

Polyhedral combinatorics refers to the study of the geometric and combinatorial properties of polyhedra, particularly those arising from integer hulls of specific families of problems such as linear programming, integer programming, and Diophantine equations. This field of research has been extensively studied for the past 60 years and is closely related to the study of lattice polytopes.From: Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case [2018], Computational Modelling of Objects Represented in Images [2018]

Contextual classification of remotely sensed images with integer linear programming

View Chapter

Purchase Book

Published in João Manuel, R. S. Tavares, R. M. Natal Jorge, Computational Modelling of Objects Represented in Images, 2018

Manuel Lameiras Campagnolo, Jorge Orestes Cerdeira

To speed up this procedure classes of strong valid inequalities (i.e., cuts) for this classification problem have to be devised. This is the subject of polyhedral combinatorics theory: see for example (Pulleyblank 1983) or (Schrijver 1995). Nevertheless, any such integer cutting algorithm will certainly suffer from serious limitations regarding the size of the data sets. Hence, the development of accurate heuristics is a reasonable option for the problem in hand.

Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case

View Article

Journal Information

Published in Optimization Methods and Software, 2018

Chun Yu Hong, Matthias Köppe, Yuan Zhou

The question becomes much harder when all or some of the variables are constrained to be integers. The theory of valid linear inequalities here is called cutting plane theory. Over the past 60 years, a vast body of research has been carried out on this topic, the largest part of it regarding the polyhedral combinatorics of integer hulls of particular families of problems. The general theory again is equivalent to the duality theory of integer linear optimization problems. Here the dual objects are not linear, but superadditive (or subadditive) functionals, making the general form of this theory infinite-dimensional even though the original problem started out with only finitely many variables.

Polyhedral combinatorics

Explore chapters and articles related to this topic

Contextual classification of remotely sensed images with integer linear programming

Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case