exact algorithm

Robust Continuous-Time Service Network Design under Travel Time Uncertainty

  • Shengnan Shu
  • Zhou Xu
  • Jin Qi
    • Categories Applications - OR and Management Sciences, Network Optimization, Robust Optimization Tags , , , , , ,

    The continuous-time service network design problem (CTSNDP) has wide applications in the field of transportation, but it is complicated by travel time uncertainty resulting from unpredictable traffic conditions. Incorporating uncertain travel times poses a significant challenge, as time-indexed mixed-integer linear programming (MILP) formulations commonly used to solve the CTSNDP with deterministic travel times become impractical. … Read more

    Water Finds its Level: A Localized Method for Multicommodity Flow Problem

  • Pengfei Liu
    • Categories Network Optimization Tags , , , ,

    This paper describes a local-control method for multicommodity flow problem. Both the capacity constraints and the flow conservation constraints are relaxed. If the flow exceeds the capacity on an edge, the edge would have a congestion cost. If the flow into a vertex is not equal to that out of the vertex, the vertex would … Read more

    D-optimal Data Fusion: Exact and Approximation Algorithms

  • Yongchun Li
  • Marcia Fampa
  • Jon Lee
  • Feng Qiu
  • Weijun Xie
    • Categories Combinatorial Optimization, Integer Programming Tags , , , , , , ,

    We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more

    CliSAT: a SAT-based exact algorithm for hard maximum clique problems

  • Pablo San Segundo
  • Fabio Furini
  • David Alvarez
  • Panos M. Pardalos
    • Categories Combinatorial Optimization, Game Theory Tags , , ,

    Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a … Read more

    Political districting to minimize cut edges

  • Austin Buchanan
  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , , , , , ,

    When constructing political districting plans, prominent criteria include population balance, contiguity, and compactness. The compactness of a districting plan, which is often judged by the “eyeball test,” has been quantified in many ways, e.g., Length-Width, Polsby-Popper, and Moment-of-Inertia. This paper considers the number of cut edges, which has recently gained traction in the redistricting literature … Read more

    A new branch-and-filter exact algorithm for binary constraint satisfaction problems

  • Fabio Furini
  • Rafael León
  • Pablo San Segundo
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    A binary constraint satisfaction problem (BCSP) consist in determining an assignment of values to variables which is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. … Read more

    Migration from Sequence to Schedule in Total Earliness and Tardiness Scheduling Problem

  • Mohammad Mahdavi Mazdeh
  • Mohammad Namakshenas
    • Categories Scheduling Tags , , ,

    Services must be delivered with high punctuality to be competitive. The classical scheduling theory offers to minimize the total earliness and tardiness of jobs to deliver punctual services. In this study, we developed a fully polynomial-time optimal algorithm to transform a given sequence, the permutation of jobs, into its corresponding minimum cost schedule, the timing … Read more

    A Column and Constraint Algorithm for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Dynamic Programming, Integer Programming Tags , ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

  • Federico Della Croce
  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Combinatorial Optimization, Dynamic Programming Tags , , ,

    We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more

    A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

  • Pedro J. de Rezende
  • Cid C. de Souza
  • D. C. Tozoni
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more