integral polyhedra – Optimization Online

Fixed charges of arbitrary sign: what survives and what fails

Published: 2026/09/01

Duy T. Nguyen

(Mixed) Integer Linear Programming, Polyhedra, Production and Logistics fixed-charge problems, integral polyhedra, lot sizing, negative prices, total unimodularity

For integer activities, conditioning on the support makes a fixed-charge objective affine. If every support-conditioned cell is integral, an optimal solution is a vertex of its cell for arbitrary fixed charges and marginal rates. A totally unimodular constraint matrix with integral data guarantees this condition. This surviving property is weaker than the classical conclusions. A … Read more

Implied Integrality in Mixed-Integer Optimization

Published: 2025/07/12

(Mixed) Integer Linear Programming, Integer Programming, Polyhedra implied integers, integral polyhedra, mixed-integer linear programming, presolving, total unimodularity

Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this work we formalize the definition of implied integrality by taking a … Read more