Combinatorial Optimization

Multi-objective Optimization Based Algorithms for Solving Mixed Integer Linear Minimum Multiplicative Programs

  • Hadi Charkhgard
  • Vahid Mahmoodian
  • Yu Zhang
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization

    We present two new algorithms for a class of single-objective non-linear optimization problems, the so-called Mixed Integer Linear minimum Multiplicative Programs (MIL-mMPs). This class of optimization problems has a desirable characteristic: a MIL-mMP can be viewed as a special case of the problem of optimization over the efficient set in multi-objective optimization. The proposed algorithms … Read more

    Persistency of Linear Programming Formulations for the Stable Set Problem

  • Elisabeth Rodriguez-Heck
  • Matthias Walter
  • Karl Stickler
  • Stefan Weltge
    • Categories 0-1 Programming, Polyhedra Tags , ,

    The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP … Read more

    Minimizing Airplane Boarding Time

  • Andreas M. Tillmann
  • Felix J. L. Willamowski
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , ,

    The time it takes passengers to board an airplane is known to influence the turn-around time of the aircraft and thus bears a significant cost-saving potential for airlines. Although minimizing boarding time therefore is the most important goal from an economic perspective, previous efforts to design efficient boarding strategies apparently never tackled this task directly. … Read more

    A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

  • S.C. Fang
  • Ruotian Gao
  • Wenxun Xing
  • Cheng Lu
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

    Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs

  • Gregory A. Kasapidis
  • Dimitris C. Paraskevopoulos
  • Panagiotis P. Repoussis
  • Christos D. Tarantilis
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential; however, in practice there can be multiple connections and finish-to-start dependencies among the operations of each job. This paper studies flexible job shop scheduling problems with arbitrary precedence graphs. Rigorous mixed integer and constraint … Read more

    Query Batching Optimization in Database Systems

  • Hadi Charkhgard
  • Iman Dayarian
  • Mehrad Eslami
  • Vahid Mahmoodian
  • Yicheng Tu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Multidisciplinary Design Optimization

    Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong … Read more

    A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization

  • Christoph Buchheim
    • Categories Combinatorial Optimization, Robust Optimization

    For many classical combinatorial optimization problems such as, e.g., the shortest path problem or the spanning tree problem, the robust counterpart under general discrete, polytopal, or ellipsoidal uncertainty is known to be intractable. This implies that any algorithm solving the robust counterpart that can access the underlying certain problem only by an optimization oracle has … Read more

    A bi-level branch-and-bound algorithm for the capacitated competitive facility location problem

  • Hadi Charkhgard
  • Vahid Mahmoodian
  • Yu Zhang
    • Categories Branch and Cut Algorithms, Supply Chain Management Tags , , ,

    Competitive facility location problem is a typical facility locating optimization problem but in a competitive environment. The main characteristic of this problem is the competitive nature of the market. In essence, the problem involves two competitors, i.e., a leader and a follower, who seek to attract customers by establishing new facilities to maximize their own … Read more

    Single Allocation Hub Location with Heterogeneous Economies of Scale

  • Okan Arslan
  • Masoud Chitsaz
  • Gilbert Laporte
  • Andrea Lodi
  • Borzou Rostami
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , , ,

    We study the single allocation hub location problem with heterogeneous economies of scale (SAHLP-h). The SAHLP-h is a generalization of the classical single allocation hub location problem (SAHLP), in which the hub-hub connection costs are piecewise linear functions of the amounts of flow. We model the problem as an integer non-linear program, which we then … Read more

    Vertex ordering with optimal number of adjacent predecessors

  • Tangi Migot
  • Jérémy Omer
    • Categories Combinatorial Optimization Tags , , ,

    In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function.Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such … Read more