(Mixed) Integer Linear Programming

Multi-period investment pathways – Modeling approaches to design distributed energy systems under uncertainty

  • Markus Bohlayer
  • Marco Braun
  • Adrian Bürger
  • Markus Fleschutz
  • Gregor Zöttl
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming

    Multi-modal distributed energy system planning is applied in the context of smart grids, industrial energy supply, and in the building energy sector. In real-world applications, these systems are commonly characterized by existing system structures of different age where monitoring and investment are conducted in a closed-loop, with the iterative possibility to invest. The literature contains … Read more

    Formulations and Valid Inequalities for Optimal Black Start Allocation in Power Systems

  • Ignacio Aravena
  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
    • Categories (Mixed) Integer Linear Programming, Energy Tags , , ,

    The restoration of a power system after an extended blackout starts around units with enhanced technical capabilities, referred to as black start units (BSUs). We examine the planning problem of optimally allocating these units on the grid subject to a budget constraint. We present a mixed integer programming model based on current literature in power … Read more

    An Integer Programming Approach to Deep Neural Networks with Binary Activation Functions

  • Bubacarr Bah
  • Jannis Kurtz
    • Categories (Mixed) Integer Linear Programming, Other Topics, Robust Optimization Tags , , ,

    We study deep neural networks with binary activation functions (BDNN), i.e. the activation function only has two states. We show that the BDNN can be reformulated as a mixed-integer linear program which can be solved to global optimality by classical integer programming solvers. Additionally, a heuristic solution algorithm is presented and we study the model … Read more

    Mixed Integer Bilevel Optimization with k-optimal Follower: A Hierarchy of Bounds

  • Xueyu Shi
  • Oleg A. Prokopyev
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags ,

    We consider mixed integer bilevel linear optimization problems in which the decision variables of the lower-level (follower’s) problem are all binary. We propose a general modeling and solution framework motivated by the practical reality that in a Stackelberg game, the follower does not always solve their optimization problem to optimality. They may instead implement a … Read more

    Combination Chemotherapy Optimization

  • Temitayo Ajayi
  • Seyedmohammadhossein Hosseinian
  • Andrew J. Schaefer
  • Clifton D. Fuller
    • Categories (Mixed) Integer Linear Programming, Biomedical Applications Tags , ,

    Chemotherapy is one of the primary modalities of cancer treatment. Chemotherapy drug administration is a complex problem that often requires expensive clinical trials to evaluate potential regimens. One way to alleviate this burden and better inform future trials is to build reliable models for drug administration. Previous chemotherapy optimization models have mainly relied on optimal … Read more

    Computing Optimized Path Integrals for Knapsack Feasibility

  • Endric Daues
  • Ulf Friedrich
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    A generating function technique for solving integer programs via the evaluation of complex path integrals is discussed from a theoretical and computational perspective. Applying the method to solve knapsack feasibility problems, it is demonstrated how the presented numerical integration algorithm benefits from pre-optimizing the path of integration. After discussing the algorithmic set-up in detail, a … Read more

    Solving IP via Complex Integration on Shortest Paths

  • Ulf Friedrich
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Using the weighted geometric series expansion, it is shown how integer programming can be solved by evaluating complex path integrals based on a multi-path version of Cauchy’s integral formula. In contrast to existing generating function approaches, the algorithm relies only on complex quadrature and no algebraic techniques are needed. In view of fast implementations of … Read more

    Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Cutting Plane Approaches Tags , , ,

    Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more

    Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores

  • Tobias Achterberg
  • Timo Berthold
  • Stefan Heinz
  • Thorsten Koch
  • Yuji Shinano
  • Michael Winkler
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Problem Solving Environments Tags , , , , , ,

    Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in … Read more

    Personnel scheduling during Covid-19 pandemic

  • Manuel Iori
  • Anand Subramanian
  • Giorgio Zucchi
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , ,

    This paper addresses a real-life personnel scheduling problem in the context of Covid-19 pandemic, arising in a large Italian pharmaceutical distribution warehouse. In this case study, the challenge is to determine a schedule that attempts to meet the contractual working time of the employees, considering the fact that they must be divided into mutually exclusive … Read more