Chen Disser (1121212), страница 24
Текст из файла (страница 24)
In each graph, we plot the quality of the best feasible schedule found with respect to the number of search iterations. Although SGPlant (ASPEN,100) is not guaranteed20000 30000Iteration40000500005000.60.560.520.48ASPENSGPlant(ASPEN,1)SGPlant(ASPEN,100,STATICP)SGPlant(ASPEN,100,DYNP)0.440.4010000c) DCAPSFigure 4.28 compares the performance of ASPEN, SGPlant (ASPEN,100), and SGPlant (ASPEN,1)20000 30000Iteration4000050000d) PREF0.860.850.840.830.82ASPENSGPlant(ASPEN,1)SGPlant(ASPEN,100,STATICP)SGPlant(ASPEN,100,DYNP)0.810.801000020000 30000Iteration4000050000e) OPTIMIZEFigure4.28:Quality-timecomparisonsofASPEN,SGPlant (ASPEN,1),SGPlant (ASPEN,100,STATICP ), and SGPlant (ASPEN,100,DYNP ).
(All runs involving SGPlantwere terminated at 24,000 iterations.)as more search time is spent. The results show that SGPlant (ASPEN,100) is able to findschedules of the same quality one to two orders faster than ASPEN and SGPlant (ASPEN,1)and much better schedules when they converge.1310.70.65b) CX1-PREF with 16 orbits0.80Experimental resultsproving on the best schedule found. In our experiments, we maintain the best schedule found100001.00planning can be much smaller than the value of N shown here.to find optimal schedules, it can find multiple locally optimal feasible schedules and keep im-80000.75a) CX1-PREF with 8 orbitsleast one unsatisfied local constraint.
Consequently, the actual number of stages used during4.2.440006000IterationBest Feasible Score (Higher is Better)40000.72Best Feasible Score (Higher is Better)Best Feasible Score (Higher is Better)SGPlant(ASPEN,N,STATICP)SGPlant(ASPEN,N,DYNP)Best Feasible Score (Higher is Better)Number of Iterations5000132Chapter 54.3SummaryWe have presented in this chapter the applications of the constraint-partitioning approachApplication on MathematicalProgramming Benchmarksto solve planning problems in PDDL2.2 domains and ASPEN domains.For PDDL2.2 domains, we have observed that the fraction of active global mutual-In this chapter, we apply the constraint partitioning approach to solve some large MINLPexclusion constraints across subproblems is very small when the constraints of a planningand CNLP benchmarks.
Based on our observation that MINLPs and CNLPs in many en-problem are partitioned by its subgoals into subproblems. We have then presented thegineering applications have highly structured constraints, we partition these problems bySGPlang planner that partitions the constraints of each PDDL2.2 planning problem by itstheir constraints into subproblems, solve each subproblem by an existing MINLP or CNLPsubgoals and uses a heuristic planner Metric-FF as the basic solver for each subproblem.
Wesolver, and resolve violated global constraints across subproblems using ESPC. Constrainthave also discussed other related techniques in SGPlang for reducing the search space andpartitioning allows many benchmark problems that cannot be solved by existing solvers tofor handling the new features in PDDL2.2. We have shown experimental improvement ofbe solvable because it leads to easier subproblems that are significant relaxations of the orig-SGPlang over existing planners on both the IPC3 and IPC4 domains, and have also analyzedinal problem.
We study various automated partitioning methods and strategies for resolvingthe time-quality trade-off of SGPlang .global constraints. We demonstrate the performance of our approach in solving some large-For ASPEN domains, we have observed temporal locality of the constraints and haveproposed to partition the constraints by the time horizon. We have then presented thescale MINLP and CNLP benchmarks and show significant improvements in time and qualityover those of existing solvers.integration of the constraint partitioning approach with the original ASPEN system.
Wehave described a global search strategy based on simulated annealing in order to resolve global5.1Problem Structure of Benchmarksinconsistencies and a dynamic partitioning strategy in order to balance the search overheadacross different subproblems. Finally, we have shown significant performance improvementin terms of planning time and solution quality in solving some ASPEN benchmarks.We have selected our MINLP benchmarks from the MacMINLP library [55], and CNLPbenchmarks from the CUTE library [13]. There are 43 MINLP problems in MacMINLP fromapplications including nuclear core reloading optimization, optimal design of multiproductbatch plant, bar space truss design, optimal marketing of a new product in a multiattributespace, determination of optimum number of trays in a distillation column, minimizing totalaverage cycle stock, trim loss minimization in paper industry, and engineering problems in133134benchmarks.
It shows a dot where a constraint (with unique ID on the x axis) is related4035to a variable (with a unique ID on the y axis). With the order of the variables and the30Variable IDVariable ID18016014012010080604020025constraints arranged properly, the figure shows a strong regular structure of the constraints.2015Based on the regular constraint structure of a problem instance, we can cluster its con-1050102030405060700-2080straints into multiple loosely coupled groups using constraint partitioning.
An example to0Constraint IDa) TRIMLON12 (MINLP)406080100Constraint IDpartition the TRIMLON12 problem into 12 subproblems by its index J is shown in Fig-b) POLGAS (MINLP)ure 1.2 in Section 1.2.1. Given a MINLP problem Pm defined in equation (1.1), the problemformulation under constraint partitioning is given in equation (3.23), which we rewrite below:100Variable ID30Variable ID40120352520151080(Pt ) :minz6040subject toJ(z)0102030405060070Constraint ID020406080100and120(5.1)h(t) (z(t)) = 0,g (t) (z(t)) ≤ 0(local constraints)H(z) = 0,G(z) ≤ 0(global constraints).205020Constraint IDc) OPTCDEG3 (CNLP)d) ORTHRGDS (CNLP)Figure 5.1: Regular structures of constraints in some MINLP and CNLP benchmarks. Adot in each graph represents a variable associated with a constraint.(t)(t)(t)(t)where h(t) = (h1 , .
. . , hmt )T and g (t) = (g1 , . . . , grt )T are local constraints; and H =(H1 , . . . , Hp )T and G = (G1 , . . . , Gq )T are global constraints.For example, the TRIMLON12 problem is partitioned into the following subproblems:machine design. The CUTE library includes more than 200 problems from many applicationsvariables:including structural design, optimal control, and engineering design.objective:variables that are picked randomly from their variable sets.
Invariably, many constraints iny[j], m[j], n[j, i], where i = 1, · · · , I, j ∈ Skminz=(y,m,n) f (z) = Jj=1 c[j] ∗ m[j] + C[j] ∗ y[j]Bmin ≤ Ii=1 (b[i] ∗ [n[i, j]) ≤ BmaxIi=1 n[i, j] − Nmax ≤ 0existing benchmarks are highly structured because they model spatial and temporal rela-y[j] − m[j] ≤ 0(C3j )tionships that have strong locality, such as those in physical structures, optimal control, andm[j] − M ∗ y[j] ≤ 0Nord[i] − Jj=1 (m[j] ∗ n[i, j]) ≤ 0.(C4j )We have observed that the constraints of many application benchmarks do not involvelocal const.:global const.:staged processing.Figure 5.1 illustrates this point by depicting the regular constraint structure of four135136(OBJj )(C1j )(C2j )(C5j )1. procedure CPOPT2.call automated partition(); // automatically partition the problem //3.γ ←− γ0 ; η ←− η0 ; // initialize penalty values for global constraints//4.repeat// outer loop //5.for t = 1 to N // iterate over all N stages to solve (3.31) in each stage //6.apply an existing solver to solve (3.31)7.call update penalty(); // update penalties of global constraints //8.end for;9.until stopping condition is satisfied10.
end procedureOut of the 72 constraints, 60 are local constraints and 12 are global constraints.The keys to the success of using constraint partitioning to solve MINLPs and CNLPs,therefore, depend on the identification of the constraint structure of a problem instance andthe efficient resolution of its violated global constraints. To this end, we study the followingissues.a) Automated analysis of the constraint structure of a problem instance and its partitioning into subproblems.
We study to analyze the strcuture of an instance specified in someFigure 5.2: CPOPT: Implementation of the partition-and-resolve framework to look forstandard form (such as AMPL [24] and GAMS). We show methods for determining the struc-CLMm of (5.1).ture of an instance after possibly reorganizing its variables and constraints, and identifying5.2.1CPOPT: the partition-and-resolve procedurethe dimension by which the constraints can be partitioned.Figure 5.2 presents CPOPT, a partition-and-resolve procedure for solving the constraintb) Optimality of the partitioning. The optimality relies on trade-offs between the numberpartitioned problem Pt in (5.1).
It first partitions the constraints into N subproblems (Lineof global constraints to be resolved and the overhead for evaluating each subproblem. We2 of Figure 5.2b, discussed in Section 5.2.2). With fixed γ and η, it then solves (3.31) definedpropose a metric for comparing various partitioning schemes and a simple and effectivein stage t using an existing solver (Line 6). To satisfy the differentiability requirement of theheuristic method for selecting the optimal partitioning according to the metric.objective function in (1.1), we transform (3.31) into the following equivalent problem withc) Resolution of violated global constraints.
We apply the theory of extended saddle pointsa differentiable objective:for resolving violated global constraints by formulating the NLPs into a penalty formulationand solving a modified subproblem with biased objective function at each partition. Weminz(t)J(z) + γ T a + η T b(5.2)develop a partition-and-resolve solver based on the general ESPC search framework proposedin Chapter 3. We study strategies for updating penalties of violated constraints in the ESPCsubject toh(t) (z(t)) = 0 and g (t) (z(t)) ≤ 0,−a ≤ H(z) ≤ a and G(z) ≤ btheory for solving MINLPs and CNLPs.where a and b are non-negative auxiliary vectors. After solving each subproblem, we increase5.2Partitioning and Resolution Strategiesthe penalties γ and η on the violated global constraints (Line 7, discussed in Section 5.2.3).In this section, we study the strategies for automated partitioning and efficient resolution ofThe process is repeated until a CLMm to (3.23) is found or when γ and η exceed theirinconsistent global constraints.maximum bounds (Line 9).137138We describe below the partitioning of the constraints and the update of the penalties.We argue that it is reasonable and effective to partition constraints by their index vectors.First, indexing is an essential mechanism in modeling languages like AMPL and GAMS for5.2.2Strategies for partitioning constraints into subproblemsrepresenting a complex problem in a compact form.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
