Integer Programming

Democratization of Complex-Problem Solving: Toward Privacy-Aware, Transparent and Inclusive Optimization

  • Mikhail Bragin
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , , , , , ,

    Critical operations often involve stakeholders with diverse perspectives, yet centralized optimization assumes participation or private information, neither of which is a priori guaranteed. Additionally, decision-making involves discrete decisions, making optimization computationally challenging. Centralized formulations use approximations to manage complexity, often overlooking stakeholder perspectives, leading to bias. To resolve these challenges, we adopt a privacy-aware participatory-distributed … Read more

    Political districting to optimize the Polsby-Popper compactness score with application to voting rights

  • Pietro Belotti
  • Austin Buchanan
  • Soraya Ezazipour
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Integer Programming Tags , ,

    In the academic literature and in expert testimony, the Polsby-Popper score is the most popular way to measure the compactness of a political district. Given a district with area \(A\) and perimeter \(P\), its Polsby-Popper score is given by \( (4 \pi A)/P^2\). This score takes values between zero and one, with circular districts achieving … Read more

    On the Partial Convexification of the Low-Rank Spectral Optimization: Rank Bounds and Algorithms

  • Yongchun Li
  • Weijun Xie
    • Categories Integer Programming Tags , , , ,

    A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed “LSOP-R”, is often tractable and yields a high-quality solution. … Read more

    When Deep Learning Meets Polyhedral Theory: A Survey

  • Joey Huchette
  • Gonzalo Muñoz
  • Thiago Serra
  • Calvin Tsay
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science, Polyhedra

    In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified … Read more

    Heuristic methods for noisy derivative-free bound-constrained mixed-integer optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories (Mixed) Integer Nonlinear Programming, Bound-constrained Optimization, Global Optimization Tags

    This paper introduces MATRS, a novel matrix adaptation trust-region strategy designed to solve noisy derivative-free mixed-integer optimization problems with simple bounds in low dimensions. MATRS operates through a repeated cycle of five phases: mutation, selection, recombination, trust-region, and mixed-integer, executed in this sequence. But if in the mutation phase a new best point (the point … Read more

    Optimal Planning for the Electrification of Bus Fleets in Public Transit Systems

  • Filipe Cabral
  • Xu Andy Sun
    • Categories Applications - OR and Management Sciences, Integer Programming, Transportation Tags , , ,

    Electric vehicles (EV) pave a promising way towards low-carbon transportation, but the transition to all EV fleets creates new challenges for the public transportation sector. Despite increasing adoption of electric buses, the main challenges presented by the battery electric bus technology include the lack of charging facilities, the reduced operating capacity per battery charge compared … Read more

    Markov Decision Process Design: A Framework for Integrating Strategic and Operational Decisions

  • Seth Brown
  • Saumya Sinha
  • Andrew J. Schaefer
    • Categories Integer Programming, Nonlinear Optimization Tags , ,

    We consider the problem of optimally designing a system for repeated use under uncertainty. We develop a modeling framework that integrates design and operational phases, which are represented by a mixed-integer program and discounted-cost infinite-horizon Markov decision processes, respectively. We seek to simultaneously minimize the design costs and the subsequent expected operational costs. This problem … Read more

    Mixed-Integer Programming Approaches to Generalized Submodular Optimization and its Applications

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogenous items from more than one ground set or selecting multiple copies … Read more

    Multi-Stage Robust Mixed-Integer Programming

  • Krzysztof Postek
  • Ward Romeijnders
  • Wolfram Wiesemann
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming, Robust Optimization Tags , ,

    Multi-stage robust optimization, in which decisions are taken sequentially as new information becomes available about the uncertain problem parameters, is a very versatile yet computationally challenging paradigm for decision-making under uncertainty. In this paper, we propose a new model and solution approach for multi-stage robust mixed-integer programs, which may contain both continuous and discrete decisions … Read more

    Test Instances for Multiobjective Mixed-Integer Nonlinear Optimization

  • Leo Warnow
  • Gabriele Eichfelder
  • Tobias Gerlach
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization, Nonlinear Optimization Tags , , ,

    A suitable set of test instances, also known as benchmark problems, is a key ingredient to systematically evaluate numerical solution algorithms for a given class of optimization problems. While in recent years several solution algorithms for the class of multiobjective mixed-integer nonlinear optimization problems have been proposed, there is a lack of a well-established set … Read more