# Presolving techniques and linear relaxations for cumulative scheduling

## Heinz, Stefan

In the mathematical optimization community the term scheduling usually describes the computation of a sequential plan for a set of jobs w.r.t. a set of side conditions such as precedence constraints and resource restrictions. Thereby, a certain objective should be fulfilled which can be for example to minimize the latest completion time of all jobs. The sequential plan can be an ordering of the jobs or in case of this dissertation a schedule which assigns a start time to each job. Many scheduling problems can be modeled and solved as a constraint program as well as a mixed-integer (linear) program. Both approaches have their advantages and disadvantages which are often complementary. In this dissertation we use a hybrid approach, called constraint integer programming, to solve scheduling problems. We focus on scheduling problems which contain a cumulative resource structure: the available resources are renewable and can be shared between jobs which have to be scheduled non-preemptively. We define the class of energy-based propagation algorithms which are inference algorithms for the cumulative resource structure using volume arguments to infer bounds on the start time and the completion time of a job. Many of the known propagation algorithms for the cumulative resource structure, such as time-tabling, edge-finding, time-tabling edge-finding, and energetic reasoning, belong to this class. For this class we develop explanations for their inferred bound changes. These explanations are used during the analyzes of infeasible sub-problem to retrieve additional (redundant) constraints which help to solve a particular problem more quickly. This concept generalizes known explanations for propagation algorithms for the cumulative resource structure. In addition we show that each energy-based propagation algorithm implies a linear relaxation for the cumulative resource structure with optional jobs. For current state-of-the-art mixed-integer programming solvers presolving is an important feature. During presolving, the original problem is reformulated into a hopefully easier-to-solve problem. One aim is to remove redundant variables and constraints. For the cumulative resource structure we present several presolving techniques generalizing the concept of dual reductions, which is known for mixed-integer programs to shrink a problem formulation, to constraint programs. This techniques allows us to remove feasible or even optimal solutions from the solution space as long as one optimal solution remains in case that the problem is feasible. Using this idea we develop several dual reduction steps for the cumulative resource structure. These reductions enable the removal of jobs from a cumulative resource with the knowledge that this job can be scheduled independently of the schedule for the remaining jobs. In a computational study, we analyze the impact of the presolving techniques for the cumulative constraint and the linear relaxations for the cumulative constraint with optional jobs. Therefore, we use two problem classes which are resource-constrained project scheduling problems and resource allocation and scheduling problem.
In der mathematischen Optimierung bezeichnet der Begriff Scheduling die Berechnung eines Ablaufplans, die eine gegebenen Menge von Prozessen (Jobs), typischerweise mit Reihenfolgebeziehungen, einer Menge von beschrÃ¤nkten Ressourcen (z.B. Maschinen) zuordnet, meist mit dem Ziel die spÃ¤teste Fertigstellungszeit aller Jobs zu minimieren. Scheduling-Probleme lassen sich sowohl als Gemischt-Ganzzahlige (Lineare) Programme als auch als Constraint-Programme modellieren und lÃ¶sen. Beide AnsÃ¤tze haben ihre StÃ¤rken und SchwÃ¤chen, diese sind aber in vielerlei Hinsicht komplementÃ¤r. In der vorliegenden Arbeit verwenden wir einen integrierten Ansatz, die sogenannte Constraint-Ganzzahlige Programmierung, um Scheduling-Probleme zu lÃ¶sen. Wir konzentrieren uns auf Scheduling-Probleme mit Kumulativ-Bedingungen, d.h. es gibt Ressourcen, welche sich mehrere nicht-unterbrechbare Jobs teilen. Wir definieren die Klasse von energiebasierten Propagierungsalgorithmen fÃ¼r Kumulativ-Bedingungen, welche Volumenargumente nutzen, um die Startzeit und Endzeit eines Jobs zu beschrÃ¤nken. Viele aus der Literatur bekannte Propagierungsalgorithmen, wie time-tabling, edge-finding, time-tabling edge-finding und energetic reasoning, gehÃ¶ren zu dieser Klasse. FÃ¼r die Klasse der energiebasierten Propagierungsalgorithmen entwickeln wir allgemeine ErklÃ¤rungen fÃ¼r die propagierten Schranken. Diese ErklÃ¤rungen werden in der Analyse von unzulÃ¤ssigen Teilproblemen genutzt, um zusÃ¤tzliche gÃ¼ltige Bedingungen zu lernen. Dabei generalisieren wir aus der Literatur bekannte ErklÃ¤rungen fÃ¼r Propagierungsalgorithmen fÃ¼r Kumulativ-Bedingungen. ZusÃ¤tzlich zeigen wir, dass jeder energiebasierte Propagierungsalgorithmus eine lineare Relaxierung fÃ¼r Kumulativ-Bedingung mit optionalen Jobs impliziert. Diese Relaxierung kann genutzt werden, um die lineare Relaxierung eines Constraint-Ganzzahligen Programms zu verstÃ¤rken. Presolving-Verfahren sind ein wichtiger algorithmischer Bestandteil zum LÃ¶sen Gemischt-Ganzzahlige Programme. Presolving-Verfahren reformulieren das Original-Problem in ein (hoffentlich) leichter zu lÃ¶sendes Problem. Oftmals werden dabei redundante Variablen und Bedingungen eliminiert. Wir entwickeln diverse Presolving-Verfahren fÃ¼r Kumulativ-Bedingungen vor. Unter anderem verallgemeinern wir das Konzept der dualen Reduktion, welches in der Gemischt-Ganzzahligen Programmierung fÃ¼r Problemvereinfachungen genutzt wird, auf die Constraint-Programmierung. Solch eine Reduktion kann genutzt werden, um zulÃ¤ssige oder sogar optimale LÃ¶sungen aus dem LÃ¶sungsraum zu entfernen, solange sicher gestellt wird, dass nicht alle OptimallÃ¶sung entfernt werden. Wenn es beispielsweise eine Bearbeitungszeit fÃ¼r einen Job gibt, aus der sich keinerlei EinschrÃ¤nkungen fÃ¼r andere Jobs ergeben, kann dieser dort platziert werden und aus der entsprechenden Kumulativ-Bedingung entfernt werden. In einem umfangreichen Rechenexperiment zeigen wir, dass der im Rahmen dieser Arbeit entwickelte Scheduling-LÃ¶ser kompetitiv zu den besten aus der Literatur bekannten Scheduling-LÃ¶sern ist. Dabei ist zu bemerken, dass die entwickelten Techniken allgemein gÃ¼ltig sind fÃ¼r die Constraint-Ganzzahlige Programmierung. Das heiÃŸt, diese Techniken kÃ¶nnen allgemein zum LÃ¶sen aller Gemischt-Ganzzahligen Programme, die Kumulativ- Bedingungen enthalten, genutzt werden und sind nicht problemspezifisch.