Combinatorial Optimization

Improving the LP bound of a MILP by dual concurrent branching and the relationship to cut generation methods

  • H. Georg Büsching
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags ,

    In this paper branching for attacking MILP is investigated. Under certain circumstances branches can be done concurrently. By introducing a new calculus it is shown there are restrictions for dual values. As a second result of this study a new class of cuts for MILP is found, which are defined by those values. This class … Read more

    A branch and cut algorithm for minimum spanning trees under conflict constraints

  • Phillippe Samer
  • Sebastián Urrutia
    • Categories 0-1 Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , ,

    We study approaches for the exact solution of the \NP–hard minimum spanning tree problem under conflict constraints. Given a graph $G(V,E)$ and a set $C \subset E \times E$ of conflicting edge pairs, the problem consists of finding a conflict-free minimum spanning tree, i.e. feasible solutions are allowed to include at most one of the … Read more

    Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs

  • Nir Halman
  • Diego Klabjan
  • James B. Orlin
  • David Simchi-Levi
  • Chung-Lun Li
    • Categories Approximation Algorithms, Dynamic Programming

    We present a framework for obtaining Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two sets of computational rules, namely the Calculus of K-approximation Functions and the Calculus of K-approximation Sets. Using our framework, we provide … Read more

    Scheduling on uniform nonsimultaneous parallel machines

  • Donald K. Friesen
  • Liliana Grigoriu
    • Categories Approximation Algorithms, Combinatorial Optimization, Scheduling Tags ,

    We consider the problem of scheduling on uniform processors with nonsimultaneous machine available times with the purpose of mini\-mi\-zing the maximum completion time. We give a variant of the Multifit algorithm which generates schedules which end within $1.382$ times the optimal maximum completion times. This results from properties of the Multifit algorithm when used for … Read more

    New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Global Optimization Tags , , , , ,

    The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest … Read more

    Handelman’s hierarchy for the maximum stable set problem

  • Monique Laurent
  • Zhao Sun
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming

    The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope can … Read more

    Near-Optimal Algorithms for Capacity Constrained Assortment Optimization

  • Antoine Desir
  • Vineet Goyal
    • Categories Applications - OR and Management Sciences, Approximation Algorithms, Combinatorial Optimization Tags , ,

    Assortment optimization is an important problem that arises in many practical applications such as retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximizes the expected revenue in the presence of the substitution behavior of consumers specified by a choice model. In this paper, we … Read more

    Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems

  • Alper Uygur
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling Tags , , ,

    This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more

    Analysis of MILP Techniques for the Pooling Problem

  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Global Optimization Tags , , , , ,

    The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear … Read more