Integer Programming

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

    Bi-Perspective Functions for Mixed-Integer Fractional Programs with Indicator Variables

  • Adam N. Letchford
  • Qiang Ni
  • Zhaoyu Zhong
    • Categories (Mixed) Integer Nonlinear Programming, Telecommunications Tags , ,

    Perspective functions have long been used to convert fractional programs into convex programs. More recently, they have been used to form tight relaxations of mixed-integer nonlinear programs with so-called indicator variables. Motivated by a practical application (maximising energy efficiency in an OFDMA system), we consider problems that have a fractional objective and indicator variables simultaneously. … Read more

    Constraints reduction programming by subset selection: a study from numerical aspect

  • Yuan Shen
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Convex Optimization Tags , , , , , ,

    We consider a novel method entitled constraints reduction programming which aims to reduce the constraints in an optimization model. This method is derived from various applications of management or decision making, and has potential ability to handle a wider range of applications. Due to the high combinatorial complexity of underlying model, it is difficult to … Read more

    The Vertex k-cut Problem

  • Denis Cornaz
  • Fabio Furini
  • Enrico Malaguti
  • Mathieu Lacroix
  • A. Ridha Mahjoub
  • Sébastien Martin
    • Categories Combinatorial Optimization, Graphs and Matroids, Integer Programming Tags , , ,

    Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex … 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

    Robust Combinatorial Optimization under Convex and Discrete Cost Uncertainty

  • Christoph Buchheim
  • Jannis Kurtz
    • Categories Combinatorial Optimization, Integer Programming, Robust Optimization Tags , , , , ,

    In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more

    Parsimonious formulations for low-diameter clusters

  • Austin Buchanan
  • Hosseinali Salemi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    In the analysis of networks, one often searches for tightly knit clusters. One property of a “good” cluster is a small diameter (say, bounded by $k$), which leads to the concept of a $k$-club. In this paper, we propose new path-like and cut-like integer programming formulations for detecting these low-diameter subgraphs. They simplify, generalize, and/or … 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

    Comparative Analysis of Capacitated Arc Routing Formulations for Branch-Cut-and-Price Algorithms

  • Diego Pecin
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Integer Programming, Transportation

    The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies … 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