(Mixed) Integer Linear Programming

Portfolio Optimization with Irreversible Long-Term Investments in Renewable Energy under Policy Risk: A Mixed-Integer Multistage Stochastic Model and a Moving-Horizon Approach

  • Nadine Gatzert
  • Martin Schmidt
  • Alexander Martin
  • Benjamin Seith
  • Nikolai Vogl
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    Portfolio optimization is an ongoing hot topic of mathematical optimization and management science. Due to the current financial market environment with low interest rates and volatile stock markets, it is getting more and more important to extend portfolio optimization models by other types of investments than classical assets. In this paper, we present a mixed-integer … Read more

    Generalized Chvatal-Gomory closures for integer programs with bounds on variables

  • Sanjeeb Dash
  • Oktay Gunluk
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is … Read more

    A Generic Exact Solver for Vehicle Routing and Related Problems

  • Artur Alves Pessoa
  • Ruslan Sadykov
  • Eduardo Uchoa
  • François Vanderbeck
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems Tags , ,

    Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This … Read more

    Risk-Averse Bi-Level Stochastic Network Interdiction Model for Cyber-Security Risk Management

  • Tanveer Hossain Bhuiyan
  • Mahantesh Halappanavar
  • Hugh R. Medal
  • Apurba Nandi
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Stochastic Programming Tags , , , ,

    Security of cyber networks is crucial; recent severe cyber-attacks have had a devastating effect on many large organizations. The attack graph, which maps the potential attack paths of a cyber network, is a popular tool for analyzing cyber system vulnerability. In this study, we propose a bi-level stochastic network interdiction model on an attack graph … Read more

    Decomposing the Train Scheduling Problem into Integer Optimal Polytopes

  • Masoud Barah
  • James Ostrowski
  • Abbas Seifi
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , ,

    This paper presents conditions for which the linear relaxation for the train scheduling problem is integer-optimal. These conditions are then used to identify how to partition a general problem’s feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results … Read more

    Radius of Robust Feasibility for Mixed-Integer Problems

  • Frauke Liers
  • Lars Schewe
  • Johannes Thürauf
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , ,

    For a mixed-integer linear problem (MIP) with uncertain constraints, the radius of robust feasibility (RRF) determines a value for the maximal “size” of the uncertainty set such that robust feasibility of the MIP can be guaranteed. To the best of our knowledge, the approaches for the RRF presented in the literature are restricted to continuous … Read more

    There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

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

    One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level’s dual feasible … Read more

    Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

  • Simge Küçükyavuz
  • Hasan Manzour
  • Ali Shojaie
  • Hao-Hsiang Wu
    • Categories (Mixed) Integer Linear Programming, Statistics Tags , , ,

    Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a … Read more

    Multi-objective optimization models for many-to-one matching problems

  • Natsumi Shimada
  • Yuichi Takano
  • Natsuki Yamazaki
    • Categories (Mixed) Integer Linear Programming, Finance and Economics Tags , , , ,

    This paper is concerned with many-to-one matching problems for assigning residents to hospitals according to their preferences. The stable matching model aims at finding a stable matching, and the assignment game model involves maximizing the total utility; however, these two objectives are incompatible in general. We also focus on a situation where there are predetermined … Read more

    An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes

  • Armin Fügenschuh
  • Fabian Gnegel
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number … Read more