The problem of selecting processes and capacity expansion policies for a chemical complex can be formulated as a multiperiod, mixed-integer linear program (MILP). This MILP can be reformulated by exploiting lot sizing substructures. The reformulation produces a tight linear programming relaxation but also introduces a large number of variables and constraints. To avoid unnecessary additional variables and constraints, a polyhedral approach is developed. The reformulation variables are projected out giving rise to a larger constraint system. The new model is solved using a strong cutting plane approach. The separation problem is solved exactly in polynomial time. Computational experiments are performed to compare the conventional MILP formulation with the nonconventional formulations after variable disaggregation and projection. It is found that only a few of the constraints of the projection model suffice to substantially reduce the relaxation gap of the conventional model. This property leads to more robust and faster solution algorithms for large scale problems. Computational results are presented for planning problems with up to 38 processes, 25 products and 8 time periods. The corresponding MILPs included up to 300 binary variables and a few thousand continuous variables and constraints.
ASJC Scopus subject areas
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research