integer programming

A parametric programming approach to redefine the global configuration of resource constraints of 0-1-Integer Linear Programming problems.

  • Alejandro Crema
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Multi-Criteria Optimization Tags , , , ,

    A mathematical programming approach to deal with the global configuration of resource constraints is presented. A specialized parametric programming algorithm to obtain the pareto set for the biobjective problem that appears to deal with the global configuration for 0-1-Integer Linear Programing problems is presented and implemented. Computational results for Multiconstrained Knapsack problems and Bounded Knapsack … Read more

    Mixed Integer Quadratic Optimization Formulations for Eliminating Multicollinearity Based on Variance Inflation Factor

  • Ken Kobayashi
  • Tomomi Matsui
  • Ryuhei Miyashiro
  • Kazuhide Nakata
  • Yuichi Takano
  • Ryuta Tamura
    • Categories Applications - Science and Engineering, Integer Programming, Statistics Tags , , , , ,

    The variance inflation factor, VIF, is the most frequently used indicator for detecting multicollinearity in multiple linear regression models. This paper proposes two mixed integer quadratic optimization formulations for selecting the best subset of explanatory variables under upper-bound constraints on VIF of selected variables. Computational results illustrate the effectiveness of our optimization formulations based on … Read more

    Improving the Randomization Step in Feasibility Pump

  • Santanu S. Dey
  • Andres Iroume
  • Marco Molinaro
  • Domenico Salvagnin
    • Categories 0-1 Programming, Stochastic Programming Tags , , ,

    Feasibility pump (FP) is a successful primal heuristic for mixed-integer linear programs (MILP). The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the LP relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have … Read more

    Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    Decomposition of loosely coupled integer programs: A multiobjective perspective

  • Shabbir Ahmed
  • Merve Bodur
  • Natashia Boland
  • George L. Nemhauser
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition algorithm to solve loosely coupled IPs. … Read more

    On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width

  • Sanjeeb Dash
  • Oktay Gunluk
  • Diego Moran
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    For a fixed integer $t > 0$, we say that a $t$-branch split set (the union of $t$ split sets) is dominated by another one on a polyhedron $P$ if all cuts for $P$ obtained from the first $t$-branch split set are implied by cuts obtained from the second one. We prove that given a … Read more

    Aggregation-based cutting-planes for packing and covering integer programs

  • Merve Bodur
  • Alberto Del Pia
  • Santanu S. Dey
  • Sebastian Pokutta
  • Marco Molinaro
    • Categories Cutting Plane Approaches, Integer Programming Tags , , , ,

    In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined … Read more

    Mixed-integer Programming Based Approaches for the Movement Planner Problem: Model, Heuristics and Decomposition

  • Chiwei Yan
  • Luyi Yang
    • Categories Scheduling, Transportation Tags , , , ,

    This is the first prize winning report for the 2012 INFORMS Railway Application Section Problem Solving Competition (https://www.informs.org/Community/RAS/Problem-Solving-Competition/2012-RAS-Problem-Solving-Competition). Article Download View Mixed-integer Programming Based Approaches for the Movement Planner Problem: Model, Heuristics and Decomposition

    A combinatorial approach for small and strong formulations of disjunctive constraints

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

    We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

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

    We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more