skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Convexification of Bilinear Terms over Network Polytopes
It is well-known that the McCormick relaxation for the bilinear constraint z = xy gives the convex hull over the box domains for x and y. In network applications where the domain of bilinear variables is described by a network polytope, the McCormick relaxation, also referred to as linearization, fails to provide the convex hull and often leads to poor dual bounds. We study the convex hull of the set containing bilinear constraints [Formula: see text] where xirepresents the arc-flow variable in a network polytope, and yjis in a simplex. For the case where the simplex contains a single y variable, we introduce a systematic procedure to obtain the convex hull of the above set in the original space of variables, and show that all facet-defining inequalities of the convex hull can be obtained explicitly through identifying a special tree structure in the underlying network. For the generalization where the simplex contains multiple y variables, we design a constructive procedure to obtain an important class of facet-defining inequalities for the convex hull of the underlying bilinear set that is characterized by a special forest structure in the underlying network. Computational experiments conducted on different applications show the effectiveness of the proposed methods in improving the dual bounds obtained from alternative techniques. Funding: This work was supported by Air Force Office of Scientific Research [Grant FA9550-23-1-0183]; National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation [Grant 2338641]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2023.0001 .  more » « less
Award ID(s):
2338641
PAR ID:
10546393
Author(s) / Creator(s):
;
Publisher / Repository:
INFORMS
Date Published:
Journal Name:
Mathematics of Operations Research
ISSN:
0364-765X
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Mathematics of Operations Research)
    The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acyclic hypergraphs, a class that lies between gamma-acyclic and beta-acyclic hypergraphs, the running intersection relaxation coincides with the multilinear polytope and it admits a polynomial size extended formulation. 
    more » « less
  2. ; ; (, Mathematical Programming Computation)
    We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set. 
    more » « less
  3. ; (, Mathematics of Operations Research)
    In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P, where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes [Formula: see text] time, where d is the number of inner functions and n is the number of estimators for each inner function. Consequently, we derive large classes of inequalities that tighten prevalent factorable programming relaxations. We also generalize a decomposition result and devise techniques to simultaneously separate hypographs of various supermodular, concave-extendable functions using facet-defining inequalities. Assuming that the outer function is convex in each argument, we characterize the limiting relaxation obtained with infinitely many estimators as the solution of an optimal transport problem. When the outer function is also supermodular, we obtain an explicit integral formula for this relaxation. 
    more » « less
  4. ; (, Journal of Combinatorial Optimization)
    Ordering polytopes have been instrumental to the study of combinatorial optimization problems arising in a variety of fields including comparative probability, computational social choice, and group decision-making. The weak order polytope is defined as the convex hull of the characteristic vectors of all binary orders on n alternatives that are reflexive, transitive, and total. By and large, facet defining inequalities (FDIs) of this polytope have been obtained through simple enumeration and through connections with other combinatorial polytopes. This paper derives five new large classes of FDIs by utilizing the equivalent representations of a weak order as a ranking of n alternatives that allows ties; this connection simplifies the construction of valid inequalities, and it enables groupings of characteristic vectors into useful structures. We demonstrate that a number of FDIs previously obtained through enumeration are actually special cases of the large classes. This work also introduces novel construction procedures for generating affinely independent members of the identified ranking structures. Additionally, it states two conjectures on how to derive many more large classes of FDIs using the featured techniques. 
    more » « less
  5. ; (, Mathematics of Operations Research)
    Facet-defining inequalities of the symmetric traveling salesman problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the circlet inequalities. These inequalities were first conjectured in Gutekunst and Williamson [Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478] when studying the circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture from Marco Buratti in 2007. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans [Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349]; they achieve the same worst case strength as the similarly circulant crown inequalities of Naddef and Rinaldi [Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326] but are generally stronger. Funding: This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program [Grant DGE-1650441] and by the National Science Foundation Division of Computing and Communications Foundations [Grant CCF-1908517]. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email