Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in K-dimensional space such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called … Read more
The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more
The Traveling Salesman Problem with Pickup and Delivery (TSPPD) describes the problem of finding a minimum cost path in which pickups precede their associated deliveries. The TSPPD is particularly important in the growing field of Dynamic Pickup and Delivery Problems (DPDP). These include the many-to-many Dial-A-Ride Problems (DARP) of companies such as Uber and Lyft, … Read more
Existing approaches to identify multiple solutions to combinatorial problems in practice are at best limited in their ability to simultaneously incorporate both diversity among generated solutions, as well as problem-specific desires that are apriori unknown, or at least difficult to articulate, for the end-user. We propose a general framework that can generate a set of … Read more
There is an undeniable global shortage of skillful nurses. This is a problem of high priority, which is correlated to workforce management issues. These issues can be palliated by increasing nurses’ satisfaction based on flexible rosters using automated nurse rostering. This paper in concerned with nurse rostering based on constraint programming by satisfying global constraints, … Read more
We propose a constraint programming approach for the optimization of inventory routing in the liquefied natural gas industry. We present two constraint programming models that rely on a disjunctive scheduling representation of the problem. We also propose an iterative search heuristic to generate good feasible solutions for these models. Computational results on a set of … Read more
We show that global optimization techniques, based on interval analysis and constraint propagation, succeed in solving the classical problem of optimization of the Belgium gas network. Citation Published as Inria Research report RR-7796, November 2011. Article Download View Global optimization of pipe networks by the interval analysis approach: the Belgium network case
We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but … Read more
This paper considers constraint propagation methods for continuous constraint satisfaction problems consisting of linear and quadratic constraints. All methods can be applied after suitable preprocessing to arbitrary algebraic constraints. The basic new techniques consist in eliminating bilinear entries from a quadratic constraint, and solving the resulting separable quadratic constraints by means of a sequence of … Read more
Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling … Read more