Integer Programming

AI for Enhancing Operations Research of Agriculture and Energy

  • Morteza Kimiaei
  • Anshu Kumar
  • Vyacheslav Kungurtsev
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Global Optimization Tags , , , , , , ,

    This paper surveys optimization problems arising in agriculture, energy systems, and water-energy coordination from an operations research perspective. These problems are commonly formulated as integer nonlinear programs, mixed-integer nonlinear programs, or combinatorial set optimization models, characterized by nonlinear physical constraints, discrete decisions, and intertemporal coupling. Such structures pose significant computational challenges in large-scale and repeated-solution … 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

    Weight reduction inequalities revisited

  • Shreyas Bhowmik
  • Sachin Jayaswal
    • Categories 0-1 Programming Tags , , , ,

    In this paper, we propose an extension of the classical weight reduction inequalities for the binary knapsack polytope for settings where the maximum-weight item in the associated pack is not unique. We derive sufficient conditions under which the extended inequalities are facet-defining and identify conditions under which they strictly dominate the original weight reduction inequalities. … Read more

    Modeling Bloons Tower Defense as a temporal two-dimensional knapsack problem with irregular shapes and side constraints: integer programming-based approaches

  • Maxence Delorme
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    In Tower Defense (TD) games, the objective is to defend a specific point on the game map from mobile units by constructing towers with offensive capabilities. In this work, we focus on Bloons Tower Defense (Bloons TD), one of the earliest and most prominent TD games. We show that the problem of finding tower configurations … 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

    Combinatorial Benders Decomposition and Column Generation for Optimal Box Selection

  • Christoph Buchheim
  • Alice Kirchheim
  • Pia Schreynemackers
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Transportation Tags , ,

    We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items. In the first stage, we select the optimal dimensions of the boxes, while in the second … Read more

    A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal

  • Jie Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , , , , , ,

    This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain … Read more

    A Framework for Handling and Exploiting Symmetry in Benders’ Decomposition

  • Christopher Hojny
  • Cedric Roy
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Scheduling Tags ,

    Benders’ decomposition (BD) is a framework for solving optimization problems by removing some variables and modeling their contribution to the original problem via so-called Benders cuts. While many advanced optimization techniques can be applied in a BD framework, one central technique has not been applied systematically in BD: symmetry handling. The main reason for this … Read more