Month: March 2023

Occupation measure relaxations in variational problems: the role of convexity

  • Didier Henrion
  • Milan Korda
  • Martin Kružík
  • Rodolfo Rios-Zertuche
    • Categories Linear, Cone and Semidefinite Programming Tags

    This work addresses the occupation measure relaxation of calculus of variations problems, which is an infinite-dimensional linear programming reformulation amenable to numerical approximation by a hierarchy of semidefinite optimization problems. We address the problem of equivalence of this relaxation to the original problem. Our main result provides sufficient conditions for this equivalence. These conditions, revolving … Read more

    An infeasible interior-point arc-search method with Nesterov’s restarting strategy for linear programming problems

  • Einosuke Iida
  • Makoto Yamashita
    • Categories Linear Programming Tags , , ,

    An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s … Read more

    Submodular maximization and its generalization through an intersection cut lens

  • Liding Xu
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , ,

    \(\) We study a mixed-integer set \(\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}\) arising in the submodular maximization problem, where \(f\) is a submodular function defined over \(\{0,1\}^n\). We use intersection cuts to tighten a polyhedral outer approximation of \(\mathcal{S}\). We construct a continuous extension \(\mathsf{F}\) of \(f\), which is convex and defined over … Read more

    On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints

  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories Bound-constrained Optimization, Global Optimization, Quadratic Programming Tags , , ,

    Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more

    A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints

  • Samuel Burer
    • Categories Cone Programming, Global Optimization Theory, Quadratic Programming

    \(\) Globally optimizing a nonconvex quadratic over the intersection of $m$ balls in $\mathbb{R}^n$ is known to be polynomial-time solvable for fixed $m$. Moreover, when $m=1$, the standard semidefinite relaxation is exact. When $m=2$, it has been shown recently that an exact relaxation can be constructed using a disjunctive semidefinite formulation based essentially on two … Read more

    On the Relationship Between the Value Function and the Efficient Frontier of a Mixed Integer Linear Optimization Problem

  • Ted K. Ralphs
    • Categories Multi-Criteria Optimization, Other Topics

    In this paper, we investigate the connection between the efficient frontier (EF) of a general multiobjective mixed integer linear optimization problem (MILP) and the so-called restricted value function (RVF) of a closely related single-objective MILP. We demonstrate that the EF of the multiobjective MILP is comprised of points on the boundary of the epigraph of … Read more

    Semidefinite approximations for bicliques and biindependent pairs

  • Monique Laurent
  • Sven Polak
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , , , , ,

    \(\) We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be … Read more

    Optimality-Based Discretization Methods for the Global Optimization of Nonconvex Semi-Infinite Programs

  • Evren Turan
  • Johannes Jäschke
  • Rohit Kannan
    • Categories Global Optimization, Semi-infinite Programming Tags , , , , ,

    We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min … Read more

    Customer Satisfaction and Pricing in E-Retail Delivery

  • Dipayan Banerjee
  • Alan L. Erera
  • Alejandro Toriello
    • Categories Applications - OR and Management Sciences, Production and Logistics, Supply Chain Management Tags , ,

    We study a system in which a common delivery fleet provides service to both same-day delivery (SDD) and next-day delivery (NDD) orders placed by e-retail customers who are sensitive to delivery prices. We develop a model of the system and optimize with respect to two separate objectives. First, empirical research suggests that fulfilling e-retail orders … Read more