Facets of the Total Matching Polytope for bipartite graphs

The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for … Read more

Multilinear Sets with Two Monomials and Cardinality Constraints

Binary polynomial optimization is equivalent to the problem of minimizing a linear function over the intersection of the multilinear set with a polyhedron. Many families of valid inequalities for the multilinear set are available in the literature, though giving a polyhedral characterization of the convex hull is not tractable in general as binary polynomial optimization … Read more

Relating Single-Scenario Facets to the Convex Hull of the Extensive Form of a Stochastic Single-Node Flow Polytope

Stochastic mixed-integer programs (SMIPs) are a widely-used modeling paradigm for sequential decision making under uncertainty. One popular solution approach to solving SMIPs is to solve the so-called “extensive form” directly as a large-scale (deterministic) mixed-integer program. In this work, we consider the question of when a facet-defining inequality for the convex hull of a deterministic, … Read more

On Lifted Cover Inequalities: A New Lifting Procedure with Unusual Properties

Lifted cover inequalities are well-known cutting planes for 0-1 linear programs. We show how one of the earliest lifting procedures, due to Balas, can be significantly improved. The resulting procedure has some unusual properties. For example, (i) it can yield facet-defining inequalities even if the given cover is not minimal, (ii) it can yield facet-defining … Read more

Matroid Optimization Problems with Monotone Monomials in the Objective

In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. … Read more

Matroid Optimisation Problems with Nested Non-linear Monomials in the Objective Function

Recently, Buchheim and Klein suggested to study polynomial-time solvable optimisation problems with linear objective functions combined with exactly one additional quadratic monomial. They concentrated on special quadratic spanning tree or forest problems. We extend their results to general matroid optimisation problems with a set of nested monomials in the objective function. The monomials are linearised … Read more

Stronger Multi-Commodity Flow Formulations of the (Capacitated) Sequential Ordering Problem

The “sequential ordering problem” (SOP) is the generalisation of the asymmetric travelling salesman problem in which there are precedence relations between pairs of nodes. Hernández & Salazar introduced a “multi-commodity flow” (MCF) formulation for a generalisation of the SOP in which the vehicle has a limited capacity. We strengthen this MCF formulation by fixing variables … Read more

The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity

In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard … Read more

An extended approach for lifting clique tree inequalities

We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling salesman problem (SQTSP). Applying this new approach to the subtour elimination constraints (SEC) leads to two new classes … Read more

The Asymmetric Quadratic Traveling Salesman Problem

The quadratic traveling salesman problem asks for a tour of minimal costs where the costs are associated with each two arcs that are traversed in succession. This structure arises, e. g., if the succession of two arcs represents the costs of loading processes in transport networks or a switch between different technologies in communication networks. … Read more