We study the polyhedral convex hull of a mixed-integer set 𝒮 defined by collection multilinear equations over unit hypercube. Such sets appear frequently in factorable reformulation nonlinear optimization problems. In particular, represents feasible region linearized unconstrained binary polynomial problem. define an equivalent hypergraph representation 𝒮, which enables us to derive several families facet-defining inequalities, structural properties, and lifting operations for its space...

Abstract We consider a waste collection problem encountered in Due Carrare, town located Northern Italy. The original feature of the consists need for arranging appointments between vehicles along their routes so that small can dump contents large ones and continue work. This identifies as generalization well‐known Capacitated Arc Routing Problem (CARP). propose local search heuristic obtained from variable neighborhood procedure suggested by Hertz Mittaz (2001) CARP. In Carrare instance,...

We consider the multilinear polytope defined as convex hull of set binary points $z$ satisfying a collection equations form $z_e = \prod_{v \in e} {z_v}$, $e E$, where $E$ denotes family subsets $\{1, \ldots , n\}$ cardinality at least two. Such sets are fundamental importance in many types mixed-integer nonlinear optimization problems, such $0-1$ polynomial optimization. Utilizing an equivalent hypergraph representation, we study facial structure conjunction with acyclicity degree...

This article provides an overview of our joint work on binary polynomial optimization over the past decade. We define multilinear polytope as convex hull feasible region a linearized problem. By representing with hypergraphs, we investigate connections between hypergraph acyclicity and complexity facial structure polytope. characterize acyclic hypergraphs for which polynomial-size extended formulation can be constructed in time.

The multilinear polytope of a hypergraph is the convex hull set binary points satisfying collection equations. We introduce running intersection inequalities, new class facet-defining inequalities for polytope. Accordingly, we define polyhedral relaxation polytope, referred to as relaxation, and identify conditions under which this tight. Namely, show that kite-free beta-acyclic hypergraphs, lies between gamma-acyclic coincides with it admits polynomial size extended formulation.

Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting combinatorial structure these inequalities with their Chvátal rank. We determine rank all known and show that almost them 1. observe an associated hypergraph is β-acyclic. Our second goal to derive deeper planes; do so, consider hypergraphs admit β-cycles. introduce a novel class valid arising from odd β-cycles, generally 2. These allow...

Let ℒ be a family of lattice-free polyhedra in ℝ m containing the splits. Given polyhedron P + n , we characterize when valid inequality for ∩ (ℤ × ) can obtained with finite number disjunctive cuts corresponding to ℒ. We also M such that all every P. Our results imply interesting consequences, related split rank and integral polyhedra, extend recent research findings.

We show that the problem of minimizing a quadratic polynomial with integer coefficients over points in general two-dimensional rational polyhedron is solvable time bounded by input size.

We introduce the reverse Chvátal--Gomory rank $r^*(P)$ of an integral polyhedron $P$, defined as supremum ranks all rational polyhedra whose integer hull is $P$. A well-known example in dimension two shows that there exist polytopes $P$ with $r^*(P)=+\infty$. provide a geometric characterization this property every dimension, and investigate upper bounds on when value finite.

We investigate new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network games belong to this class.In symmetric case, when all players have same strategy set, we design an algorithm that finds optimal aggregated and then decomposes it into single strategies. This approach yields strongly polynomial-time algorithms (i) find a pure Nash...

We investigate a new class of congestion games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra defined by totally unimodular constraint matrices. Network games belong to this class.In symmetric case, when all players have same strategy set, we design an algorithm that finds optimal aggregated and then decomposes it into single strategies. This approach yields strongly polynomial-time algorithms (i) find pure Nash...

We complete the complexity classification by degree of minimizing a polynomial over integer points in polyhedron real vector space dimension two. Previous work shows that optimizing quadratic polyhedral region two can be done time, whereas quartic same type is NP-hard. close gap showing this problem solved time for cubic polynomials. Furthermore, we show homogeneous any fixed bounded solvable time. holds polynomials translated into polynomials, even when translation unknown. demonstrate such...