Integer Programming

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

    A Stochastic Benders Decomposition Scheme for Large-Scale Stochastic Network Design

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
  • Periklis Petridis
    • Categories Cutting Plane Approaches, Network Optimization, Stochastic Programming Tags , ,

    Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a stochastic version where operational costs are uncertain due to fluctuating demand and estimated as a sample average from historical data. This problem is computationally challenging, and instances with as few as  100 … Read more

    An approximation algorithm for multi-objective mixed-integer convex optimization

  • Ina Lammel
  • Karl-Heinz Küfer
  • Philipp Süss
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , ,

    In this article we introduce an algorithm that approximates Pareto fronts of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front exploiting the convexity of the patches and is applicable to problems with an arbitrary number of criteria. In the algorithm, the problem is decomposed into patches, which … Read more