Global optimization of large‐scale mixed‐integer linear fractional programming problems: A reformulation‐linearization method and process scheduling applications

Mixed‐integer linear fractional program (MILFP) is a class of mixed‐integer nonlinear programs (MINLP) where the objective function is the ratio of two linear functions and all constraints are linear. Global optimization of large‐scale MILFPs can be computationally intractable due to the presence of discrete variables and the pseudoconvex/pseudoconcave objective function. We propose a novel and efficient reformulation–linearization method, which integrates Charnes–Cooper transformation and Glover's linearization scheme, to transform general MILFPs into their equivalent mixed‐integer linear programs (MILP), allowing MILFPs to be globally optimized effectively with MILP methods. Extensive computational studies are performed to demonstrate the efficiency of this method. To illustrate its applications, we consider two batch scheduling problems, which are modeled as MILFPs based on the continuous‐time formulations. Computational results show that the proposed approach requires significantly shorter CPU times than various general‐purpose MINLP methods and shows similar performance than the tailored parametric algorithm for solving large‐scale MILFP problems. Specifically, it performs with respect to the CPU time roughly a half of the parametric algorithm for the scheduling applications. © 2013 American Institute of Chemical Engineers AIChE J, 59: 4255–4272, 2013     

Mixed integer polynomial programming

The mixed integer polynomial programming problem is reformulated as a multi-parametric programming problem by relaxing integer variables as continuous variables and then treating them as parameters. The optimality conditions for the resulting parametric programming problem are given by a set of simultaneous parametric polynomial equations which are solved analytically to give the parametric optimal solution as a function of the relaxed integer variables. Evaluation of the parametric optimal solution for integer variables fixed at their integer values followed by screening of the evaluated solutions gives the optimal solutions.     

A superstructure‐based mixed‐integer programming approach to optimal design of pipeline network for large‐scale CO2 transport

Pipeline transport is the major means for large‐scale and long‐distance CO₂ transport in a CO₂ capture and sequestration (CCS) project. But optimal design of the pipeline network remains a challenging problem, especially when considering allocation of intermediate sites, like pump stations, and selection of pipeline routes. A superstructure‐based mixed‐integer programming approach for optimal design of the pipeline network, targeting on minimizing the overall cost in a CCS project is presented. A decomposition algorithm to solve the computational difficulty caused by the large size and nonlinear nature of a real‐life design problem is also presented. To illustrate the capability of our models. A real‐life case study in North China, with 45 emissions sources and four storage sinks, is provided. The result shows that our model and decomposition algorithm is a practical and cost‐effective method for pipeline networks design. © 2014 American Institute of Chemical Engineers AIChE J, 60: 2442–2461, 2014     

Systematic modeling of discrete‐continuous optimization models through generalized disjunctive programming

Discrete‐continuous optimization problems are commonly modeled in algebraic form as mixed‐integer linear or nonlinear programming models. Since these models can be formulated in different ways, leading either to solvable or nonsolvable problems, there is a need for a systematic modeling framework that provides a fundamental understanding on the nature of these models. This work presents a modeling framework, generalized disjunctive programming (GDP), which represents problems in terms of Boolean and continuous variables, allowing the representation of constraints as algebraic equations, disjunctions and logic propositions. An overview is provided of major research results that have emerged in this area. Basic concepts are emphasized as well as the major classes of formulations that can be derived. These are illustrated with a number of examples in the area of process systems engineering. As will be shown, GDP provides a structured way for systematically deriving mixed‐integer optimization models that exhibit strong continuous relaxations, which often translates into shorter computational times. © 2013 American Institute of Chemical Engineers AIChE J, 59: 3276–3295, 2013     

On Bayesian analysis of nonlinear continuous‐time autoregression models

Abstract. This article introduces a method for performing fully Bayesian inference for nonlinear conditional autoregressive continuous‐time models, based on a finite skeleton of observations. Our approach uses Markov chain Monte Carlo and involves imputing data from times at which observations are not made. It uses a reparameterization technique for the missing data, and because of the non‐Markovian nature of the models, it is necessary to adopt an overlapping blocks scheme for sequentially updating segments of missing data. We illustrate the methodology using both simulated data and a data set from the S & P 500 index.     

Theoretical and computational comparison of continuous‐time process scheduling models for adjustable robust optimization

Coping with uncertainty in system parameters is a prominent hurdle when scheduling multi‐purpose batch plants. In this context, our previously introduced multi‐stage adjustable robust optimization (ARO) framework has been shown to obtain more profitable solutions, while maintaining the same level of immunity against risk, as compared to traditional robust optimization approaches. This paper investigates the amenability of existing deterministic continuous‐time scheduling models to serve as the basis of this ARO framework. A comprehensive computational study is conducted that compares the numerical tractability of various models across a suite of literature benchmark instances and a wide range of uncertainty sets. This study also provides, for the first time in the open literature, robust optimal solutions to process scheduling instances that involve uncertainty in production yields. © 2018 American Institute of Chemical Engineers AIChE J, 64: 3055–3070, 2018     

Shell and tube heat exchanger design using mixed‐integer linear programming

The design of heat exchangers, especially shell and tube heat exchangers was originally proposed as a trial and error procedure where guesses of the heat transfer coefficient were made and then verified after the design was finished. This traditional approach is highly dependent of the experience of a skilled engineer and it usually results in oversizing. Later, optimization techniques were proposed for the automatic generation of the best design alternative. Among these methods, there are heuristic and stochastic approaches as well as mathematical programming. In all cases, the models are mixed integer non‐linear and non‐convex. In the case of mathematical programming solution procedures, all the solution approaches were likely to be trapped in a local optimum solution, unless global optimization is used. In addition, it is very well‐known that local solvers need good initial values or sometimes they do not even find a feasible solution. In this article, we propose to use a robust mixed integer global optimization procedure to obtain the optimal design. Our model is linear thanks to the use of standardized and discrete geometric values of the heat exchanger main mechanical components and a reformulation of integer nonlinear expressions without losing any rigor. © 2016 American Institute of Chemical Engineers AIChE J, 63: 1907–1922, 2017     

Multi‐period planning,design, and strategic models for long‐term,quality‐sensitive shale gas development

In this work we address the long‐term, quality‐sensitive shale gas development problem. This problem involves planning, design, and strategic decisions such as where, when, and how many shale gas wells to drill, where to lay out gathering pipelines, as well as which delivery agreements to arrange. Our objective is to use computational models to identify the most profitable shale gas development strategies. For this purpose we propose a large‐scale, nonconvex, mixed‐integer nonlinear programming model. We rely on generalized disjunctive programming to systematically derive the building blocks of this model. Based on a tailor‐designed solution strategy we identify near‐global solutions to the resulting large‐scale problems. Finally, we apply the proposed modeling framework to two case studies based on real data to quantify the value of optimization models for shale gas development. Our results suggest that the proposed models can increase upstream operators’ profitability by several million U.S. dollars. © 2016 American Institute of Chemical Engineers AIChE J, 62: 2296–2323, 2016     

Solving mixed integer nonlinear programming problems with line-up competition algorithm

Line-up competition algorithm (LCA), a global optimization algorithm proposed recently, is applied to the solution of mixed integer nonlinear programming (MINLP) problems. Through using alternative schemes to handle integer variables, the algorithm reported previously for solving NLP problems can be extended expediently to the solution of MINLP problems. The performance of the LCA is tested with several non-convex MINLP problems published in the literature, including the optimal design of multi-product batch chemical processes and the location-allocation problem. Testing shows that the LCA algorithm is efficient and robust in the solution of MINLP problems.     

A quadratic approximation‐based algorithm for the solution of multiparametric mixed‐integer nonlinear programming problems

An algorithm for the solution of convex multiparametric mixed‐integer nonlinear programming problems arising in process engineering problems under uncertainty is introduced. The proposed algorithm iterates between a multiparametric nonlinear programming subproblem and a mixed‐integer nonlinear programming subproblem to provide a series of parametric upper and lower bounds. The primal subproblem is formulated by fixing the integer variables and solved through a series of multiparametric quadratic programming (mp‐QP) problems based on quadratic approximations of the objective function, while the deterministic master subproblem is formulated so as to provide feasible integer solutions for the next primal subproblem. To reduce the computational effort when infeasibilities are encountered at the vertices of the critical regions (CRs) generated by the primal subproblem, a simplicial approximation approach is used to obtain CRs that are feasible at each of their vertices. The algorithm terminates when there does not exist an integer solution that is better than the one previously used by the primal problem. Through a series of examples, the proposed algorithm is compared with a multiparametric mixed‐integer outer approximation (mp‐MIOA) algorithm to demonstrate its computational advantages. © 2012 American Institute of Chemical Engineers AIChE J, 59: 483–495, 2013     

Continuous‐time modeling and global optimization approach for scheduling of crude oil operations

Scheduling of crude oil operations is a critical and complicated component of overall refinery operations, because crude oil costs account for about 80% of the refinery turnover. Moreover, blending with less expensive crudes can significantly increase profit margins. The mathematical modeling of blending different crudes in storage tanks results in many bilinear terms, which transforms the problem into a challenging, nonconvex, and mixed‐integer nonlinear programming (MINLP) optimization model. Two primary contributions have been made. First, the authors developed a novel unit‐specific event‐based continuous‐time MINLP formulation for this problem. Then they incorporated realistic operational features such as single buoy mooring (SBM), multiple jetties, multiparcel vessels, single‐parcel vessels, crude blending, brine settling, crude segregation, and multiple tanks feeding one crude distillation unit at one time and vice versa. In addition, 15 important volume‐based or weight‐based crude property indices are also considered. Second, they exploited recent advances in piecewise‐linear underestimation of bilinear terms within a branch‐and‐bound algorithm to globally optimize the MINLP problem. It is shown that the continuous‐time model results in substantially fewer bilinear terms. Several examples taken from the work of Li et al. are used to illustrate that (1) better solutions are obtained and (2) ε‐global optimality can be attained using the proposed branch‐and‐bound global optimization algorithm with piecewise‐linear underestimations of the bilinear terms. © 2011 American Institute of Chemical Engineers AIChE J, 2012     

Synthesis and optimization of membrane cascade for gas separation via mixed‐integer nonlinear programming

Currently, membrane gas separation systems enjoy widespread acceptance in industry as multistage systems are needed to achieve high recovery and high product purity simultaneously, many such configurations are possible. These designs rely on the process engineer's experience and therefore suboptimal configurations are often the result. This article proposes a systematic methodology for obtaining the optimal multistage membrane flow sheet and corresponding operating conditions. The new approach is applied to cross‐flow membrane modules that separate CO₂ from CH₄, for which the optimization of the proposed superstructure has been achieved via a mixed‐integer nonlinear programming model, with the gas processing cost as objective function. The novelty of this work resides in the large number of possible interconnections between each membrane module, the energy recovery from the high pressure outlet stream and allowing for nonisothermal conditions. The results presented in this work comprise the optimal flow sheet and operating conditions of two case studies. © 2017 American Institute of Chemical Engineers AIChE J, 63: 1989–2006, 2017     

A projection‐based method for production planning of multiproduct facilities

An algorithm is presented for identifying the projection of a scheduling model's feasible region onto the space of production targets. The projected feasible region is expressed using one of two mixed‐integer programming formulations, which can be readily used to address integrated production planning and scheduling problems that were previously intractable. Production planning is solved in combination with a surrogate model representing the region of feasible production amounts to provide optimum production targets, while a detailed scheduling is solved in a rolling‐horizon manner to define feasible schedules for meeting these targets. The proposed framework provides solutions of higher quality and yields tighter bounds than previously proposed approaches. © 2009 American Institute of Chemical Engineers AIChE J, 2009     

A general framework for process scheduling

Existing methods for process scheduling can be broadly classified as network‐based or sequential. The former are used to address problems where different batches of the same or different tasks are freely mixed or split, whereas the latter are used to address problems where batch mixing/splitting is not allowed. A framework is proposed that allows us to: (1) express scheduling problems in facilities that consist of network and sequential, as well as continuous subsystems, (2) formulate mixed‐integer programming (MIP) scheduling models for such problems, and (3) solve the resulting MIP formulations effectively. The proposed framework bridges the gap between network and sequential approaches, thereby addressing the major formulation challenge in the area of process scheduling, namely, the development of a framework that can be used to address a wide spectrum of problems. © 2010 American Institute of Chemical Engineers AIChE J, 57: 695–710, 2011     

Optimal processing network design under uncertainty for producing fuels and value‐added bioproducts from microalgae: Two‐stage adaptive robust mixed integer fractional programming model and computationally efficient solution algorithm

Fractional metrics, such as return on investment (ROI), are widely used for performance evaluation, but uncertainty in the real market may unfortunately diminish the results that are based on nominal parameters. This article addresses the optimal design of a large‐scale processing network for producing a variety of algae‐based fuels and value‐added bioproducts under uncertainty. We develop by far the most comprehensive processing network with 46,704 alternative processing pathways. Based on the superstructure, a two‐stage adaptive robust mixed integer fractional programming model is proposed to tackle the uncertainty and select the robust optimal processing pathway with the highest ROI. Since the proposed problem cannot be solved directly by any off‐the‐shelf solver, we develop an efficient tailored solution method that integrates a parametric algorithm with a column‐and‐constraint generation algorithm. The resulting robust optimal processing pathway selects biodiesel and poly‐3‐hydroxybutyrate as the final fuel and bioproduct, respectively. © 2016 American Institute of Chemical Engineers AIChE J, 63: 582–600, 2017     

Hybrid time slots sequencing model for a class of scheduling problems

This article presents a new model for the short‐term scheduling of multistage batch plants with a single unit per stage, mixed storage policies, and multiple shared resources for moving orders between stages. Automated wet‐etching stations for wafer fabrication in semiconductor plants provide the industrial context. The uncommon feature of the continuous‐time model is that it relies on time grids, as well as on global precedence sequencing variables, to find the optimal solution to the problem. Through the solution of a few test cases taken from the literature, we show that new model performs significantly better than a pure sequencing formulation and better than a closely related hybrid model with slightly different sequencing variables. We also propose a new efficient heuristic procedure for extending the range of problems that can effectively be solved, which essentially solves relaxed and constrained versions of the full‐space model. © 2011 American Institute of Chemical Engineers AIChE J, 2012     

A cutting plane method for minimizing pseudo-convex functions in the mixed integer case

In this paper, a mixed integer non linear programming (MINLP) algorithm for minimizing pseudo-convex functions under pseudo-convex constraints is proposed and illustrated. The solution procedure is iterative and relies on successive linear approximation of the objective function and on a line-search technique. The whole procedure is then embedded within the framework of a existing cutting plane method for mixed integer non-linear programs. This enables us to solve general MINLPs with pseudo-convex objective and pseudo-convex inequality constraints to global optimality.