integer programming

Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case

  • Chun Yu Hong
  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. Citation An extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016 Article Download View Equivariant … Read more

    A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs

  • Vicky Mak-Hau
    • Categories Polyhedra Tags , , , ,

    In this paper, we study the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Car- dinality Constrained Cycle and Chain Problem (CCCCP). A feasible solution allows one or more cardinality-constrained cycles to exist on the digraph. A vertex can only be involved in at most one cycle, and there may be vertices not involved in any … Read more

    Beating the SDP bound for the floor layout problem: A simple combinatorial idea

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories Facility Planning and Design, Integer Programming Tags ,

    For many Mixed-Integer Programming (MIP) problems, high-quality dual bounds can obtained either through advanced formulation techniques coupled with a state-of-the-art MIP solver, or through Semidefinite Programming (SDP) relaxation hierarchies. In this paper, we introduce an alternative bounding approach that exploits the “combinatorial implosion” effect by solving portions of the original problem and aggregating this information … Read more

    Strong mixed-integer formulations for the floor layout problem

  • Santanu S. Dey
  • Joey Huchette
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design Tags ,

    The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes … Read more

    Robust Nonparametric Testing for Causal Inference in Observational Studies

  • Md. Noor-E-Alam
  • Cynthia Rudin
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Data-Mining Tags , , , , ,

    We consider the decision problem of making causal conclusions from observational data. Typically, using standard matched pairs techniques, there is a source of uncertainty that is not usually quanti fied, namely the uncertainty due to the choice of the experimenter: two di fferent reasonable experimenters can easily have opposite results. In this work we present an alternative … Read more

    New Exact Approaches to Row Layout Problems

  • Anja Fischer
  • Frank Fischer
  • Philipp Hungerländer
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Facility Planning and Design Tags , , ,

    Given a set of departments, a number of rows and pairwise connectivities between these departments, the multi-row facility layout problem (MRFLP) looks for a non-overlapping arrangement of these departments in the rows such that the weighted sum of the center-to-center distances is minimized. As even small instances of the (MRFLP) are rather challenging, several special … Read more

    Another pedagogy for pure-integer Gomory

  • Qi He
  • Jon Lee
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , , , , ,

    We present pure-integer Gomory cuts in a way so that they are derived with respect to a “dual form” pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In … Read more

    The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

  • Fabio Furini
  • Carlo Alfredo Persiani
  • Paolo Toth
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , , ,

    The integration of Unmanned Aircraft Systems (UAS) into civil airspace is one of the most challenging problems for the automation of the Controlled Airspace, and the optimization of the UAS route is a key step for this process. In this paper, we optimize the planning phase of a UAS mission that consists of departing from … Read more

    New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

  • Matthias Köppe
  • Yuan Zhou
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles several open questions. Article Download View New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

    Sparse optimization for inverse problems in atmospheric modelling

  • Lukáš Adam
  • Martin Branda
    • Categories 0-1 Programming, Civil and Environmental Engineering Tags , , , , ,

    We consider inverse problems in atmospheric modelling. Instead of using the ordinary least squares, we add a weighting matrix based on the topology of measurement points and show the connection with Bayesian modelling. Since the source–receptor sensitivity matrix is usually ill-conditioned, the problem is often regularized, either by perturbing the objective function or by modifying … Read more