Combinatorial Optimization

Finding the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling

  • Yunpeng Pan
  • Leyuan Shi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization

    We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. CitationSubmitted for publication.ArticleDownload View PDF

    Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\

  • Leonid Gurvits
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more

    Solving a combinatorial problem using a local optimization in ant based system

  • D. Dumitrescu
  • C-M. Pintea
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Local optimizations introduced to obtain improved tours for Traveling Salesman Problem have a great impact on the final solution. That is way we introduce a new ant system algorithm with a new local updating pheromone rule, and the tours are improved using k-opt techniques. The tests use different parameters, in order to obtain solutions close … Read more

    Approximating the Chromatic Number of a Graph by Semidefinite Programming

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more

    Alternative Formulation for the p-median Problem

  • Sourour Elloumi
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , , ,

    Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem … Read more

    Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

  • Pierre Hansen
  • Martine Labbé
  • David Schindl
    • Categories Branch and Cut Algorithms, Graphs and Matroids Tags , , ,

    We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more

    Comparing Imperfection Ratio and Imperfection Index for Graph Classes

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It … Read more

    On Ants, Bacteria and Dynamic Environments

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Global Optimization, Meta Heuristics, Robust Optimization Tags , , , ,

    Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective “swarm” intelligence. Termite colonies – for instance – build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any … Read more

    MW: A Software Framework for Combinatorial Optimization on Computational Grids

  • Wasu Glankwamdee
  • Jeff Linderoth
    • Categories Combinatorial Optimization, Parallel Algorithms Tags , , ,

    Our goal in this paper is to demonstrate that branch-and-bound algorithms for combinatorial optimization can be effectively implemented on a relatively new type of multiprocessor platform known as a computational grid. We will argue that to easily and effectively harness the power of computational grids for branch-and-bound algorithms, the master-worker paradigm should be used to … Read more