Integer Programming

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

    Mixed-Integer Quadratic Optimization and Iterative Clustering Techniques for Semi-Supervised Support Vector Machines

  • Martin Schmidt
  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms, Data Science Applications Tags , , ,

    Among the most famous algorithms for solving classification problems are support vector machines (SVMs), which find a separating hyperplane for a set of labeled data points. In some applications, however, labels are only available for a subset of points. Furthermore, this subset can be non-representative, e.g., due to self-selection in a survey. Semi-supervised SVMs tackle … Read more

    Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework

  • Leon Eifler
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably … Read more