Comparison of global optimization algorithms for the design of water-using networks

We address a special class of bilinear process network problems with global optimization algorithms iterating between a lower bound provided by a mixed-integer linear programming (MILP) formulation and an upper bound given by the solution of the original nonlinear problem (NLP) with a local solver. Two conceptually different relaxation approaches are tested, piecewise McCormick envelopes and multiparametric disaggregation, each considered in two variants according to the choice of variables to partition/parameterize. The four complete MILP formulations are derived from disjunctive programming models followed by convex hull reformulations. The results on a set of test problems from the literature show that the algorithm relying on multiparametric disaggregation with parameterization of the concentrations is the best performer, primarily due to a logarithmic as opposed to linear increase in problem size with the number of partitions. The algorithms are also compared to the commercial solvers BARON and GloMIQO through performance profiles.     

Multi-period design and planning model of shale gas field development

Long-term design and planning of shale gas field development is challenging due to the complex development operations and a wide range of candidate locations. In this work, we focus on the multi-period shale gas field development problem, where the shale gas field has multiple formations and each well can be developed from one of several alternative pads. The decisions in this problem involve the design of the shale gas network and the planning of development operations. A mixed-integer linear programming (MILP) model is proposed to address this problem. Since the proposed model is a large-scale MILP, we propose a solution pool-based bilevel decomposition algorithm to solve it. Results on realistic instances demonstrate the value of the proposed model and the effectiveness of the proposed algorithm.     

Source-based discrete and continuous-time formulations for the crude oil pooling problem

The optimization of crude oil operations in refineries is a challenging scheduling problem due to the need to model tanks of varying composition with nonconvex bilinear terms, and complicating logistic constraints. Following recent work for multiperiod pooling problems of refined petroleum products, a source-based mixed-integer nonlinear programming formulation is proposed for discrete and continuous representations of time. Logistic constraints are modeled through Generalized Disjunctive Programming while a specialized algorithm featuring relaxations from multiparametric disaggregation handles the bilinear terms. Results over a set of test problems from the literature show that the discrete-time approach finds better solutions when minimizing cost (avoids source of bilinear terms). In contrast, solution quality is slightly better for the continuous-time formulation when maximizing gross margin. The results also show that the specialized global optimization algorithm can lead to lower optimality gaps for fixed CPU, but overall, the performance of commercial solvers BARON and GloMIQO are better.     

A new continuous-time formulation for scheduling crude oil operations

In today's competitive business climate characterized by uncertain oil markets, responding effectively and speedily to market forces, while maintaining reliable operations, is crucial to a refinery's bottom line. Optimal crude oil scheduling enables cost reduction by using cheaper crudes intelligently, minimizing crude changeovers, and avoiding ship demurrage. So far, only discrete-time formulations have stood up to the challenge of this important, nonlinear problem. A continuous-time formulation would portend numerous advantages, however, existing work in this area has just begun to scratch the surface. In this paper, we present the first complete continuous-time mixed integer linear programming (MILP) formulation for the short-term scheduling of operations in a refinery that receives crude from very large crude carriers via a high-volume single buoy mooring pipeline. This novel formulation accounts for real-world operational practices. We use an iterative algorithm to eliminate the crude composition discrepancy that has proven to be the Achilles heel for existing formulations. While it does not guarantee global optimality, the algorithm needs only MILP solutions and obtains excellent maximum-profit schedules for industrial problems with up to 7 days of scheduling horizon. We also report the first comparison of discrete- vs. continuous-time formulations for this complex problem.     

An MILP-MINLP decomposition method for the global optimization of a source based model of the multiperiod blending problem

The multiperiod blending problem involves binary variables and bilinear terms, yielding a nonconvex MINLP. In this work we present two major contributions for the global solution of the problem. The first one is an alternative formulation of the problem. This formulation makes use of redundant constraints that improve the MILP relaxation of the MINLP. The second contribution is an algorithm that decomposes the MINLP model into two levels. The first level, or master problem, is an MILP relaxation of the original MINLP. The second level, or subproblem, is a smaller MINLP in which some of the binary variables of the original problem are fixed. The results show that the new formulation can be solved faster than alternative models, and that the decomposition method can solve the problems faster than state of the art general purpose solvers.     

Optimal cyclic cleaning scheduling in heat exchanger networks under fouling

This work addresses the problem of cyclic cleaning scheduling in heat exchanger networks (HENs). A salient characteristic of this problem is that the performance of each heat exchanger decreases with time which can then be restored to its initial state by performing cleaning operations. Due to the cyclic nature of the schedule, some operations may span successive cycles (wrap-around) which should be taken into account in the mathematical models. A tight mixed integer linear programming (MILP) model is proposed minimising cleaning cost and energy requirements. A complex heat exchanger network example is presented to illustrate the applicability of the proposed model.     

A mathematical programming approach for cyclic production and cleaning scheduling of multistage continuous plants

The objective of this paper is to address the cyclic scheduling of cleaning and production operations in multiproduct multistage plants with performance decay. A mixed-integer nonlinear programming (MINLP) model based on continuous time representation is proposed that can simultaneously optimize the production and cleaning scheduling. The resulting mathematical model has a linear objective function to be maximized over a convex solution space thus allowing globally optimal solutions to be obtained with an outer approximation algorithm. Case studies demonstrate the applicability of the model and its potential benefits in comparison with a hierarchical procedure for the production and cleaning scheduling problem.     

Long-term scheduling of a single-unit multi-product continuous process to manufacture high performance glass

In this paper we address the long-term scheduling of a real world multi-product single stage continuous process for manufacturing glass. This process features long minimum run lengths, and sequence dependent changeovers of the order of days, with high transition costs. The long-term scheduling involves extended time horizons that lead to large scale mixed-integer linear programming (MILP) scheduling models. In order to address the difficulties posed by the size of the models, three different rolling horizon algorithms based on different models and time aggregation techniques are developed. The models are based on the continuous time slot MILP model, and on the traveling salesman model proposed by Erdirik-Dogan and Grossmann (2008). Due to the particular characteristics of the process under study, several new features, including minimum run lengths and changeovers across due dates, are proposed. The performance and characteristics of the proposed rolling horizon algorithms are discussed for one industrial example.     

A decomposition approach for the scheduling of a steel plant production

In this paper we present a decomposition strategy for solving large scheduling problems using mathematical programming methods. Instead of formulating one huge and unsolvable MILP problem, we propose a decomposition scheme that generates smaller programs that can often be solved to global optimality. The original problem is split into subproblems in a natural way using the special features of steel making and avoiding the need for expressing the highly complex rules as explicit constraints. We present a small illustrative example problem, and several real-world problems to demonstrate the capabilities of the proposed strategy, and the fact that the solutions typically lie within 1–3% of the global optimum.     

MILP scheduling model for multipurpose batch processes considering various intermediate storage policies

MILP (Mixed Integer Linear Programming) scheduling models for non-sequential multipurpose batch processes are presented. Operation sequences of products have to be made in each unit differently by considering production route of each product under a given intermediate storage policy to reduce idle time of units and to raise the efficiency of the process. We represent the starting and finishing time of a task in each unit with two coordinates for a given storage policy. One is based on products, and the other is based on operation sequences. Then, using binary variables and logical constraints, we match the variables used in the two coordinates into one. We suggest MILP models considering sequence dependent setup times to guarantee the optimality of the solutions. Two examples are presented to show the effectiveness of the suggested models.     

Simultaneous planning and scheduling of single-stage multi-product continuous plants with parallel lines

In this paper we present a multi-period mixed integer linear programming model for the simultaneous planning and scheduling of single-stage multi-product continuous plants with parallel units. While effective for short time horizons, the proposed scheduling model becomes computationally expensive to solve for long time horizons. In order to address this problem, we propose a bi-level decomposition algorithm in which the original problem is decomposed into an upper level planning and a lower level scheduling problem. For the representation of the upper level, we propose an MILP model which is based on a relaxation of the original model, but accounts for the effects of scheduling by incorporating sequencing constraints, which results in very tight upper bounds. In the lower level the simultaneous planning and scheduling model is solved for a subset of products predicted by the upper level. These sub-problems are solved iteratively until the upper and lower bounds converge. A number of examples are presented that show that the planning model can often obtain the optimal schedule in one single iteration.     

多产品间歇过程的分层次在线调度--一种数学规划与遗传算法的混合算法

In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.     

Generic mathematical programming formulation and solution for computer-aided molecular design

This short communication presents a generic mathematical programming formulation for computer-aided molecular design (CAMD). A given CAMD problem, based on target properties, is formulated as a mixed integer linear/non-linear program (MILP/MINLP). The mathematical programming model presented here, which is formulated as an MILP/MINLP problem, considers first-order and second-order molecular groups for molecular structure representation and property estimation. It is shown that various CAMD problems can be formulated and solved through this model.     

An MILP-based reordering algorithm for complex industrial scheduling and rescheduling

The challenging structure as well as the extensive economical potential of solving various scheduling problems has fascinated numerous researchers during the recent decades. Despite the significant progress made in the fields of operations research and process systems engineering (Puigjaner, Comp. Chem. Eng., 23 (1999): S929–S943; Shah, Proceedings of FOCAPO'98, Snowbird, Utah, USA, 1998) the complexity of many industrial-size scheduling problems means that a global optimal solution cannot be reached within a reasonable computational time. In these cases, the production schedule must be generated using e.g. some kind of sophisticated heuristics, which can often lead to suboptimal solutions. In this paper, we introduce a Mixed Integer Linear Programming (MILP) based algorithm, which can be efficiently used to improve an existing feasible, but non-optimal, production schedule or to reschedule jobs in the case of changed operational parameters. The algorithm has been successfully applied to certain scheduling problems in both the paper-converting and pharmaceutical industry.     

Composite planning and scheduling algorithm addressing intra‐period infeasibilities of gasoline blend planning models

Multi‐period planning models result in solutions which are feasible at the boundaries of the periods but may be infeasible within the periods. The composite algorithm presented here (i) solves coarse multi‐period MILP model structure for production planning; (ii) sequences operations via a genetic algorithm to minimise switching; (iii) verifies schedule feasibility via agent‐based simulation and local logical decision making; and (iv) if infeasible, re‐partitions the time horizon into multi‐periods and resolves from (i) until feasible. Application of the algorithm to gasoline blending illustrates its effectiveness in computing feasible plans and schedules for such systems. © 2012 Canadian Society for Chemical Engineering     

Optimization models for planning shale gas well refracture treatments

Refracturing is a promising option for addressing the characteristically steep decline curves of shale gas wells. In this work we propose two optimization models to address the refracturing planning problem. First, we present a continuous‐time nonlinear programming model based on a novel forecast function that predicts pre‐ and post‐treatment productivity declines. Next, we propose a discrete‐time, multi‐period mixed‐integer linear programming (MILP) model that explicitly accounts for the possibility of multiple refracture treatments over the lifespan of a well. In an attempt to reduce solution times to a minimum, we compare three alternative formulations against each other (big‐M formulation, disjunctive formulation using Standard and Compact Hull‐Reformulations) and find that the disjunctive models yield the best computational performance. Finally, we apply the proposed MILP model to two case studies to demonstrate how refracturing can increase the expected recovery of a well and improve its profitability by several hundred thousand USD. © 2016 American Institute of Chemical Engineers AIChE J, 62: 4297–4307, 2016     

A bi‐criterion optimization approach for the design and planning of hydrogen supply chains for vehicle use

In this article, we address the design of hydrogen supply chains for vehicle use with economic and environmental concerns. Given a set of available technologies to produce, store, and deliver hydrogen, the problem consists of determining the optimal design of the production‐distribution network capable of satisfying a predefined hydrogen demand. The design task is formulated as a bi‐criterion mixed‐integer linear programming (MILP) problem, which simultaneously accounts for the minimization of cost and environmental impact. The environmental impact is measured through the contribution to climate change made by the hydrogen network operation. The emissions considered in the analysis are those associated with the entire life cycle of the process, and are quantified according to the principles of Life Cycle Assessment (LCA). To expedite the search of the Pareto solutions of the problem, we introduce a bi‐level algorithm that exploits its specific structure. A case study that addresses the optimal design of the hydrogen infrastructure needed to fulfill the expected hydrogen demand in Great Britain is introduced to illustrate the capabilities of the proposed approach. © 2009 American Institute of Chemical Engineers AIChE J, 2010     

Batch selection,assignment and sequencing in multi-stage multi-product processes

The scheduling of multi-product, multi-stage batch processes is industrially important because it allows us to utilize resources that are shared among competing products in an optimal manner. Previously proposed methods consider problems where the number and size of batches is known a priori. In many instances, however, the selection and sizing (batching) of batches is or should be an optimization decision. To address this class of problems we develop a novel mixed-integer linear programming (MILP) formulation that involves three levels of discrete decisions: selection of batches, assignment of batches to units and sequencing of batches in each unit. Continuous decision variables include sizing and timing of batches. We consider various objective functions: minimization of makespan, earliness, lateness and production cost, as well as maximization of profit, an objective not addressed by previous multi-stage scheduling methods. To enhance the solution of the proposed MILP model we propose symmetry breaking constraints, develop a preprocessing algorithm for the generation of constraints that reduce the number of feasible solutions, and fix sequencing variables based upon time window information. The model enables the optimization of batch selection, assignment and sequencing decisions simultaneously and is shown to yield solutions that are better than those obtained by existing sequential optimization methods.     

Global Search Metaheuristics for planning transportation of multiple petroleum products in a multi-pipeline system

The objective of this work is to develop several metaheuristic algorithms to improve the efficiency of the MILP algorithm used for planning transportation of multiple petroleum products in a multi-pipeline system. The problem involves planning the optimal sequence of products assigned to each new package pumped through each polyduct of the network in order to meet product demands at each destination node before the end of the planning horizon. All the proposed metaheuristics are combinations of improvement methods applied to solutions resulting from different construction heuristics. These improvements are performed by searching the neighborhoods generated around the current solution by different Global Search Metaheuristics: Multi-Start Search, Variable Neighborhood Search, Taboo Search and Simulated Annealing. Numerical examples are solved in order to show the performance of these metaheuristics against a standard commercial solver using MILP. Results demonstrate how these metaheuristics are able to reach better solutions in much lower computational time.     

New approach for scheduling crude oil operations

Scheduling of crude oil operations is crucial to petroleum refining, which includes determining the times and sequences of crude oil unloading, blending, and CDU feeding. In the last decades, many approaches have been proposed for solving this problem, but they either suffered from composition discrepancy [Lee et al. 1996. Mixed-integer linear programming model for refinery short-term scheduling of crude oil unloading with inventory management. Industrial and Engineering Chemistry Research 35, 1630-1641; Jia et al., 2003. Refinery short-term scheduling using continuous time formulation: crude-oil operations. Industrial and Engineering Chemistry Research 42, 3085-3097; Jia and Ierapetritou, 2004. Efficient short-term scheduling of refinery operations based on a continuous time formulation. Computer and Chemical Engineering 28, 1001-1019] or led to infeasible solutions for some cases [Reddy et al., 2004a. Novel solution approach for optimizing crude oil operations. A.I.Ch.E. Journal 50(6), 1177-1197; 2004b. A new continuous-time formulation for scheduling crude oil operations. Chemical Engineering Science 59, 1325-1341]. In this paper, coastal and marine-access refineries with simplified workflow are considered. Unlike existing approaches, the new approach can avoid composition discrepancy without using iterative algorithm and find better solution effectively. In this approach, a new mixed integer non-linear programming (MINLP) formulation is set up for crude oil scheduling firstly, and then some heuristic rules collected from expert experience are proposed to linearize bilinear terms and prefix some binary variables in the MINLP model. Thus, crude oil scheduling can be expressed as a complete mixed integer linear programming (MILP) model with fewer binary variables. To illustrate the advantage of the new approach, four typical examples are solved with three models. The new model is compared with the most effective models (RKS(a) and RKS(b) models) presented by Reddy et al. [2004a. Novel solution approach for optimizing crude oil operations. A.I.Ch.E. Journal 50(6), 1177-1197; 2004b. A new continuous-time formulation for scheduling crude oil operations. Chemical Engineering Science 59, 1325-1341], which proves that the new approach is valid and feasible in most small-size and medium-size problems.