Preprocessing and tightening methods for time-indexed MIP chemical production scheduling models

Andres F. Merchan, Christos T. Maravelias

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We propose a series of preprocessing algorithms for the generation of strong valid inequalities for time-indexed, discrete and continuous, mixed-integer programming scheduling models for problems in network production environments. Specifically, starting from time- and inventory-related instance data, the proposed algorithms use constraint propagation techniques to calculate parameters that are used to bound the number of times subsets of tasks can be executed in a feasible solution. We also extend some of the propagation ideas to generate three classes of new tightening constraints. The proposed methods result in tightening constraints expressed in terms of assignment binary variables (Xijt=1 if task i is assigned to start on unit j at time point t) which are present in all time-indexed MIP models, therefore they are applicable to all time-indexed models accounting for a wide range of processing features. Finally, the methods are shown to lead to up to two orders of magnitude reduction in computational time when optimal solutions are found and significantly improve optimality gap when a time limit is enforced.

Original languageEnglish (US)
Pages (from-to)516-535
Number of pages20
JournalComputers and Chemical Engineering
Volume84
DOIs
StatePublished - Jan 4 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Chemical Engineering(all)
  • Computer Science Applications

Keywords

  • Constraint propagation
  • Preprocessing
  • Strong valid inequalities

Fingerprint

Dive into the research topics of 'Preprocessing and tightening methods for time-indexed MIP chemical production scheduling models'. Together they form a unique fingerprint.

Cite this