Combinatorial Optimization

On implementation of local search and genetic algorithm techniques for some combinatorial optimization problems

  • Anton Bondarenko
    • Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics Tags , , , , ,

    In this paper we propose the approach to solving several combinatorial optimization problems using local search and genetic algorithm techniques. Initially this approach was developed in purpose to overcome some difficulties inhibiting the application of above-mentioned techniques to the problems of the Questionnaire Theory. But when the algorithms were developed it became clear that them … Read more

    On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

  • Alberto Costa
  • Pierre Hansen
  • Leo Liberti
    • Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

    We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more

    Efficient Solutions for the Far From Most String Problem

  • Paola Festa
  • Panos M. Pardalos
    • Categories Basic Sciences Applications, Combinatorial Optimization, Meta Heuristics Tags , , , ,

    Computational molecular biology has emerged as one of the most exciting interdisciplinary fields. It has currently benefited from concepts and theoretical results obtained by different scientific research communities, including genetics, biochemistry, and computer science. In the past few years it has been shown that a large number of molecular biology problems can be formulated as … Read more

    Job-Shop Scheduling in a Body Shop

  • Joachim Schauer
  • Cornelius Schwarz
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more

    Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

  • Edward D. Kim
    • Categories Polyhedra Tags , ,

    We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of … Read more

    New VNS heuristic for Total Flowtime Flowshop Scheduling Problem

  • Wagner Emanoel Costa
  • Elizabeth G. Goldbarg
  • Marco César Goldbarg
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    This paper develops a new VNS approach to Permutational Flow shop Scheduling Problem with Total Flow time criterion. There are many hybrid approaches inthe problem’s literature, that make use of VNS internally, usually applying job insert neighbourhood followed by job interchange neighbourhood. In this study different ways to combine both neighbourhoods were examined. All tests … Read more

    Solution Methods for the Multi-trip Elementary Shortest Path Problem with Resource Constraints

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Combinatorial Optimization, Transportation Tags , ,

    We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more

    LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison

  • Marzena Fuegenschuh
  • Christoph Helmberg
  • Alexander Martin
    • Categories Branch and Cut Algorithms, Polyhedra Tags , , ,

    While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit … Read more

    Recoverable Robust Knapsack: the Discrete Scenario Case

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , ,

    Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach … Read more