(Mixed) Integer Linear Programming

Stabilized Benders methods for large-scale combinatorial optimization, with application to data privacy

  • Daniel Baena
  • Jordi Castro
  • Antonio Frangioni
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Cutting Plane Approaches

    The Cell Suppression Problem (CSP) is a challenging Mixed-Integer Linear Problem arising in statistical tabular data protection. Medium sized instances of CSP involve thousands of binary variables and million of continuous variables and constraints. However, CSP has the typical structure that allows application of the renowned Benders’ decomposition method: once the “complicating” binary variables are … Read more

    Enhanced Pseudo-Polynomial Formulations for Bin Packing and Cutting Stock Problems

  • Maxence Delorme
  • Manuel Iori
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    We study pseudo-polynomial formulations for the classical bin packing and cutting stock problems. We first propose an overview of dominance and equivalence relations among the main pattern-based and pseudo-polynomial formulations from the literature. We then introduce reflect, a new formulation that uses just half of the bin capacity to model an instance and needs significantly … Read more

    A New Exact Algorithm to Optimize a Linear Function Over the Set of Efficient Solutions for Bi-objective Mixed Integer Linear Programs

  • Hadi Charkhgard
  • Alvaro Sierra-Altamiranda
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of bi-objective mixed integer linear programs. The proposed algorithm is developed based on the Triangle Splitting Method (Boland et al. 2015b) which can find a full representation of the nondominated frontier of any bi-objective mixed integer … Read more

    A mixed-integer branching approach for very small formulations of disjunctive constraints

  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    We study the existence and construction of very small formulations for disjunctive constraints in optimization problems: that is, formulations that use very few integer variables and extra constraints. To accomplish this, we present a novel mixed-integer branching formulation framework, which preserves many of the favorable algorithmic properties of a traditional mixed-integer programming formulation, including amenability … Read more

    Partially-Ranked Choice Models for Data-Driven Assortment Optimization

  • Sanjay Dominik Jena
  • Andrea Lodi
  • Hugo Palmer
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Marketing

    The assortment of products carried by a store has a crucial impact on its success. However, finding the right mix of products to attract a large portion of the customers is a challenging task. Several mathematical models have been proposed to optimize assortments. In particular, rank-based choice models have been acknowledged for representing well high-dimensional … Read more

    FPBH.jl: A Feasibility Pump Based Heuristic for Multi-objective Mixed Integer Linear Programming in Julia

  • Hadi Charkhgard
  • Aritra Pal
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Optimization Software and Modeling Systems Tags , , , ,

    Feasibility pump is one of the successful heuristic solution approaches developed almost a decade ago for computing high-quality feasible solutions of single-objective integer linear programs, and it is implemented in exact commercial solvers such as CPLEX and Gurobi. In this study, we present the first Feasibility Pump Based Heuristic (FPBH) approach for approximately generating nondominated … Read more

    Shaping and Trimming Branch-and-bound Trees

  • Philipp M. Christophel
  • Imre Pólik
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags ,

    We present a new branch-and-bound type search method for mixed integer linear optimization problems based on the concept of offshoots (introduced in this paper). While similar to a classic branch-and-bound method, it allows for changing the order of the variables in a dive (shaping) and removing unnecessary branching variables from a dive (trimming). The regular … Read more

    Optimized Assignment Patterns in Mobile Edge Cloud Networks

  • Alberto Ceselli
  • Marco Fiore
  • Marco Premoli
  • Stefano Secci
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Telecommunications Tags , , ,

    Given an existing Mobile Edge Cloud (MEC) network including virtualization facilities of limited capacity, and a set of mobile Access Points (AP) whose data traffic demand changes over time, we aim at finding plans for assigning APs traffic to MEC facilities so that the demand of each AP is satisfied and MEC facility capacities are … Read more

    New solution approaches for the maximum-reliability stochastic network interdiction problem

  • James R. Luedtke
  • Eli Towle
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a … Read more

    Electric Power Infrastructure Planning: Mixed-Integer Programming Model and Nested Decomposition Algorithm

  • Ignacio E. Grossmann
  • Dimitri J. Papageorgiou
  • Cristiana L. Lara
  • D. Mallapragada
  • A. Venkatesh
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering Tags , , , , ,

    This paper addresses the long-term planning of electric power infrastructures considering high renewable penetration. To capture the intermittency of these sources, we propose a deterministic multi-scale Mixed-Integer Linear Programming (MILP) formulation that simultaneously considers annual generation investment decisions and hourly operational decisions. We adopt judicious approximations and aggregations to improve its tractability. Moreover, to overcome … Read more