# Strong Bounds for Resource Constrained Project Scheduling: Preprocessing and Cutting Planes

arXiv: https://arxiv.org/abs/1909.02737 · HTML: https://mlsanity.com/paper/1909.02737/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP](https://mlsanity.com/paper/2206.01857/) (2022)

## Abstract (arXiv)

Resource Constrained Project Scheduling Problems (RCPSPs) without preemption are well-known NP-hard combinatorial optimization problems. A feasible RCPSP solution consists of a time-ordered schedule of jobs with corresponding execution modes, respecting precedence and resources constraints. In this paper, we propose a cutting plane algorithm to separate five different cut families, as well as a new preprocessing routine to strengthen resource-related constraints. New lifted versions of the well-known precedence and cover inequalities are employed. At each iteration, a dense conflict graph is built considering feasibility and optimality conditions to separate cliques, odd-holes and strengthened Chv'atal-Gomory cuts. The proposed strategies considerably improve the linear relaxation bounds, allowing a state-of-the-art mixed-integer linear programming solver to find provably optimal solutions for 754 previously open instances of different variants of the RCPSPs, which was not possible using the original linear programming formulations.