We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that t...
详细信息
We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixedintegernonlinear optimization problems arises frequently in many industrial and scientific applications and this motivates the increasing interest in the study of derivative-free methods for their solution. The continuous variables are handled by a linesearch strategy whereas to tackle the discrete ones we employ a local search-type approach. We propose different algorithms which are characterized by the way the current iterate is updated and by the stationarity conditions satisfied by the limit points of the sequences they produce.
This paper presents a new and efficient approach to determine security-constrained generation scheduling (SCGS) in large-scale power systems, taking into account dispatch, network, and security constraints in pre and ...
详细信息
This paper presents a new and efficient approach to determine security-constrained generation scheduling (SCGS) in large-scale power systems, taking into account dispatch, network, and security constraints in pre and post-contingency states. A novel ramp rate limit is also modeled as a piecewise linear function in the SCGS problem to reflect more practical characteristics of the generating units. Benders decomposition is applied to this constrained solution process to obtain an optimal SCGS problem based on mixed-integer nonlinear programming (MINLP). The formulation can be embedded in two stages. First, a MIP is formulated in the master problem to solve a unit commitment (UC) problem. This stage determines appropriate on/off states of the units. The second stage, the subproblem, is formulated as a NLP to solve a security-constrained economic dispatch (SCED) problem. This stage is used to determine the feasibility of the master problem solution. It provides information to formulate the benders cuts that connect both problems. The proposed approach is tested in the IEEE 118-bus system to show its effectiveness. The simulation results are more realistic and feasible, whilst assuring an acceptable computation time. (C) 2011 Elsevier Ltd. All rights reserved.
In this paper, we addressed a multi-product unrelated parallel machines scheduling problem with the possibility of producing imperfect jobs. Rework processes in the problem are studied and a mixed-integernonlinear Pr...
详细信息
In this paper, we addressed a multi-product unrelated parallel machines scheduling problem with the possibility of producing imperfect jobs. Rework processes in the problem are studied and a mixed-integer nonlinear programming (MINLP) model to formulate this problem is proposed. Rework activities are used to upgrade imperfect jobs to a preset standard quality level. It is assumed that the defective production probability for each job on machines can be estimated through historical data acquisition. Since the problem is strongly NP-hard, exact algorithms are inefficient for medium and large-sized problems. Thus, some heuristic methods focusing on the rework processes are developed based on dispatching rules. In order to evaluate the efficiency of the presented algorithms, makespan is used as the objective function. Computational experiments show the efficacy of the modified shortest processing time (MSPT) heuristic, in terms of computational time and objective value for randomly generated test problems. (C) 2012 Sharif University of Technology. Production and hosting by Elsevier B.V. All rights reserved.
We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiven...
详细信息
We address the problem of locating new facilities of a firm or franchise that enters a market where a competitor operates existing facilities. The goal of the new entrant firm is to decide the location and attractiveness of its new facilities that maximize its profit. The competitor can react by opening new facilities, closing existing ones, and adjusting the attractiveness levels of its existing facilities, with the aim of maximizing its own profit. The demand is assumed to be aggregated at certain points in the plane and the new facilities of both the firm and the competitor can be located at predetermined candidate sites. We employ the gravity-based rule in modeling the behavior of the customers where the probability that a customer visits a certain facility is proportional to the facility attractiveness and inversely proportional to the distance between the facility site and demand point. We formulate a bilevel mixed-integer nonlinear programming model where the firm entering the market is the leader and the competitor is the follower. We propose heuristics that combine tabu search with exact solution methods. (C) 2011 Elsevier Ltd. All rights reserved.
We present numerical results of a comparative study of codes for nonlinear and nonconvex mixed-integer optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by ...
详细信息
We present numerical results of a comparative study of codes for nonlinear and nonconvex mixed-integer optimization. The underlying algorithms are based on sequential quadratic programming (SQP) with stabilization by trust-regions, linear outer approximations, and branch-and-bound techniques. The mixed-integer quadratic programming subproblems are solved by a branch-and-cut algorithm. Second order information is updated by a quasi-Newton update formula (BFGS) applied to the Lagrange function for continuous, but also for integer variables. We do not require that the model functions can be evaluated at fractional values of the integer variables. Thus, partial derivatives with respect to integer variables are replaced by descent directions obtained from function values at neighboring grid points, and the number of simulations or function evaluations, respectively, is our main performance criterion to measure the efficiency of a code. Numerical results are presented for a set of 100 academic mixed-integer test problems. Since not all of our test examples are convex, we reach the best-known solutions in about 90 % of the test runs, but at least feasible solutions in the other cases. The average number of function evaluations of the new mixed-integer SQP code is between 240 and 500 including those needed for one-or two-sided approximations of partial derivatives or descent directions, respectively. In addition, we present numerical results for a set of 55 test problems with some practical background in petroleum engineering.
Well placement and control optimization in oil field development are commonly performed in a sequential manner. In this work, we propose a joint approach that embeds well control optimization within the search for opt...
详细信息
Well placement and control optimization in oil field development are commonly performed in a sequential manner. In this work, we propose a joint approach that embeds well control optimization within the search for optimum well placement configurations. We solve for well placement using derivative-free methods based on pattern search. Control optimization is solved by sequential quadratic programming using gradients efficiently computed through adjoints. Joint optimization yields a significant increase, of up to 20% in net present value, when compared to reasonable sequential approaches. The joint approach does, however, require about an order of magnitude increase in the number of objective function evaluations compared to sequential procedures. This increase is somewhat mitigated by the parallel implementation of some of the pattern-search algorithms used in this work. Two pattern-search algorithms using eight and 20 computing cores yield speedup factors of 4.1 and 6.4, respectively. A third pattern-search procedure based on a serial evaluation of the objective function is less efficient in terms of clock time, but the optimized cost function value obtained with this scheme is marginally better.
We address the discrete network design problem (DNDP) which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the u...
详细信息
ISBN:
(纸本)9789881581419
We address the discrete network design problem (DNDP) which determines the optimal number of lanes to add to each candidate link in a road network. We formulate the problem as a bi-level programming model, where the upper level aims to minimize the total travel time via adding new lanes to candidate links and the lower level is a traditional Wardrop user equilibrium (UE) problem. We propose a global optimization method that is based on the system-optimum relaxation of the UE model. Numerical examples are given.
Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex mixed-integer nonlinear programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplis...
详细信息
Branch-and-Bound (B&B) is perhaps the most fundamental algorithm for the global solution of convex mixed-integer nonlinear programming (MINLP) problems. It is well-known that carrying out branching in a nonsimplistic manner can greatly enhance the practicality of B&B in the context of mixed-integer Linear programming (MILP). No detailed study of branching has heretofore been carried out for MINLP. In this article, we study and identify useful sophisticated branching methods for MINLP, including novel approaches based on approximations of the nonlinear relaxations by linear and quadratic programs.
Scheduling of crude oil operations is an important component of overall refinery operations, because crude oil costs account for about 80% of the refinery turnover. The mathematical modeling of blending different crud...
详细信息
Scheduling of crude oil operations is an important component of overall refinery operations, because crude oil costs account for about 80% of the refinery turnover. The mathematical modeling of blending different crudes in storage tanks results in many bilinear terms, which transform the problem into a challenging, nonconvex, mixed-integer nonlinear programming (MINLP) optimization model. In practice, uncertainties are unavoidable and include demand fluctuations, ship arrival delays, equipment malfunction, and tank unavailability. In the presence of these uncertainties, an optimal schedule generated using nominal parameter values may often be suboptimal or even become infeasible. In this article, the robust optimization framework proposed by Lin et al. and Janak et al. is extended to develop a deterministic robust counterpart optimization model for demand uncertainty. The recently proposed branch and bound global optimization algorithm with piecewise-linear underestimation of bilinear terms by Li et al. is also extended to solve the nonconvex MINLP deterministic robust counterpart optimization model and generate robust schedules. Two examples are used to illustrate the capability of the proposed robust optimization approach, and the extended branch and bound global optimization algorithm for demand uncertainty. The computational results demonstrate that the obtained schedules are robust in the presence of demand uncertainty. (C) 2011 American Institute of Chemical Engineers AIChE J, 58: 23732396, 2012
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...
详细信息
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 piecewiselinear 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) e-global optimality can be attained using the proposed branch-and-bound global optimization algorithm with piecewise-linear underestimations of the bilinear terms. (C) 2011 American Institute of Chemical Engineers AIChE J, 58: 205-226, 2012
暂无评论