mixed-integer programming

A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems

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

    In multi-objective mixed-integer convex optimization multiple convex objective functions need to be optimized simultaneously while some of the variables are only allowed to take integer values. In this paper we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization … Read more

    On implementation details and numerical experiments for the HyPaD algorithm to solve multi-objective mixed-integer convex optimization problems

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

    In this paper we present insights on the implementation details of the hybrid patch decomposition algorithm (HyPaD) for convex multi-objective mixed-integer optimization problems. We discuss how to implement the SNIA procedure which is basically a black box algorithm in the original work by Eichfelder and Warnow. In addition, we present and discuss results for various … Read more

    On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Thomas Kleinert
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory, Quadratic Programming Tags , , , ,

    Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more

    A novel decomposition approach for holistic airline optimization

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories Airline Optimization, Applications - OR and Management Sciences Tags , , , ,

    Airlines face many different planning processes until the day of operation. These include Fleet Assignment, Tail Assignment and the associated control of ground processes between consecutive flights, called Turnaround Handling. All of these planning problems have in common that they often need to be reoptimized on the day of execution due to unplanned events. In … Read more

    Battery Storage Formulation and Impact on Day Ahead Security Constrained Unit Commitment

  • Ross Baldick
  • Yonghong Chen
    • Categories Applications - OR and Management Sciences Tags , ,

    This paper discusses battery storage formulations and analyzes the impact of the constraints on the computational performance of security constrained unit commitment (SCUC). Binary variables are in general required due to mutual exclusiveness of charging and discharging modes. We use valid inequalities to improve the SOC constraints. Adding batteries to the MISO day ahead market … Read more

    A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

  • Marianna De Santis
  • Sven de Vries
  • Martin Schmidt
  • Lukas Winkel
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Complementarity and Variational Inequalities Tags , , , ,

    Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more

    Distributionally Robust Fair Transit Resource Allocation During a Pandemic

  • Luying Sun
  • Weijun Xie
  • Tim Witten
    • Categories Applications - OR and Management Sciences Tags , , ,

    This paper studies Distributionally robust Fair transit Resource Allocation model (DrFRAM) under Wasserstein ambiguity set to optimize the public transit resource allocation during a pandemic. We show that the proposed DrFRAM is highly nonconvex and nonlinear and is, in general, NP-hard. Fortunately, we show that DrFRAM can be reformulated as a mixed-integer linear programming (MILP) … Read more

    Cardinality Minimization, Constraints, and Regularization: A Survey

  • Daniel Bienstock
  • Andrea Lodi
  • Andreas M. Tillmann
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , , , , , ,

    We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

    Second-Order Conic and Polyhedral Approximations of the Exponential Cone: Application to Mixed-Integer Exponential Conic Programs

  • Ye Qing
  • Weijun Xie
    • Categories Integer Programming Tags , , , ,

    Exponents and logarithms exist in many important applications such as logistic regression, maximum likelihood, relative entropy and so on. Since the exponential cone can be viewed as the epigraph of perspective of the natural exponential function or the hypograph of perspective of the natural logarithm function, many mixed-integer nonlinear convex programs involving exponential or logarithm … Read more

    An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories (Mixed) Integer Linear Programming Tags ,

    Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a … Read more