共查询到20条相似文献,搜索用时 421 毫秒
1.
A neural-network-based iterative GDHP approach for solving a class of nonlinear optimal control problems with control constraints 总被引:2,自引:1,他引:1
Ding Wang Derong Liu Dongbin Zhao Yuzhu Huang Dehua Zhang 《Neural computing & applications》2013,22(2):219-227
In this paper, a novel neural-network-based iterative adaptive dynamic programming (ADP) algorithm is proposed. It aims at solving the optimal control problem of a class of nonlinear discrete-time systems with control constraints. By introducing a generalized nonquadratic functional, the iterative ADP algorithm through globalized dual heuristic programming technique is developed to design optimal controller with convergence analysis. Three neural networks are constructed as parametric structures to facilitate the implementation of the iterative algorithm. They are used for approximating at each iteration the cost function, the optimal control law, and the controlled nonlinear discrete-time system, respectively. A simulation example is also provided to verify the effectiveness of the control scheme in solving the constrained optimal control problem. 相似文献
2.
《Journal of Process Control》2014,24(5):531-541
The operating point of a typical chemical process is determined by solving a non-linear optimization problem where the objective is to minimize an economic cost subject to constraints. Often, some or all of the constraints at the optimal solution are active, i.e., the solution is constrained. Though it is profitable to operate at the constrained optimal point, it might lead to infeasible operation due to uncertainties. Hence, industries try to operate the plant close to the optimal point by “backing-off” to achieve the desired economic benefits. Therefore, the primary focus of this paper is to present an optimization formulation for solving the dynamic back-off problem based on an economic cost function. In this regard, we work within a stochastic framework that ensures feasible dynamic operating region within the prescribed confidence limit. In this work, we aim to reduce the economic loss due to the back-off by simultaneously solving for the operating point and a compatible controller that ensures feasibility. Since the resulting formulation is non-linear and non-convex, we propose a novel two-stage iterative solution procedure such that a convex problem is solved at each step in the iteration. Finally, the proposed approach is demonstrated using case studies. 相似文献
3.
This paper considers the design of two-layered fully interconnected networks. A two-layered network consists of clusters of nodes, each defining an access network and a backbone network. We consider the integrated problem of determining the access networks and the backbone network simultaneously. A mathematical formulation is presented, but as the linear programming relaxation of the mathematical formulation is weak, a formulation based on the set partitioning model and column generation approach is also developed. The column generation subproblems are solved by solving a series of quadratic knapsack problems. We obtain superior bounds using the column generation approach than with the linear programming relaxation. The column generation method is therefore developed into an exact approach using the branch-and-price framework. With this approach we are able to solve problems consisting of up to 25 nodes in reasonable time. Given the difficulty of the problem, the results are encouraging. 相似文献
4.
《国际计算机数学杂志》2012,89(6):1329-1350
In this work, three stabilized finite volume iterative schemes for the stationary Navier–Stokes equations are considered. Under the finite volume discretization at each iterative step, the iterative scheme I consists in solving the steady Stokes problem, iterative scheme II consists in solving the stationary linearized Navier–Stokes equations and iterative scheme III consists in solving the steady Oseen equations, respectively. We discuss the stabilities and convergence of three iterative methods. The iterative schemes I and II are stable and convergent under some strong uniqueness conditions, while iterative scheme III is unconditionally stable and convergent under the uniqueness condition. Finally, some numerical results are presented to verify the performance of these iterative schemes. 相似文献
5.
An Efficient Numerical Scheme for Solving Multi‐Dimensional Fractional Optimal Control Problems With a Quadratic Performance Index 下载免费PDF全文
A. H. Bhrawy E. H. Doha J. A. Tenreiro Machado S. S. Ezz‐Eldien 《Asian journal of control》2015,17(6):2389-2402
The shifted Legendre orthogonal polynomials are used for the numerical solution of a new formulation for the multi‐dimensional fractional optimal control problem (M‐DFOCP) with a quadratic performance index. The fractional derivatives are described in the Caputo sense. The Lagrange multiplier method for the constrained extremum and the operational matrix of fractional integrals are used together with the help of the properties of the shifted Legendre orthonormal polynomials. The method reduces the M‐DFOCP to a simpler problem that consists of solving a system of algebraic equations. For confirming the efficiency and accuracy of the proposed scheme, some test problems are implemented with their approximate solutions. 相似文献
6.
Anirban Basudhar Christoph Dribusch Sylvain Lacaze Samy Missoum 《Structural and Multidisciplinary Optimization》2012,46(2):201-221
This paper presents a methodology for constrained efficient global optimization (EGO) using support vector machines (SVMs). While the objective function is approximated using Kriging, as in the original EGO formulation, the boundary of the feasible domain is approximated explicitly as a function of the design variables using an SVM. Because SVM is a classification approach and does not involve response approximations, this approach alleviates issues due to discontinuous or binary responses. More importantly, several constraints, even correlated, can be represented using one unique SVM, thus considerably simplifying constrained problems. In order to account for constraints, this paper introduces an SVM-based ??probability of feasibility?? using a new Probabilistic SVM model. The proposed optimization scheme is constituted of two levels. In a first stage, a global search for the optimal solution is performed based on the ??expected improvement?? of the objective function and the probability of feasibility. In a second stage, the SVM boundary is locally refined using an adaptive sampling scheme. An unconstrained and a constrained formulation of the optimization problem are presented and compared. Several analytical examples are used to test the formulations. In particular, a problem with 99 constraints and an aeroelasticity problem with binary output are presented. Overall, the results indicate that the constrained formulation is more robust and efficient. 相似文献
7.
Dung-Ying Lin Ampol Karoonsoontawong S. Travis Waller 《Networks and Spatial Economics》2011,11(1):101-126
We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the
Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem
is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission
network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing
combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary
slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are
then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping
criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability
of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed
scheme can be extended to solve multi-destination problems as well. 相似文献
8.
This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices. 相似文献
9.
K. S. Hindi 《Computers & Industrial Engineering》1995,28(4):709-719
The problem of multi-item, single-level, dynamic lotsizing in the presence of a single capacitated resource is addressed. A model based on variable redefinition is developed leading to a solution strategy based on a branch-and-bound search with sharp low bounds. The multi-item low bound problems are solved by column generation with the capacity constraints as the linking constraints. The resulting subproblems separate into as many single-item, uncapacitated lotsizing problems as there are items. These subproblems are solved as shortest-path problems. Good upper bounds are also generated by solving an appropriate minimum-cost network flow problem at each node of the branch-and-bound tree. The resulting solution scheme is very efficient in terms of computation time. Its efficiency is demonstrated by computational testing on a ste of benchmark problem instances and is attributable to the sharpness of the lower bounds, the efficiency with which the low bound problems are solved and the frequent generation of good upper bounds; all of which leading to a high exclusion rate. 相似文献
10.
A solution approach for log truck scheduling based on composite pricing and branch and bound 总被引:2,自引:0,他引:2
Myrna Palmgren Mikael Rönnqvist Peter Värbrand 《International Transactions in Operational Research》2003,10(5):433-447
The logging truck scheduling problem is one of the most complex routing problems where both pick‐up and delivery operations are included. It consists in finding one feasible route for each vehicle in order to satisfy the demands of the customers and in such a way that the total transport cost is minimized. We use a mathematical formulation of the log truck scheduling problem where each column represents a feasible route. We generate a large pool of columns based on solving a transportation problem. Then we apply a composite pricing algorithm, which mainly consists of pricing the pool of columns and maintain an active set of these, for solving the LP relaxed model. A branch and price approach is used to obtain integer solutions in which we apply composite pricing to generate new columns. Numerical results from case studies at Swedish forestry companies are presented. 相似文献
11.
Neural-Network-Based Near-Optimal Control for a Class of Discrete-Time Affine Nonlinear Systems With Control Constraints 总被引:6,自引:0,他引:6
Huaguang Zhang Yanhong Luo Derong Liu 《Neural Networks, IEEE Transactions on》2009,20(9):1490-1503
In this paper, the near-optimal control problem for a class of nonlinear discrete-time systems with control constraints is solved by iterative adaptive dynamic programming algorithm. First, a novel nonquadratic performance functional is introduced to overcome the control constraints, and then an iterative adaptive dynamic programming algorithm is developed to solve the optimal feedback control problem of the original constrained system with convergence analysis. In the present control scheme, there are three neural networks used as parametric structures for facilitating the implementation of the iterative algorithm. Two examples are given to demonstrate the convergence and feasibility of the proposed optimal control scheme. 相似文献
12.
D. Bredström K. Jörnsten M. Rönnqvist M. Bouchard 《International Transactions in Operational Research》2014,21(2):177-197
In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation. 相似文献
13.
《Computers & Operations Research》2005,32(8):2095-2116
There is a growing interest in the applications of the constrained multi-product newsboy problem. In this paper, we develop a methodology to examine the dual of the solution space of this type of problem with two constraints and propose an approach to obtain the optimum batch size of each product. The approach is based on utilizing the Lagrangian Multipliers, Leibniz Rule, Kuhn–Tucker conditions, and when necessary it engages them into iterative techniques to obtain the optimum or near optimum solution values. Among the important features of the developed approach is its applicability to general probability distribution functions of products’ demands. Also, it can be utilized in cases when the constraints are so tight, hence allowing the decision-maker to either delete some of the products from the original list or increase the available resources. The paper shows how the parametric functions that envelope the dual solution space are developed and includes numerical examples to illustrate the application of the proposed approach. 相似文献
14.
Miguel A. Otaduy Rasmus Tamstorf Denis Steinemann Markus Gross 《Computer Graphics Forum》2009,28(2):559-568
We present an algorithm for robust and efficient contact handling of deformable objects. By being aware of the internal dynamics of the colliding objects, our algorithm provides smooth rolling and sliding, stable stacking, robust impact handling, and seamless coupling of heterogeneous objects, all in a unified manner. We achieve dynamicsawareness through a constrained dynamics formulation with implicit complementarity constraints, and we present two major contributions that enable an efficient solution of the constrained dynamics problem: a time stepping algorithm that robustly ensures non-penetration and progressively refines the formulation of constrained dynamics, and a new solver for large mixed linear complementarity problems, based on iterative constraint anticipation. We show the application of our algorithm in challenging scenarios such as multi-layered cloth moving at high velocities, or colliding deformable solids simulated with large time steps. 相似文献
15.
We present an exact algorithm for solving the channel assignment problem in cellular telephony networks. This problem consists of assigning sets of channels to the network cells in such a way that the channel demand is satisfied, while avoiding co-channel interference and adjacent channel interference and respecting the channel spacing constraint for each antenna. In a previous article [Jaumard B, Marcotte O, Meyer C, Vovor T. Comparison of column generation models for channel assignment in cellular networks. Discrete Applied Mathematics 2002; 118:299–322], we formulated this problem as a covering problem in two different ways and compared these two formulations and another formulation both from a theoretical and computational point of view (by solving their linear relaxations). In the present article we focus on the best set covering formulation, where the subsets are sets of cells that can be assigned the same channel, and we actually solve two versions of the integer program. In the first version, we seek to minimize the unmet demand, while in the second, we seek to minimize the overall interference while assigning the required number of channels to each cell. In either version, the integer program is solved by an algorithm combining the column generation technique and a branch-and-cut scheme. Finally, we present the solutions produced by these algorithms for some instances of European networks and real-life instances supplied by the Bell Mobilité company. 相似文献
16.
A crew pairing is a sequence of flights, connections and rests that starts and ends at a crew base and is assigned to a single crew. The crew pairing problem consists of determining a minimum cost set of feasible crew pairings such that each flight is covered exactly once and side constraints are satisfied. Traditionally, this problem has been solved in the industry by a heuristic three-phase approach that solves sequentially a daily, a weekly, and a monthly problem. This approach prohibits or strongly penalizes the repetition of the same flight number in a pairing. In this paper, we highlight two weaknesses of the three-phase approach and propose alternative solution approaches that exploit flight number repetitions in pairings. First, when the flight schedule is irregular, we show that better quality solutions can be obtained in less computational time if the first two phases are skipped and the monthly problem is solved directly using a rolling horizon approach based on column generation. Second, for completely regular flight schedules, we show that better quality solutions can be derived by skipping the daily problem phase and solving the weekly problem directly. 相似文献
17.
18.
We examine methods for constructing regression ensembles based on a linear program (LP). The ensemble regression function consists of linear combinations of base hypotheses generated by some boosting-type base learning algorithm. Unlike the classification case, for regression the set of possible hypotheses producible by the base learning algorithm may be infinite. We explicitly tackle the issue of how to define and solve ensemble regression when the hypothesis space is infinite. Our approach is based on a semi-infinite linear program that has an infinite number of constraints and a finite number of variables. We show that the regression problem is well posed for infinite hypothesis spaces in both the primal and dual spaces. Most importantly, we prove there exists an optimal solution to the infinite hypothesis space problem consisting of a finite number of hypothesis. We propose two algorithms for solving the infinite and finite hypothesis problems. One uses a column generation simplex-type algorithm and the other adopts an exponential barrier approach. Furthermore, we give sufficient conditions for the base learning algorithm and the hypothesis set to be used for infinite regression ensembles. Computational results show that these methods are extremely promising. 相似文献
19.
Dmitri A. Dolgov Edmund H. Durfee 《Annals of Mathematics and Artificial Intelligence》2006,47(3-4):273-293
A weakness of classical Markov decision processes (MDPs) is that they scale very poorly due to the flat state-space representation.
Factored MDPs address this representational problem by exploiting problem structure to specify the transition and reward functions
of an MDP in a compact manner. However, in general, solutions to factored MDPs do not retain the structure and compactness
of the problem representation, forcing approximate solutions, with approximate linear programming (ALP) emerging as a promising
MDP-approximation technique. To date, most ALP work has focused on the primal-LP formulation, while the dual LP, which forms
the basis for solving constrained Markov problems, has received much less attention. We show that a straightforward linear
approximation of the dual optimization variables is problematic, because some of the required computations cannot be carried
out efficiently. Nonetheless, we develop a composite approach that symmetrically approximates the primal and dual optimization
variables (effectively approximating both the objective function and the feasible region of the LP), leading to a formulation
that is computationally feasible and suitable for solving constrained MDPs. We empirically show that this new ALP formulation
also performs well on unconstrained problems.
相似文献
20.
The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results. 相似文献