(301c) A Constraint Propagation Algorithm and Valid Inequalities for Chemical Production Scheduling MIP Models

Sara Zenner and Christos T. Maravelias

Department of Chemical and Biological Engineering, University of Wisconsin – Madison

1415 Engineering Dr., Madison, WI 53706, USA

In chemical production industries (e.g. pharmaceutical, food, and petroleum), processes consist of a set of tasks to produce finished goods. The equipment units used to process a task have a minimum and maximum capacity. Materials, such as feedstocks, intermediate chemicals, and final products, can be mixed together, split apart, and recycled. Each task consumes and produces materials according to a fixed recipe. Material balances enforce this recipe and keep track of the inventory for all materials.  In general, scheduling decisions include (i) how many tasks to carry out, (ii) which piece of equipment to use for each task, (iii) when to carry out each task, and (iv) how much material to process. Chemical production scheduling problems can be modeled and solved using mixed integer programming (MIP) methods.

Unfortunately, solving MIP scheduling problems for practical instances remains computationally intractable.  Previous work showed that adding valid inequalities based on material balances in lot-sizing problems results in a significantly tighter formulation (Pochet and Wolsey, 1993; Wolsey, 1997; Pochet and Wolsey, 2000; and Miller and Wolsey, 2003). However, these methods are not effective in chemical production scheduling problems due to the presence of minimum capacity constraints and recycle streams.  To address this challenge, we propose two new types of valid inequalities based on material balances and customer orders for final products.  

To construct these inequalities, we back-propagate demand for final products through the network to determine the minimum amount of each material that is needed and the minimum amount that each task must produce.  Two things make the back-propagation for chemical production processes especially challenging. First, units have minimum capacities, which means that not all values for a task’s minimum production are attainable. For example, if a task must produce at least 50kg and can take place in a single unit with a 30-40kg capacity, then the task will have to produce at least 60kg in at least two batches; we must use this improved value in the back-propagation. To account for this, we first determine the set of attainable production amounts for each task, and then, using this information, we adjust the minimum necessary amount for each material. Second, recycle loops are common in chemical industries, which makes back-propagating demand sequentially challenging. To overcome this challenge, we use a tear stream.

The demand propagation algorithm, which is run within a few seconds even for large scale process networks, provides us with a lower bound on the number of batches of each task and the amount of material that each task has to produce. These bounds are then used to formulate two types of tightening constraints. The first lower bounds the total number of times each task is run, while the second lower bounds the total production of each task.  Our constraint propagation algorithm can be applied in process networks of arbitrary structure (including networks with nested recycle loops). Also, the proposed tightening constraints can be added to any time-indexed (discrete or continuous) MIP scheduling formulation.

To illustrate the effectiveness of our methods, we present results from 36 instances using the discrete-time model of Shah et al. (1993).  Adding these inequalities reduces the average computational time for problems that are solved to optimality from 189s to 1.9s and increases the percent of problems that are solved to optimality within 30 minutes from 39% to 94%. Similar enhancements are observed for continuous-time formulations. 

Shah, N.; Pantelides, C.C.; Sargent, R.W.H. A General Algorithm for Short-Term Scheduling of Batch Operations – II. Computational Issues. Comput. Chem. Eng., 1993, 17, 229-244.

Pochet, Y.; Wolsey, L.A. Lot-Sizing with Constant Batches: Formulation and Valid Inequalities. Math. Oper. Res., 1993, 18, 767-785.

Wolsey, L.A. MIP Modelling of Changeovers in production Planning and Scheduling Problems. European Journal of Operational Research, 1997, 99, 154-165.

Miller, A.J.; Wolsey, L.A. Tight MIP Formulations for Multi-Item Discrete Lot-Sizing Problems. Op. Res., 2003, 51, 557-565.

Pochet, Y; Wolsey, L.A. Production Planning by Mixed Integer Programming. Springer, New York, 2000.