Combinatorial Optimization

A parametric active set method for quadratic programs with vanishing constraints

  • Hans Georg Bock
  • Christian Kirches
  • Andreas Potschka
  • Sebastian Sager
    • Categories Combinatorial Optimization, Control Applications, Quadratic Programming Tags , , ,

    Combinatorial and logic constraints arising in a number of challenging optimization applications can be formulated as vanishing constraints. Quadratic programs with vanishing constraints (QPVCs) then arise as subproblems during the numerical solution of such problems using algorithms of the Sequential Quadratic Programming type. QPVCs are nonconvex problems violating standard constraint qualifications. In this paper, we … Read more

    The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm

  • Hernan Abeledo
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Polyhedra Tags ,

    The Time Dependent Traveling Salesman Problem (TDTSP) is a generalization of the classical Traveling Salesman Problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. … Read more

    Biased random-key genetic algorithms with applications in telecommunications

  • Mauricio G.C. Resende
    • Categories Applications - OR and Management Sciences, Meta Heuristics, Telecommunications Tags , , , , , ,

    This paper surveys several applications of biased random-key genetic algorithms (BRKGA) in optimization problems that arise in telecommunications. We first review the basic concepts of BRKGA. This is followed by a description of BRKGA-based heuristics for routing in IP networks, design of survivable IP networks, redundant server location for content distribution, regenerator location in optical … Read more

    A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering

  • Luciana S. Pessoa
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , , , , , , , ,

    The set multicovering or set K-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least K times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set K-covering problem, … Read more

    Convex Graph Invariants

  • Venkat Chandrasekaran
  • Pablo A. Parrilo
  • Alan S. Willsky
    • Categories Convex Optimization, Graphs and Matroids, Robust Optimization

    The structural properties of graphs are usually characterized in terms of invariants, which are functions of graphs that do not depend on the labeling of the nodes. In this paper we study convex graph invariants, which are graph invariants that are convex functions of the adjacency matrix of a graph. Some examples include functions of … Read more

    Formulations for Dynamic Lot Sizing with Service Levels

  • Dinakar Gade
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more

    A Branch-and-Price Approach to the k-Clustering Minimum Biclique Completion Problem

  • Stefano Gualandi
  • Francesco Maffioli
  • Claudio Magni
    • Categories Applications - OR and Management Sciences, Graphs and Matroids, Integer Programming Tags , , ,

    Given a bipartite graph G = (S , T , E ), we consider the problem of finding k bipartite subgraphs, called clusters, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and … Read more

    On Computation of Performance Bounds of Optimal Index Assignment

  • Hans D Mittelmann
  • Xiaolin Wu
  • J. Wang
  • X. Wang
    • Categories Applications - Science and Engineering, Combinatorial Optimization, Semi-definite Programming Tags , , , , ,

    Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more