(Mixed) Integer Nonlinear Programming

Separating Hyperplanes for Mixed-Integer Polynomial Optimization Problems

  • Carl Eggen
  • Jan Kronqvist
  • Andreas Lundell
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , ,

    Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more

    Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , , ,

    We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more

    Fast Presolving Framework For Sparsity Constrained Convex Quadratic Programming: Screening-Based Cut Generation and Selection

  • haoztan
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Nonlinear Optimization Tags , , , ,

    Screening is widely utilized for Mixed-Integer Programming (MIP) presolving. It aims to certify a priori whether one or multiple specific binary variables can be fixed to optimal values based on solutions from convex relaxations. This paper studies the challenge of solving Sparsity-constrained (strongly) Convex Quadratic Programming (SCQP) and proposes the Screening-based Cut Presolving Framework (SCPF). … Read more

    Exact and approximate formulations for the close-enough TSP

  • Domingo Araya
  • Gustavo Angulo
  • Margarita P Castro
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , ,

    This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear … Read more

    The Fulfillment Regionalization Problem

  • Nidhima Grover
  • Xiaoyan Si
  • Alejandro Toriello
    • Categories (Mixed) Integer Nonlinear Programming, Supply Chain Management, Transportation Tags , , , ,

    In many retail industries, the retailer can choose the inventory location or fulfillment center (FC) that fulfills an order, yielding opportunities for inventory pooling and product selection expansion. However, fulfillment decisions are complex and must consider cost and speed, among various factors. With the unprecedented growth of the retail industry, companies must look for strategies … Read more

    Solving the Heilbronn Triangle Problem using Global Optimization Methods

  • Burak Kocuk
  • Amirali Modir
  • Amirhossein Monji
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications Tags , , , ,

    We study the Heilbronn triangle problem, which involves placing \(n\) points in the unit square such that the minimum area of any triangle formed by these points is maximized. A straightforward maximin formulation of this problem is highly non-linear and non-convex due to the existence of bilinear terms and absolute value equations. We propose two … Read more

    Branch and price for nonlinear production-maintenance scheduling in complex machinery

  • João Dionísio
  • Ambros Gleixner
  • João Pedro Pedroso
  • Ksenia Bestuzheva
    • Categories (Mixed) Integer Nonlinear Programming, Production and Logistics, Scheduling Tags , , , ,

    This paper proposes a mixed-integer nonlinear programming approach for joint scheduling of long-term maintenance decisions and short-term production for groups of complex machines with multiple interacting components. We introduce an abstract model where the production and the condition of machines are described by convex functions, allowing the model to be employed for various application areas … Read more

    Towards a geometric characterization of unbounded integer cubic optimization problems via thin rays

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming

    We study geometric characterizations of unbounded integer polynomial optimization problems. While unboundedness along a ray fully characterizes unbounded integer linear and quadratic optimization problems, we show that this is not the case for cubic polynomials. To overcome this, we introduce thin rays, which are rays with an arbitrarily small neighborhood, and prove that they characterize … Read more

    Projection-width as a structural parameter for discrete separable optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

    While several classes of integer linear optimization problems are known to be solvable in polynomial time, far fewer tractability results exist for integer nonlinear optimization. In this work, we narrow this gap by identifying a broad class of discrete nonlinear optimization problems that admit polynomial-time algorithms. Central to our approach is the notion of projection-width, … Read more