Chen Disser (1121212), страница 27
Текст из файла (страница 27)
We have developedROBOT14 25.4630.5538.490.0138.490.10an automated algorithm for partitioning a large problem in order to minimize the number0.00.5638.490.0138.490.11SINROSNB 2 1SNAKE2 2---0.000.01-0.000.11SPIRAL3 20.00.71-0.000.01-0.000.11STANCMIN 3 24.250.584.250.014.250.09SVANBERG 10 1015.730.594.257.024.250.46SYNTHES1 6 60.7590.550.760.010.760.09TWOBARS 2 21.510.531.510.011.510.09WOMFLET 3 30.00.510.000.010.000.09of global constraints, an iterative method for determining the optimal number of partitionsin order to minimize the search time, and an efficient strategy for resolving inconsistentglobal constraints based on the theory of extended saddle points.
Our experimental resultsZECEVIC32 297.310.5497.310.0197.310.09ZECEVIC42 27.5580.597.560.017.560.09ZY23 22.00.462.000.012.000.09153demonstrate significant improvements over the best existing solvers in terms of solution timeand quality in solving a collection of mixed-integer and continuous nonlinear constrainedoptimization benchmarks.154Chapter 6In order to resolve violated global constraints efficiently, We further show that ESPC canbe decomposed for constraint-partitioned NLPs. We derive a set of decomposed conditionsConclusions and Future Workthat are necessary individually and sufficient collectively for constrained local minima. Sincethe decomposed ESPC is satisfied by constrained local minima in each subproblem in addition to satisfying the local constraints, it is much more effective than the local constraintsalone for limiting the search space when resolving violated global constraints.
Based onIn this chapter, we conclude our research on constraint partitioning using the theory ofextended saddle points and points out some possible future directions.the decomposed ESPC, we propose a general partition-and-resolve framework that iteratesbetween calling a basic solver to solve a modified subproblem while incorporating the local constraints and the bias on violated global constraints, and using a penalty-reweighting6.1Summary of Workstrategy to resolve the violated global constraints across the subproblems.In this thesis, we have proposed a general approach of constraint partitioning to significantlyWe have applied constraint partitioning to solve some planning and mathematical pro-reduce the computational complexity in solving constrained nonlinear optimization problemsgramming benchmarks originated from engineering applications.
We have studied importantin discrete, continuous, and mixed spaces. This approach is based on the observationsimplementation issues in making the constraint partitioning approach efficient for these ap-that most NLPs from real-world applications have structured constraints that are highlyplications, including automated methods in deciding partitioning dimensions, strategies inlocalized, and that exploiting the constraint structure by partitioning can lead to muchchoosing the optimal number of partitions, selection and adaptation of existing solvers forrelaxed subproblems that are easy to solve and are loosely coupled.solving subproblems efficiently, and strategies for updating penalty values in resolving vio-The constraint partitioning approach leads to global constraints that many be inconsis-lated global constraints quickly.
For both applications, our proposed method has achievedtent across multiple subproblems. We have proposed a unified theory of extended saddle-significant reduction in solution time, and has solved many large problems not solvable bypoint condition (ESPC) for solving discrete, continuous, and mixed NLPs. This work extendsother start-of-the-art solvers.the previous work on ESPC for discrete NLPs, developed by Wah and Wu [91, 98], to a unified theory that works in discrete, continuous, and mixed spaces. Based on an 1 −penaltyformulation, our theory provides a necessary and sufficient condition that governs all constrained local minima.
The result shows that each constrained local minimum is associatedwith a saddle point of the corresponding unconstrained 1 -penalty function when penalties6.2Future WorkIn this thesis, we have shown that the constraint partitioning approach can significantly reduce the search complexity by improving over existing solvers on planning and mathematicalprogramming applications. We point out two possible ways to extend this research.are sufficiently large.1551561) We plan to continue the study of the constraint partitioning approach for nonlinearoptimization on other applications, including computational biology, VLSI circuit design,computer vision and optimal control.
Many applications have intrinsic structural proper-Referencesties that can be exploited to make the search more efficient than general solution methods.Existing methods either do not utilize the structural information of applications (such assequential quadratic programming), or require user-supplied domain-specific knowledge onproblem structure (such as methods for circuit layouts).
There is a lack of methods that auto-[1] E. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines. J. Wiley andSons, 1989.matically utilize problem structures, such as the structural relations between constraints and[2] S. Anily and A. Federgruen. Ergodicity in parametric nonstationary Markov chains: Anvariables. It is desirable to design automated methods to exploit these problem structuresapplication to simulated annealing methods. Operations Research, 35(6):867–874, 1987.using an application-oriented approach, and develop theoretical results on search complex-[3] S. Anily and A Federgruen. Simulated annealing methods with general acceptanceity.
Future research in this direction will improve the efficiency of nonlinear optimizationmethods and bridge the gap between optimization theory and practical applications.2) The planning technology based on constraint partitioning has been proved very effective on the PDDL2.2 and the ASPEN models. We plan to study other important planningapplications, such as spacecraft control and production planning, investigate the structureof these applications, and propose suitable schemes to exploit their structure to improve theprobabilities.
Journal of Appl. Prob., 24:657–667, 1987.[4] M. Avriel. Nonlinear Programming: Analysis and Methods. Prentice-Hall, Inc., Englewood Cliffs, NJ., 1976.[5] T. Back, F. Hoffmeister, and H.-P. Schwefel. A survey of evolution strategies. InProceedings of the 4th International Conference on Genetic Algorithms, pages 2–9, 1991.[6] T. Back, F. Hoffmeister, and H. P. Schwefel. A survey of evolution strategies.
In Proc.of 4th Int’l Conf. on Genetic Algorithms, pages 2–9, 1991.search efficiency. Moreover, we plan to extend the proposed approach to more expressiveAI modelling languages and to probabilistic planning and scheduling where there are uncertainties in the environments and outcomes of actions. In a broader scope, we plan to extendour planning technology and mathematical programming approach to other related subjectsin artificial intelligence, including motion planning, robot planning, machine learning, and[7] M. S.
Bazaraa and J. J. Goode. A survey of various tactics for generating Lagrangianmultipliers in the context of Lagrangian duality. European Journal of Operational Research, 3:322–338, 1979.[8] J. C. Bean and A. B. Hadj-Alouane. A dual genetic algorithm for bounded integerprograms. In Technical Report TR 92-53, Department of Industrial and OperationsEngineering, The University of Michigan, 1992.multi-agent systems.[9] D. P.
Bertsekas. Constrained Optimization and Lagrange Multiplier Methods. AcademicPress, 1982.[10] D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, Massachusetts,1999.157158[11] A. L. Blum and M. L. Furst. Fast planning through planning graph analysis. ArtificialIntelligence, 90:281–300, 1997.[22] S. Edelkamp. Pddl2.2 planning in the model checking integrated environment. In UKPlanning and Scheduling Special Interest Group (PlanSig). Glasgow, 2003.[12] B.
Bonet and H. Geffner. Planning as heuristic search. Artificial Intelligence, Specialissue on Heuristic Search, 129(1), 2001.[13] I. Bongartz, A. R. Conn, N. Gould, and P. L. Toint. CUTE: Constrained and unconstrained testing environment. ACM Trans. on Mathematical Software, 21(1):123–160,[23] S. Edelkamp and J. Hoffmann. Classical part, 4th international planning competition.http://ls5-www.cs.uni-dortmund.de/~edelkamp/ipc-4/, 2004.[24] R. Fourer, D. M. Gay, and B. W.
Kernighan. AMPL: A Modeling Language for Mathematical Programming. Brooks Cole Publishing Company, 2002.1995.[25] M. P. Fourman. Propositional planning. In Proc. Workshop on Model Theoretic Ap[14] Y. X. Chen. Optimal Anytime Search for Constrained Nonlinear Programming. M.Sc.proaches to Planning. AIPS, 2000.Thesis, Dept. of Computer Science, Univ. of Illinois, Urbana, IL, May 2001.[26] M.
I. Freidlin and A. D. Wentzell. Random perturbations of dynamical systems. New[15] Y. X. Chen and B. W. Wah. Automated planning and scheduling using calculus ofYork : Springer, 1984, 1984.variations in discrete space. In Proc. Int’l Conf. on Automated Planning and Scheduling,[27] B. Gavish. On obtaining the ‘best’ multilpliers for a Lagrangean relaxation for integerpages 2–11, June 2003.programming. Comput. & Ops.
Res., 5:55–71, 1978.[16] S. Chien, et al. ASPEN - Automating space mission operations using automated planning and scheduling. In Proc. SpaceOps. Space Operations Organization, 2000.[28] A. M. Geoffrion. Generalized Benders decomposition. J. Optim. Theory and Appl.,10(4):237–241, 1972.[17] A. R. Conn, N. Gould, and Ph. L.
Toint. Numerical experiments with the LANCELOTpackage (Release A) for large-scale nonlinear optimization. Mathematical Programming,[29] A. M. Geoffrion. Lagrangian relaxation for integer programming. Mathematical Programming Study, 2:82–114, 1974.73:73–110, 1996.[18] G.
B. Dantzig and P. Wolfe. Decomposition principle for linear programming. Operations[30] A. Gerevini and I. Serina. LPG: a planner based on local search for planning graphswith action costs. In Proc. of the Sixth Int. Conf. on AI Planning and Scheduling, pagesResearch, 8:101–111, 1960.12–22. Morgan Kaufman, 2002.[19] P. Doherty and J. Kvarnstrm. TALplanner: An empirical investigation of a temporallogic-based forward chaining planner. In Proc. Sixth Int’l Workshop on Temporal Logicbased Forward Chaining Planner, pages 47–54. AIPS, 1999.[20] M. A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
