Chen Disser (1121212), страница 25
Текст из файла (страница 25)
Without it, it will be very cumbersomeOur goal in Line 2 of Figure 5.2b is to partition the constraints in such a way that minimizesto use a unique name for each variable, especially when there are thousands of variablesthe overall search time. Since the enumeration of all possible ways of partitioning is compu-and constraints. Second, index vectors in large application problems are typically associatedtationally prohibitive, we restrict our strategy to only partitioning by the index vectors ofwith physical entities. When constraints are organized and partitioned by index vectors, theirproblems modelled by the AMPL language [24].partitioning can be interpreted meaningfully. For example, index vector J in TRIMLON12corresponds to the possible cuts of paper rolls, and a subproblem partitioned by J entails theDefinition 2.
An index vector V in an AMPL model is a finite ordered array of discreteelements that are used to index variables and constraints.For example, TRIMLON12 described in Section 1.2.1 has two index vectors: I = J ={1, · · · , 12}. A variable or a constraint function can be indexed by one or more index vectors:n[i, j], i ∈ I, j ∈ J, is indexed by I and J; and (C5) is indexed by I alone.Definition 3.
A partitioning index vector (PIV) of an AMPL model is an index vector inoptimization of the paper production in each cut individually, while the overall productionis globally constrained by the client orders.Given a MINLP specified in AMPL, we present in the following our approach to automatically partition the problem by its constraints. We propose a metric to measure thequality of partitioning, present an algorithm to select the optimal PIV, illustrate trade-offsbetween the number of partitions and the overall complexity, and show an efficient heuristicfor determining the optimal number of partitions.the model for partitioning the constraints.Definition 4.
Constraint partitioning by PIV. Given a PIV of an AMPL model, an Npartition by PIV is a collection of subsets of the PIV, S1 , · · · , SN , where a) Si ∈ P IV ; b)S1 ∪ · · · ∪ SN = P IV ; and c) Si ∩ Sj = ∅ for i = j, i, j = 1..N.The constraints of a problem can be partitioned along one or more index vectors. Withmultiple index vectors, the Cartesian-product space of the PIVs is partitioned into subsets.For instance, we have shown in Section 1.2.1 the partitioning of TRIMLON12 by J intoN = 12 subproblems; that is, PIV = {J}, and S1 = {1}, · · · , S12 = {12}.
This allows allthe constraints indexed by J (C1 to C4) to be grouped into local constraints, and those notindexed by J (C5) to be the global constraints.a) Metric of partition-ability. We define Rglobal to measure the effectiveness of usingPIVs for partitioning the constraints of a problem. Since the time to solve a partitionedproblem is largely driven by the overhead in resolving its inconsistent global constraints, wedefine Rglobal to be the ratio of the number of global constraints to the total number of allconstraints.
This metric also needs to account for shared variables in multiple subproblemsthat must be consistent with each other. For simplicity, we assume each shared variable vthat appears in k subproblems to be equivalent to k − 1 global constraints, where the ithconstraint involves the consistency between the ith copy and the i + 1st copy.
Note thatthe metric is heuristic because the exact overhead depends on the difficulty of resolving theinconsistent global constraints and not on the number of global constraints.1391401ILMT(I,T)0.60.8Rglobal0.8RglobalTable 5.1: Trade-offs between N and total solution time on the SPACE-960-r problem10.40.20.6membersyielddofNsize(members,yield)0.40.2Number of partitions NTime per subproblemTime per iterationNumber of iterationsTotal time to solve problem115 60 120 240 48030 >3600 8.4 3.3 2.72.6 3.1 2.8>3600 126 99 186 336 648 1248112251 2>3600 126 99 372 672 1296 6240b) Selection of PIV. To select the best PIV that minimizes Rglobal , we observe from the1.
procedure optimal number of partitions (PIV)2.N ←− |P IV |; last time ←− ∞ ;3.repeat4.Evaluate a subproblem under N partitions, record the solution time Tp (N );5.overall time ←− Tp (N ) × N ;6.if (overall time > last time) then return (2N );7.last time ←− overall time;8.N ←− N/2 ;9.end repeat10.
end procedurebenchmarks tested that the best PIV for a problem instance is independent of the number ofFigure 5.4: An iterative algorithm to estimate the optimal number of partitions.001234567809Number of Partitions N124816 32 64 128 256 512 1024Number of Partitions Na) C-RELOAD-r-104b) SPACE-960-r (MINLP)Figure 5.3: Ratio of global constraints when partitioned by different PIVs for two MINLPs.partitions N. To illustrate this observation, Figure 5.3 plots the value of Rglobal for variousPIVs as a function of N for two benchmarks. It shows that the best PIV that minimizesRglobal is the same for all N. Based on this property, we first fix an arbitrary value of N inour implementation. As there are usually less than five index vectors in a model file, we justenumerate all possible combinations of PIVs, compute Rglobal for each case, and pick the oneor when there is no partitioning, each subproblem is large and expensive to evaluate, althoughthe global constraints will be few in number and easy to revolve.
In the other extreme, whenthere are many partitions, there will be many global constraints that are hard to resolve,although each subproblem is small and easy to evaluate.The convex relationship allows us to determine an optimal number of partitions thatthat minimizes Rglobal .c) Number of partitions. Based on the best PIV selected, we decide next the numberof partitions. Experimentally, we have observed a convex relationship between N and thetotal solution time.
We illustrate this observation in Table 5.1 for various values of N on theSPACE-960-r MINLP from the MacMINLP library [55]. It shows the average time to solvea subproblem, the total time to solve all the subproblems in one iteration, the number ofiterations needed to resolve the inconsistent global constraints, and the overall time to solvethe problem. The best N for this problem is 30.The convex relationship is intuitively reasonable. When the number of partitions is smallminimizes the overall solution time. The idea is to start with the maximum number ofpartitions in the original problem (Line 2 of Figure 5.4) and evaluate a few subproblemsthere in order to estimate Tp (N), the average time to solve a subproblem when there areN partitions (Line 4). We also evaluate overall time, the time to solve all the subproblemsonce (Line 5).
Assuming the number of iterations for resolving the global constraints to besmall, overall time will be related to the time to solve the original problem by a constantfactor. This assumption is generally true for the benchmarks tested when N is close to theoptimal value (as illustrated in Table 5.1). Next, we reduce N by half (Line 8) and repeatthe process. We stop the process when we hit the bottom of the convex curve and have141142Table 5.2: Average and standard deviation of solution time per subproblem for two bench-Hi , i = 1, · · · , p, we use ci to count the number of consecutive subproblem evaluations inmarks.which Hi is violated since the last update of ρi .
After solving a subproblem, we increase ciProblem instanceORTHRGDS ORTHRGDS SPACE-960-r SPACE-960-rNumber of partitions N10002010010Avg. time per subproblem (Tp (N))1.88.52.89.40.0210.310.0130.015Std. dev. of time per subproblemby 1 if Hi is violated; if ci reaches threshold K, which means that Hi has not been satisfiedin K consecutive subproblem evaluations, we increase ρi by:ρi ←− ρi × α,where α > 1,(5.4)found the number of partitions that leads to the minimum overall time (Line 6).The algorithm requires Tp (N), which can be estimated accurately based on the observation that it has little variations when the constraints are partitioned evenly.
Table 5.2and reset ci to 0. If Hi is satisfied, we reset ρi to ρ0 and ci to 0. In our implementation, wechoose ρ0 = 0.01, K = 3 and, α = 1.25. We update in the same manner.illustrates this observation and shows that the standard deviation of the time to evaluate aThe procedure in Figure 5.2 may generate fixed points of the 1 −penalty function insubproblem is very small for two values of N. As a result, we only evaluate one subproblem(3.15) that do not satisfy (3.16). This happens because an ESP is a local minimum of (3.15)in each iteration of Figure 5.4 in order to estimate Tp (N) (Line 4).but not the converse.
One way to escape from infeasible fixed points of (3.15) is to allowFor the SPACE-960-r example in Table 5.1, we set N as 480, 240, 120, 60, 30, 15 andperiodic decreases of γ and η (Line 7 of Figure 5.2b). The goal of these decreases is tostop at N = 15 because overall time increases from N = 30 to N = 15. We finally choose“lower” the barrier in the penalty function in order for local descents in the inner loop toN = 30. The total time to get this estimate after solving 6 subproblems is only 22.9 seconds,escape from an infeasible region.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
