(Mixed) Integer Linear Programming

On the Structure of Decision Diagram-Representable Mixed Integer Programs with Application to Unit Commitment

  • Hosseinali Salemi
  • Danial Davarnia
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Energy Tags , , ,

    Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed integer programs (MIPs) such as those appearing in energy applications has been lacking. More broadly, the question on which … Read more

    An Axiomatic Distance Methodology for Aggregating Multimodal Evaluations

  • Adolfo Escobedo
  • Erick Moreno-Centeno
  • Romena Yasmin
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Other Topics Tags , , ,

    This work introduces a multimodal data aggregation methodology featuring optimization models and algorithms for jointly aggregating heterogenous ordinal and cardinal evaluation inputs into a consensus evaluation. Mathematical modeling components are derived to enforce three types of logical couplings between the collective ordinal and cardinal evaluations: Rating and ranking preferences, numerical and ordinal estimates, and rating … Read more

    A Computational Status Update for Exact Rational Mixed Integer Programming

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

    The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, … Read more

    Set characterizations and convex extensions for geometric convex-hull proofs

  • Andreas Bärmann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Polyhedra Tags , , , ,

    In the present work, we consider Zuckerberg’s method for geometric convex-hull proofs introduced in [Geometric proofs for convex hull defining formulations, Operations Research Letters 44(5), 625–629 (2016)]. It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. … Read more

    Strong Optimal Classification Trees

  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Statistics Tags , , ,

    Decision trees are among the most popular machine learning models and are used routinely in applications ranging from revenue management and medicine to bioinformatics. In this paper, we consider the problem of learning optimal binary classification trees with univariate splits. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality … Read more

    Worst-case analysis of clique MIPs

  • Austin Buchanan
  • Jose L. Walteros
  • Mohammad Javad Naderi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Combinatorial Optimization

    The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) … Read more

    A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization

  • Thomas Kleinert
  • Martine Labbé
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , ,

    Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and … Read more

    Efficient presolving methods for the influence maximization problem in social networks

  • Sheng-Jie Chen
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Jian-Hua Yuan
  • Hou-Shan Zhang
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the … Read more

    An exact (re)optimization framework for real-time traffic management

  • Carlo Mannino
  • Giorgio Sartor
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    In real-time traffic management, a new schedule for the vehicles must be computed whenever a deviation from the current plan is detected, or periodically after some time. If this time interval is relatively small, then each two consecutive instances are likely to be similar. We exploit this aspect to derive an exact reoptimization framework for … Read more

    Learning To Scale Mixed-Integer Programs

  • Timo Berthold
  • Gregor Hendel
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software Design Principles Tags , , , , , ,

    Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed-integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes … Read more