(12c) Improving Mixed Integer Linear Programming Formulations

Mixed Integer Linear Programming (MILP) formulations find their application in a wide variety of chemical as well as other engineering problems. While the application of MILP is vast, the challenges for the researchers to provide a faster solution still continue to exist. Modeling plays a crucial role on the solution efficiency of any problem. Several modeling approaches (event-based, sequence-based, slot-based etc.) do exist in the literature for MILP formulations. For a given problem, different approaches can have different performance efficiencies on the problem solution. However, relaxed MILP value is definitely a good indicator to clearly show which approach yields a tight formulation (i.e. feasible region is small). In this work, we firstly show the impact of modeling approach on MILP relaxations. Then, we discuss how reduced reformulation linearization technique (RRLT) can improve MILP formulations with big-M constraints. Finally, we propose a relaxation inequality constraint for slot-based formulations, which impacts the solution efficiency.

Sivanandam (2004) observes that the slot-based MILP model of Ku and Karimi (1987) gives a better relaxation than existing sequence-based MILP models for flow-shop problems. This observation motivates us to do the similar comparison on job-shop problems. We model the job-shop scheduling problem using slot-based approach and compare its relaxation value with that of sequence-based model (Sawaya & Grossmann, 2004). Interestingly, we find that the relaxed value of our slot-based model is better than that of sequence-based model employing convex-hull relaxation. We also compare the computational performance of both the models using a few examples.

One obvious factor that influences the solution time is the presence of the big-M constraints in the formulation. Most existing MILP formulations that employ big-M constraints do suffer from the poor relaxation (relaxed MILP), which is a notorious feature of big-M. To improve the above relaxation, Balas (1979) introduces convex hull formulation for MILP problems. Sherali and Adams (1990) propose Relaxation Linearization Technique (RLT) to generate a hierarchy of relaxations for MILP problems with the final relaxation representing the convex hull of feasible solutions. Later Sherali et al. (2000) generated reduced first-level representation via the RLT for MILPs having half the RLT constraints. In an attempt to improve the performance of big-M formulations, Sawaya and Grossmann (2004) propose cutting plane algorithms to reduce the solution space and thus increase the solution speed. In this work, we employ reduced reformulation linearization technique (RRLT) to big-M constraints of various MILP formulations. In contrary to RRLT proposed by Sherali et al. (2000), which involves multiplication with all the binaries present in the formulation, we propose a technique wherein we multiply the constraints only with the binaries present in the respective constraints. We show that RRLT can improve the computation time for big-M formulations considerably. We consider several examples from the literature to compare the performance of RRLT on big-M. Performance study includes different classes of problems such as Job-shop scheduling, flow-shop scheduling and strip packing problems. We observe that almost 50% of the solution time can be reduced by applying RRLT for some of the above problem instances.

Finally, we explore the effect of adding relaxation inequalities on slot-based MILP formulations. Although, the inequality obtained is a redundant constraint to the MILP formulation as well to the MILP relaxation, the computational results indicate that inequality generated from the relaxation is very effective and it outweighs the drawback of expanding the original model.

Reference:

(1) Balas, E., (1979). Disjunctive Programming, Discrete Optimization II, Annals of Discrete Mathematics, Vol. 5, Amsterdam: North Holland.

(2) Ku,H.-M., D.Rajagopalan and I,Karimi., Scheduling in batch processes, Chem. Eng. Prog., August,1987, 35-45.

(3) Sawaya, N.W. and Grossmann, I.A., A cutting plane method for solving linear generalized disjunctive programming problems, 2004, Online: http://egon.cheme.cmu.edu/Papers/SawayaGrossmann.pdf

(4) Sherali H. and Adams W., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), 411-430.

(5) Sherali,H., Smith J. and Adams W., Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations, discrete applied mathematics 101(2000) 247-267.

(6) Sivanandam, P.S. Scheduling of serial multiproduct batch processes. M. Eng. Thesis, National University of Singapore. 2004.