Constraint-Propagation-Based Cutting Planes: An Application to the Resource-Constrained Project Scheduling Problem

Sophie Demassey · Christian Artigues · Philippe Yves Paul Michelon

74 citations0/0 files storedINFORMS journal on computing

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Resource-Constrained Project Scheduling Scheduling and Optimization Algorithms Constraint Satisfaction and Optimization

Abstract

We propose a cooperation method between constraint programming and integer programming to compute lower bounds for the resource-constrained project scheduling problem (RCPSP). The lower bounds are evaluated through linear-programming (LP) relaxations of two different integer linear formulations. Efficient resource-constraint propagation algorithms serve as a preprocessing technique for these relaxations. The originality of our approach is to use additionally some deductions performed by constraint propagation, and particularly by the shaving technique, to derive new cutting planes that strengthen the linear programs. Such new valid linear inequalities are given in this paper, as well as a computational analysis of our approach. Through this analysis, we also compare the two considered linear formulations for the RCPSP and confirm the efficiency of lower bounds computed in a destructive way.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 74 citations exist upstream.

References

1999Resource-constrained project scheduling: Notation, classification, models, and methods 1969Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach 1995Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems 1992A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem 1987Project scheduling with resource constraints: A branch and bound approach 1998An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation 1998A branch and bound algorithm for the resource-constrained project scheduling problem 1997New Benchmark Results for the Resource-Constrained Project Scheduling Problem

Cited by

2012Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources 2014Mixed-Integer Linear Programming Formulations 2004Tight LP bounds for resource constrained project scheduling 2009Project scheduling with limited resources using a genetic algorithm

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.