(554b) CP-Based Symmetry-Breaking Branching for Crude-Oil Operations Scheduling

Scheduling formulations often involve, depending on the objective, many symmetrical solutions. For instance, a discrete-time representation may involve symmetrical solutions when the objective value is not affected by moving a solution's task one time interval to the left (resp. to the right). Therefore, it is important to detect and circumvent the symmetry challenge and trying to solve a scheduling problem. This paper presents a methodology using a CP-based branching rule in order to eliminate irrelevant symmetric solutions from the search. The main idea is to select a representative for each set of symmetrical discrete solutions and use logic constraint propagation to restrict the branch and bound search to theses solutions.

Many representations have been used to solve various crude-oil operations problems. Lee et al. (1996) developed a discrete-formulation to solve a relaxation of a crude-oil operations problem where the composition constraints are dropped. This approach can lead to many symmetrical solutions especially when defining a large number of time intervals to improve the quality of the solution. Jia et al. (2003) and Furman et al. (2007) used the event-point representation introduced by Ierapetritou and Floudas (1998) to solve the same problem. The computational expenses reported seem to show that this type of formulation would benefit from detecting and breaking possible symmetries present in the problem.

In this paper, the multi-operations time-slots MINLP model introduced by Mouret et al. (2008a) is used. This representation consists in postulating a number of time-slots and assigning exactly one operation to each time-slot. As shown by Mouret et al. (2008b), this representation leads to many symmetrical solutions that have been identified. Linear symmetry-breaking constraints based on regular languages (Côté et al., 2007) have been added to the model reducing the computational expense by several orders of magnitude. The drawback of this approach is the large number of variables and constraints added to the model, thus increasing the solution time of the relaxation node.

The aim of this work is to further reduce the overall expense by using Constraint Programming (CP) to handle more efficiently the logic symmetry-breaking constraints. A CP model is defined including the symmetry-breaking constraint and other logic constraints involved in the problem formulation. The MILP branch and bound search is then improved by adding a constraint propagation step extending the branching decisions at each node. Similar ideas have been applied to Integer Programming models by Margot (2002) and Ostrowski (2007). The main difference here is that CP is used as the symmetry-breaking algorithm, thus benefiting from its flexible modeling capabilities.

The CP-based branching algorithm extends the branching decisions made by the MILP solver by fixing additional binary variables from the model on each branch initially created. Therefore, it is possible to use any pre-defined branching rule (using pseudo costs, most fractional variable, strong branching, branching on SOS1 variables, etc).

Computational results are presented for the four crude-oil operations problems introduced by Lee et al. (1996) showing an average 60% improvement compared to the extended MILP model presented by Mouret et al. (2008b). This is due to the low cost of constraint propagation compared to solving the node relaxation when the symmetry-breaking constraints are included in the MILP model.

[1] Lee, H., Pinto, J.M., Grossmann, I.E., and Park, S. (1996). "Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management." Ind. Eng. Chem. Res. 35(5): 1630-1641

[2] Jia, Z., Ierapetritou, M.G., and Kelly, J.D. (2003). "Refinery Short-Term Scheduling Using Continuous Time Formulation: Crude-Oil Operations." Ind. Eng. Chem. Res. 42(13): 3085-3097

[3] Furman, K.C., Jia, Z., and Ierapetritou, M.G. (2007). "A Robust Event-Based Continuous Time Formulation for Tank Transfer Scheduling." Ind. Eng. Chem. Res. 46(26): 9126-9136

[4] Ierapetritou, M.G. and Floudas, C.A. (1998). "Effective Continuous-Time Formulation for Short-Term Scheduling. 1. Multipurpose Batch Processes." Ind. Eng. Chem. Res. 37(11): 4341-4359

[5] Mouret, S., Grossmann, I.E., and Pestiaux, P. (2008) "Multi-Operations Time-Slots Model for Crude-Oil Operations Scheduling." ESCAPE 18. To appear.

[6] Mouret, S., Grossmann, I.E., and Pestiaux, P. (2008) "A Deterministic Finite Automaton Approach Generating Symmetry-Breaking Constraints for Crude-Oil Scheduling Problems." FOCAPO 2008. To appear.

[7] Côté, M.C., Gendron, B., and Rousseau, L.M. (2007). "Modeling the Regular Constraint with Integer Programming." CPAIOR 2007. LNCS 4510: 29-43

[8] Margot, F. (2002). "Pruning by Isomorphism in Branch-and-Cut." Mathematical Programming. 94(1): 71-90

[9] Ostrowski, J., Linderoth, J., Rossi, F., and Smriglio, S. (2007). "Orbital Branching." IPCO XII. LNCS 4513: 104-118