Combinatorial Optimization

A Decision Tool based on a Multi-Objective Methodology for designing High-Pressure Thermal Treatments in Food Industry

  • Miriam R. Ferrández
  • Benjamin Ivorra
  • Pilar M. Ortigosa
  • Ángel M. Ramos
  • Juana L. Redondo
    • Categories Meta Heuristics, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , , ,

    In this work, we propose a methodology for designing High-Pressure Thermal processes for food treatment. This approach is based on a multi-objective preference-based evolutionary optimization algorithm, called WASF-GA, combined with a decision strategy which provides the food engineer with the best treatment in accordance with some quality requirements. The resulting method is compared to a … Read more

    A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming Strong Duality into combinatorial min-max theorems. The definition of total dual integrality (TDI) revolves around the existence of optimal dual solutions that are integral, and thus naturally applies … Read more

    A polynomial time algorithm for the linearization problem of the QSPP and its applications

  • Hao Hu
  • Renata Sotirov
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    Given an instance of the quadratic shortest path problem (QSPP) on a digraph $G$, the linearization problem for the QSPP asks whether there exists an instance of the linear shortest path problem on $G$ such that the associated costs for both problems are equal for every $s$-$t$ path in $G$. We prove here that the … Read more

    The Clique Problem with Multiple-Choice Constraints under a Cycle-Free Dependency Graph

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
    • Categories Graphs and Matroids, Polyhedra, Scheduling Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC) represents a very common substructure in many real-world applications, for example scheduling problems with precedence constraints. It consists in finding a clique in a graph whose nodes are partitioned into subsets, such that exactly one node from each subset is chosen. Even though we can show that (CPMC) … Read more

    Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization

  • Andreas Bärmann
  • Maximilian Merkert
  • Thorsten Gellermann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This new special case, which we call staircase compatibility, generalizes common properties in several applications and allows for a linear description of the integer feasible … Read more

    The first heuristic specifically for mixed-integer second-order cone optimization

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Integer Programming, Second-Order Cone Programming Tags , ,

    Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more

    A Branch-and-Benders-Cut Algorithm for the Road Restoration Crew Scheduling and Routing Problem

  • Douglas Alem
  • Pedro Munari
  • Alfredo Moreno
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers … Read more

    The Maximum Clique Interdiction Problem

  • Fabio Furini
  • Ivana Ljubić
  • Sébastien Martin
  • Pablo San Segundo
    • Categories Graphs and Matroids, Integer Programming Tags , , ,

    Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of … Read more

    Iterative weighted thresholding method for sparse solution of underdetermined linear equations

  • Jianli Chen
  • Peng Zheng
  • Wenxing Zhu
  • Zilin Huang
    • Categories Combinatorial Optimization Tags , ,

    Recently, iterative reweighted methods have attracted much interest in compressed sensing, since they perform better than unweighted ones in most cases. Currently, weights are chosen heuristically in existing iterative reweighted methods, and nding an optimal weight is an open problem since we do not know the exact support set beforehand. In this paper, we present … Read more

    Bicriteria Approximation of Chance Constrained Covering Problems

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Combinatorial Optimization, Robust Optimization, Stochastic Programming

    A chance constrained optimization problem involves constraints with random data which can be violated with probability bounded above by a prespecified small risk parameter. Such constraints are used to model reliability requirements in a variety of application areas such as finance, energy, service and manufacturing. Except under very special conditions, chance constrained problems are extremely … Read more