(************** Content-type: application/mathematica ************** Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 41575, 1153]*) (*NotebookOutlinePosition[ 67459, 1994]*) (* CellTagsIndexPosition[ 67415, 1990]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[{ "Discrete Optimization using ", StyleBox["Mathematica", FontSlant->"Italic"] }], "Title"], Cell["Daniel Lichtblau", "Author"], Cell["\<\ Wolfram Research, Inc., 100 Trade Centre Dr., Champaign, Illinois \ 61820 (USA) danl@wolfram.com\ \>", "Address"], Cell[CellGroupData[{ Cell["Abstract", "Section"], Cell[TextData[{ " Many important classes of optimization problems are discrete in \ nature. Examples are the standard problems of integer programming (including \ the ever important \"knapsack problems\"), permutation assignment problems \ (e.g., the notorious \"traveling salesman problem\"), set coverings, set \ partitioning, and so on. Problems of practical interest are frequently too \ large to be solved by brute force enumeration techniques. Hence there is a \ need for more refined methods that use various tactics for sampling and \ searching the domain in pursuit of optimal solutions.\n Version 4.2 of ", StyleBox["Mathematica", FontSlant->"Italic"], " has a flexible package for performing global optimization. It includes \ powerful functionality from the category of evolutionary programming. Ways to \ apply this technology to various problems in discrete optimization will be \ discussed. We will present details of how to code problems so that built\ \[Hyphen]in ", StyleBox["Mathematica", FontSlant->"Italic"], " functions can digest them and will illustrate with a variety of examples. \ We will also discuss some practical tuning considerations.\n\n ", StyleBox["Keywords", FontWeight->"Bold"], ": evolutionary algorithms, discrete optimization, set partitioning, subset \ covering, quadratic assignment problem." }], "Abstract"] }, Open ]], Cell[CellGroupData[{ Cell["Introduction", "Section"], Cell[TextData[{ "Optimization problems that involve discrete parameters are quite common. \ Examples include task assignments, knapsack problems, and so forth. In ", StyleBox["Mathematica", FontSlant->"Italic"], " we now have some powerful global optimization technology, described in \ [1], and contained in a function called ", Cell[BoxData[ \(NMinimize\)]], ". Among its features is a method from the family of evolutionary \ algorithms (see [2] for a broad discussion of these) based on the \ \"differential evolution\" method presented in [6]. That method was designed \ primarily for continuous optimization problems. It differs from standard \ \"genetic\" methods in that vector elements take on values in a continuum; \ this was motivated by a need to represent continuous variables in a way that \ discrete\[Hyphen]valued genes cannot readily do. In other respects, e.g. \ mutation and mating, this method resembles a genetic algorithm." }], "Text"], Cell["\<\ It turns out that differential evolution is a powerful tool for \ handling constrained optimization, stochastic problems (see [1] for an \ example), and, of all things, discrete optimization. In this paper we \ demonstrate with several examples how one might attack discrete problems. It \ must be stated that these methods are heuristic. We generally do not know \ that the results returned are optimal (unless shown to be so by other means). \ What we claim is that the methods to be presented are practical ways to get \ \"near\" optimal results without resorting to problem\[Hyphen]specific \ software.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Acknowledgements", "Section"], Cell[TextData[{ "Much of the", StyleBox[" ", "Input", FontSize->14], Cell[BoxData[ \(NMinimize\)]], " code on which this paper rests was developed by Sergei Shebalov (summer \ intern at Wolfram Research, Inc., 1999, 2000) and Brett Champion of Wolfram \ Research, Inc." }], "Text"], Cell[TextData[{ "There is a discussion of the technology behind ", Cell[BoxData[ \(NMinimize\)]], " in Brett Champion's paper for this conference [1]. The primary focus \ there is to describe the general technology and provide examples of \ continuous optimization problems." }], "Text"], Cell[TextData[{ "All timings indicated below are for a 1.4 GHz machine running a \ development ", StyleBox["Mathematica ", FontSlant->"Italic"], "kernel under the Linux operating system (", StyleBox["Mathematica", FontSlant->"Italic"], " (TM) is a registered trademark of Wolfram Research, Incorporated [7]). \ Many of these examples were also presented in [3]." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Initialization", "Section"], Cell[TextData[{ "We begin by loading the add\[Hyphen]on package that has the ", Cell[BoxData[ \(NMinimize\)]], " function." }], "Text"], Cell[BoxData[{ \(\(Needs["\"];\)\), "\[IndentingNewLine]", \(\(Off[General::spell, \ General::spell1];\)\)}], "Input", CellLabel->"In[1]:="], Cell["\<\ In order to do discrete optimizations effectively we will disable \ various mechanisms that are in place to determince \"convergence\". This will \ force the program to work for the full specified maximum iterations.\ \>", \ "Text"], Cell[BoxData[ \(\(SetOptions[NMinimize, AccuracyGoal \[Rule] Infinity, PrecisionGoal \[Rule] Infinity, Compiled \[Rule] False];\)\)], "Input",\ CellLabel->"In[3]:="] }, Open ]], Cell[CellGroupData[{ Cell["A simple example", "Section"], Cell[TextData[{ "We start with a basic coin problem. We are given ", Cell[BoxData[ \(143267\)]], " coins in pennies, nickels, dimes, and quarters, of total value $12563.29, \ and we are to determine how many coins might be of each type. There are \ several ways one might set up such a problem in ", Cell[BoxData[ \(NMinimize\)]], ". We will try to minimize the sum of squares of differences between actual \ values and desired values of the two linear expressions implied by the \ information above. For our search space we will impose obvious range \ constraints on the various coin types. We will want to alter the seeding of \ the random number generator (this changes the random initial parameters used \ to seed the optimization code) so we specify the method with this option \ added. We will do ", Cell[BoxData[ \(10\)]], " runs of this." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[ Table[{min, sol} = NMinimize[{\((p + 5\ n + 10\ d + 25\ q - 1256329)\)\^2 + \((p + n + \ d + q - 143267)\)\^2, {p, n, d, q} \[Element] Integers, 0 <= p <= 1256329, 0 <= n <= 1256329/5, 0 <= d <= 1256329/10, 0 <= q <= 1256329/25}, {p, n, d, q}, MaxIterations -> 1000, Method -> {DifferentialEvolution, RandomSeed -> Random[Integer, 1000]}], {10}]]\)], "Input"], Cell[BoxData[ \({223.53\ Second, {{0. , {d \[Rule] 6362, n \[Rule] 50489, p \[Rule] 50839, q \[Rule] 35577}}, {0. , {d \[Rule] 43218, n \[Rule] 57917, p \[Rule] 21614, q \[Rule] 20518}}, {0. , {d \[Rule] 99194, n \[Rule] 38267, p \[Rule] 3004, q \[Rule] 2802}}, {0. , {d \[Rule] 45794, n \[Rule] 43001, p \[Rule] 32434, q \[Rule] 22038}}, {0. , {d \[Rule] 40522, n \[Rule] 67331, p \[Rule] 15454, q \[Rule] 19960}}, {0. , {d \[Rule] 51018, n \[Rule] 40919, p \[Rule] 30904, q \[Rule] 20426}}, {0. , {d \[Rule] 34674, n \[Rule] 62009, p \[Rule] 23544, q \[Rule] 23040}}, {0. , {d \[Rule] 78822, n \[Rule] 22550, p \[Rule] 28834, q \[Rule] 13061}}, {0. , {d \[Rule] 65434, n \[Rule] 22865, p \[Rule] 36939, q \[Rule] 18029}}, {0. , {d \[Rule] 54378, n \[Rule] 38981, p \[Rule] 30419, q \[Rule] 19489}}}}\)], "Output"] }, Open ]], Cell[TextData[{ "We obtained valid solutions each time. Using only, say, ", Cell[BoxData[ \(400\)]], " iterations we tend to get solutions about half the time and \"near\" \ solutions the other half (wherein either the number of coins and/or total \ value is off by a very small amount). Note that this type of problem is one \ of constraint satisfaction. An advantage in these is that we can discern from \ the proposed solution whether it is valid; those are exactly the cases for \ which we get an object value of zero, with all constraints satisfied." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Partitioning a set", "Section"], Cell[TextData[{ "We illustrate this sort of problem with an old example from computational \ folklore. We are to partition the integers from ", Cell[BoxData[ \(1\)]], " to ", Cell[BoxData[ \(100\)]], " into two sets of ", Cell[BoxData[ \(50\)]], ", such that the sums of the square roots in each set are as close to equal \ as possible. There are various ways to set this up as a problem for ", Cell[BoxData[ \(NMinimize\)]], ", and we illustrate one such below." }], "Text"], Cell[TextData[{ "We will utilize a simple way to choose ", Cell[BoxData[ \(50\)]], " elements from the set of ", Cell[BoxData[ \(100\)]], ". This is an approach we often use for adapting permutation problems for \ ", Cell[BoxData[ \(NMinimize\)]], ". We work with ", Cell[BoxData[ \(100\)]], " real values from ", Cell[BoxData[ \(0\)]], " to ", Cell[BoxData[ \(1\)]], " and their ordering (from the ", StyleBox["Mathematica", FontSlant->"Italic"], " ", Cell[BoxData[ \(Ordering\)]], " function) determines which is to be regarded as \"first\", which as \ \"second\", and so on. Note that this is different from the last example in \ that we now work with continuous variables even though the problem itself \ involves a discrete set." }], "Text"], Cell[BoxData[ \(splitRange[vec_] := With[{newvec = Ordering[vec], halflen = Floor[Length[vec]/2]}, {Take[newvec, halflen], Drop[newvec, halflen]}]\)], "Input"], Cell[TextData[{ "Once we have a way to associate a pair of subsets to a given set of ", Cell[BoxData[ \(100\)]], " values in the range from ", Cell[BoxData[ \(0\)]], " to ", Cell[BoxData[ \(1\)]], ", we form our objective function. A convenient choice is simply a square \ of a difference; this is often the case in optimization problems." }], "Text"], Cell[BoxData[ \(obfun[vec : {__Real}] := With[{vals = splitRange[vec]}, Abs[\((Apply[Plus, Sqrt[N[First[vals]]]] - Apply[Plus, Sqrt[N[Last[vals]]]])\)]]\)], "Input"], Cell["\<\ We now put these components together into a function that provides \ our set partition.\ \>", "Text"], Cell[BoxData[ \(getHalfSet[n_, opts___Rule] := Module[{vars, xx, ranges, nmin, vals}, \[IndentingNewLine]vars = Array[xx, n]; \[IndentingNewLine]ranges = Map[{#, 0, 1} &, vars]; \[IndentingNewLine]{nmin, vals} = NMinimize[obfun[vars], ranges, \ opts]; \[IndentingNewLine]{nmin, Map[Sort, splitRange[vars /. vals]]}]\)], "Input"], Cell[TextData[{ "If we do not specify otherwise, the default behavior will be to use the ", Cell[BoxData[ \(DifferentialEvolution\)]], " method; this is a sign of sound automatic behavior of ", Cell[BoxData[ \(NMinimize\)]], StyleBox[" ", "Input"], "[1]. All the same we explicitly set that method so that we can more \ readily pass it nondefault method\[Hyphen]specific options. Finally, we set \ this to run many iterations with alot of search points." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[{min, {s1, s2}} = getHalfSet[100, Method \[Rule] {DifferentialEvolution, CrossProbability \[Rule] .9, SearchPoints \[Rule] 100, PostProcess \[Rule] False}, \ MaxIterations \[Rule] 10000]]\)], "Input"], Cell[BoxData[ \({916.522704`\ Second, {5.30582059354856`*^-6, {{1, 4, 6, 8, 9, 13, 17, 20, 23, 24, 28, 29, 30, 33, 35, 36, 37, 38, 40, 41, 42, 46, 47, 48, 50, 51, 52, 54, 55, 56, 57, 58, 61, 63, 66, 67, 69, 71, 72, 73, 74, 75, 77, 78, 81, 83, 92, 94, 97, 99}, {2, 3, 5, 7, 10, 11, 12, 14, 15, 16, 18, 19, 21, 22, 25, 26, 27, 31, 32, 34, 39, 43, 44, 45, 49, 53, 59, 60, 62, 64, 65, 68, 70, 76, 79, 80, 82, 84, 85, 86, 87, 88, 89, 90, 91, 93, 95, 96, 98, 100}}}}\)], "Output"] }, Open ]], Cell["We obtain a fairly small value for our objective function.", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["A subset covering problem", "Section"], Cell[TextData[{ "The problem below was posed in the news group \ comp.soft-sys.math.mathematica. We are given a set of sets, each containing \ integers between ", Cell[BoxData[ \(1\)]], " and ", Cell[BoxData[ \(64\)]], ". Their union is the set of all integers in that range, and we want to \ find a set of ", Cell[BoxData[ \(12\)]], " subsets that covers that entire range. For those interested in trying \ this problem, the input in electronic form may be found in [3]." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(subsets = {{1, 2, 4, 8, 16, 32, 64}, {2, 1, 3, 7, 15, 31, 63}, {3, 4, 2, 6, 14, 30, 62}, {4, 3, 1, 5, 13, 29, 61}, {5, 6, 8, 4, 12, 28, 60}, {6, 5, 7, 3, 11, 27, 59}, {7, 8, 6, 2, 10, 26, 58}, {8, 7, 5, 1, 9, 25, 57}, {9, 10, 12, 16, 8, 24, 56}, {10, 9, 11, 15, 7, 23, 55}, {11, 12, 10, 14, 6, 22, 54}, {12, 11, 9, 13, 5, 21, 53}, {13, 14, 16, 12, 4, 20, 52}, {14, 13, 15, 11, 3, 19, 51}, {15, 16, 14, 10, 2, 18, 50}, {16, 15, 13, 9, 1, 17, 49}, {17, 18, 20, 24, 32, 16, 48}, {18, 17, 19, 23, 31, 15, 47}, {19, 20, 18, 22, 30, 14, 46}, {20, 19, 17, 21, 29, 13, 45}, {21, 22, 24, 20, 28, 12, 44}, {22, 21, 23, 19, 27, 11, 43}, {23, 24, 22, 18, 26, 10, 42}, {24, 23, 21, 17, 25, 9, 41}, {25, 26, 28, 32, 24, 8, 40}, {26, 25, 27, 31, 23, 7, 39}, {27, 28, 26, 30, 22, 6, 38}, {28, 27, 25, 29, 21, 5, 37}, {29, 30, 32, 28, 20, 4, 36}, {30, 29, 31, 27, 19, 3, 35}, {31, 32, 30, 26, 18, 2, 34}, {32, 31, 29, 25, 17, 1, 33}, {33, 34, 36, 40, 48, 64, 32}, {34, 33, 35, 39, 47, 63, 31}, {35, 36, 34, 38, 46, 62, 30}, {36, 35, 33, 37, 45, 61, 29}, {37, 38, 40, 36, 44, 60, 28}, {38, 37, 39, 35, 43, 59, 27}, {39, 40, 38, 34, 42, 58, 26}, {40, 39, 37, 33, 41, 57, 25}, {41, 42, 44, 48, 40, 56, 24}, {42, 41, 43, 47, 39, 55, 23}, {43, 44, 42, 46, 38, 54, 22}, {44, 43, 41, 45, 37, 53, 21}, {45, 46, 48, 44, 36, 52, 20}, {46, 45, 47, 43, 35, 51, 19}, {47, 48, 46, 42, 34, 50, 18}, {48, 47, 45, 41, 33, 49, 17}, {49, 50, 52, 56, 64, 48, 16}, {50, 49, 51, 55, 63, 47, 15}, {51, 52, 50, 54, 62, 46, 14}, {52, 51, 49, 53, 61, 45, 13}, {53, 54, 56, 52, 60, 44, 12}, {54, 53, 55, 51, 59, 43, 11}, {55, 56, 54, 50, 58, 42, 10}, {56, 55, 53, 49, 57, 41, 9}, {57, 58, 60, 64, 56, 40, 8}, {58, 57, 59, 63, 55, 39, 7}, {59, 60, 58, 62, 54, 38, 6}, {60, 59, 57, 61, 53, 37, 5}, {61, 62, 64, 60, 52, 36, 4}, {62, 61, 63, 59, 51, 35, 3}, {63, 64, 62, 58, 50, 34, 2}, {64, 63, 61, 57, 49, 33, 1}};\)\), "\n", \(Union[Flatten[subsets]] \[Equal] Range[64]\)}], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell["Method 1", "Subsection"], Cell[TextData[{ "We set up our objective function as follows. We represent a set of ", Cell[BoxData[ \(12\)]], " subsets of this \"universe\" set by a set of ", Cell[BoxData[ \(12\)]], " integers in the range from ", Cell[BoxData[ \(1\)]], " to the number of subsets (which in this example is also ", Cell[BoxData[ \(64\)]], "). This set is allowed to contain repetitions. Our objective function to \ minimize will be based on how many elements from ", Cell[BoxData[ \(1\)]], " through ", Cell[BoxData[ \(64\)]], " are \"covered\". Specifically it will be ", Cell[BoxData[ \(2\)]], " raised to the #(elements not covered) power. The code below does this. As \ it is a problem that may require many iterations and a relatively large \ search space, we allow for nondefault option values for these parameters." }], "Text"], Cell[BoxData[ \(f[n : {___Integer}, set_, mx_Integer] := 2^Length[Complement[Range[mx], Union[Flatten[set[\([n]\)]]]]]\)], "Input", CellLabel->"In[7]:="], Cell[BoxData[ \(spanningSets[set_, nsets_, iter_, sp_, cp_] := Module[{vars, rnges, max = Length[set], nmin, vals}, vars = Array[xx, nsets]; \[IndentingNewLine]rnges = Map[\((1 \[LessEqual] # \[LessEqual] max)\) &, vars]; \[IndentingNewLine]{nmin, vals} = NMinimize[{f[vars, set, max], Append[rnges, Element[vars, Integers]]}, vars, MaxIterations \[Rule] iter, Method \[Rule] {DifferentialEvolution, SearchPoints \[Rule] sp, CrossProbability \[Rule] cp}]; \[IndentingNewLine]vals = Union[vars /. vals]; \[IndentingNewLine]{nmin, vals}]\)], "Input", CellLabel->"In[8]:="], Cell[CellGroupData[{ Cell[BoxData[{ \(Timing[{min, sets} = spanningSets[subsets, 12, 700, 200, .94]]\), "\[IndentingNewLine]", \(Length[Union[Flatten[subsets[\([sets]\)]]]]\)}], "Input"], Cell[BoxData[{ \({196.69999999999987`\ Second, {1.`, {1, 15, 16, 21, 26, 30, 34, 41, 45, 54, 59, 60}}}\), "\n", \(64\)}], "Output", GeneratedCell->False, CellAutoOverwrite->False] }, Open ]], Cell[TextData[{ "This example has an unfortunate drawback. It requires a nondefault value \ for the ", Cell[BoxData[ \(CrossProbability\)]], " option in the ", Cell[BoxData[ \(DifferentialEvolution\)]], " method of ", Cell[BoxData[ \(NMinimize\)]], ". It is not entirely trivial to find useful values for such options, or \ even to know which such options to alter from default values. We hope to \ ameliorate this need in future work by providing an adaptive evolution that \ modifies its own parameters as it proceeds." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Method 2", "Subsection"], Cell["\<\ This problem may also be tackled in other ways. One is to write a \ simple \"greedy\" algorithm. Experience indicates that such an approach will \ fail for this particular set. Another is to cast it as a standard knapsack \ problem. We will show how to do this. First we transform our set of subsets \ into a \"bit vector\" representation; each subset is represented by a \ positional list of zeros and ones.\ \>", "Text"], Cell[BoxData[{ \(densevec[spvec_, len_] := Module[{vec = Table[0, {len}]}, \[IndentingNewLine]Do[ vec[\([spvec[\([j]\)]]\)] = 1, {j, Length[spvec]}]; \[IndentingNewLine]vec]\ \), "\n", \(\(mat = Map[densevec[#, 64] &, subsets];\)\)}], "Input", CellLabel->"In[9]:="], Cell[TextData[{ "We now work with ", Cell[BoxData[ \(0 - 1\)]], " variables and minimize their sum, subject to the constraint that an \ appropriate inner product be strictly positive. " }], "Text"], Cell[BoxData[ \(spanningSets2[set_, iter_, sp_, seed_, cp_: .5] := Module[{vars, rnges, max = Length[set], nmin, vals}, vars = Array[xx, max]; \[IndentingNewLine]rnges = Map[\((0 \[LessEqual] # \[LessEqual] 1)\) &, vars]; \[IndentingNewLine]{nmin, vals} = NMinimize[{Apply[Plus, vars], Join[rnges, {Element[vars, Integers]}, Thread[vars . set \[GreaterEqual] Table[1, {max}]]]}, vars, MaxIterations \[Rule] iter, Method \[Rule] {DifferentialEvolution, CrossProbability \[Rule] cp, SearchPoints \[Rule] sp, RandomSeed \[Rule] seed}]; \[IndentingNewLine]vals = vars /. vals; \[IndentingNewLine]{nmin, vals}]\)], "Input", CellLabel->"In[11]:="], Cell[CellGroupData[{ Cell[BoxData[ \(Timing[{min, sets} = spanningSets2[mat, 2000, 100, 0, .9]]\)], "Input",\ CellLabel->"In[17]:="], Cell[BoxData[ \({1930.4027039999999`\ Second, {12.`, {0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}}}\)], "Output", CellLabel->"Out[17]="] }, Open ]], Cell[TextData[{ "We have again obtained a result that uses ", Cell[BoxData[ \(12\)]], " subsets. We check that it covers the entire range." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Apply[Plus, Map[Min[#, 1] &, sets . mat]]\)], "Input", CellLabel->"In[19]:="], Cell[BoxData[ \(64\)], "Output", CellLabel->"Out[19]="] }, Open ]], Cell[TextData[{ "We see that this method was much slower. Experience indicates that it \ needs alot of iterations and careful setting of the ", Cell[BoxData[ \(CrossProbability\)]], " option. So at present ", Cell[BoxData[ \(NMinimize\)]], " has difficulties with this formulation. All the same it is encouraging to \ realize that one may readily set this up as a standard knapsack problem; over \ time ", Cell[BoxData[ \(NMinimize\)]], " internals may improve to the point where it can more efficiently handle \ the problem in this way." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["An assignment problem", "Section"], Cell[TextData[{ "Our next example is a benchmark from the literature of discrete \ optimization. We are given two square matrices. We want a permutation that, \ when applied to the rows and columns of the second matrix, multiplied element\ \[Hyphen]wise with corresponding elements of the first, and all elements \ summed, we get a minimum. The matrices we use have ", Cell[BoxData[ \(25\)]], " rows; they may be found in [4]. This is known as the \"NUG25\" example \ and it is an example of a \"quadratic assignment problem\" (QAP). The optimal \ result is known and was verified by a large parallel computation. The actual \ matrices are in a hidden cell below. One should recognize that the methods of \ handling this problem can, with minor modification, be applied to related \ ones such as the travelling salesman problem. In general, problems that \ require a \"best permutation\" may be amenable to the methods described \ below." }], "Text"], Cell[CellGroupData[{ Cell["Method 1", "Subsection"], Cell[TextData[{ "Our first problem is to decide how one can make a set of values into a \ permutation. One approach, as with the set partition problem, is to take \ their ", Cell[BoxData[ \(Ordering\)]], StyleBox[".", "Input"], " In order that this avoid collisions we thus work with real values." }], "Text"], Cell[BoxData[ \(permuteMatrix[mat_, perm_] := mat[\([perm, perm]\)]\)], "Input"], Cell[BoxData[ \(QAP[mat1_, mat2_, cp_, it_, sp_, sc_] := Module[{len = Length[mat1], obfunc, vars, vv, nmin, vals, rnges}, \[IndentingNewLine]vars = Array[vv, len]; \[IndentingNewLine]rnges = Map[{#, 0, 1} &, vars]; \[IndentingNewLine]obfunc[vec : {__Real}] := Apply[Plus, Flatten[mat1* permuteMatrix[mat2, Ordering[vec]]]]; \[IndentingNewLine]{nmin, vals} = NMinimize[obfunc[vars], rnges, MaxIterations \[Rule] it \.18, Method \[Rule] {DifferentialEvolution, SearchPoints \[Rule] sp, CrossProbability \[Rule] cp, ScalingFactor \[Rule] sc, PostProcess \[Rule] False}]; \[IndentingNewLine]{nmin, Ordering[vars /. vals]}]\)], "Input"], Cell[TextData[{ "Again we face the issue that this problem requires nonstandard values for \ options to the ", Cell[BoxData[ \(DifferentialEvolution\)]], " method, in order to achieve a reasonable result. While this is regretable \ it is clearly better than having no recourse at all. The specific values we \ use were found by Brett Champion by running many short trials and noticing \ which parameter values seemed to work best (it was also his idea to try \ nondefault values in the first place)." }], "Text"], Cell[TextData[{ "The idea behind having ", Cell[BoxData[ \(CrossProbability\)]], " relatively small is that we do not want many \"genetic crossovers\" in \ mating a pair of vectors. This in turn is because of the way we define a \ permutation. In particular it is not just values but relative values across \ the entire vector that give us the permutation, and thus disrupting more than \ a few, even when mating a pair of \"good\" vectors, is likely to give a \ \"random\" bad vector." }], "Text"], Cell["\<\ Below is the optimal permutation and the objective function value \ we obtain therefrom. We also show as baseline the result from applying no \ permutation, and also the result of applying several random permutations. \ This gives some idea of how to gauge the results below.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(p = {5, 11, 20, 15, 22, 2, 25, 8, 9, 1, 18, 16, 3, 6, 19, 24, 21, 14, 7, 10, 17, 12, 4, 23, 13};\)\), "\[IndentingNewLine]", \(best = Apply[Plus, Flatten[aa*permuteMatrix[bb, p]]]\), "\n", \(baseline = Apply[Plus, Flatten[aa*bb]]\), "\[IndentingNewLine]", \(randomvals = Table[\[IndentingNewLine]perm = Ordering[Table[Random[], {25}]]; \[IndentingNewLine]Apply[Plus, Flatten[aa* permuteMatrix[bb, perm]]], \[IndentingNewLine]{10}]\)}], "Input",\ CellLabel->"In[23]:="], Cell[BoxData[{ \(3744\), "\n", \(4838\), "\n", \({5250, 5076, 5050, 4628, 4858, 5140, 5058, 5250, 4962, 4870}\)}], "Output", CellLabel->"Out[24]=", GeneratedCell->False, CellAutoOverwrite->False] }, Open ]], Cell["\<\ A much more strenuous run over random permutations may be \ indicative of how hard it is to get good results by randomized search.\ \>", \ "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(SeedRandom[1111];\)\), "\[IndentingNewLine]", \(Timing[\(randomvals = Table[\[IndentingNewLine]perm = Ordering[Table[Random[], {25}]]; \[IndentingNewLine]Apply[Plus, Flatten[aa* permuteMatrix[bb, perm]]], \[IndentingNewLine]{1000000}];\)]\), "\ \[IndentingNewLine]", \(Min[randomvals]\)}], "Input", CellLabel->"In[210]:="], Cell[BoxData[{ \({1130.2\ Second, Null}\), "\n", \(4284\)}], "Output", CellLabel->"Out[211]=", CellEditDuplicate->False, GeneratedCell->False, CellAutoOverwrite->False] }, Open ]], Cell["\<\ We see that the baseline permutation (do nothing) and random \ permutations tend to be far from optimal, and even a large sampling will get \ us only about half way from baseline to optimal. A relatively brief run with \ good values for the algorithm parameters, on the other hand, yields something \ better still.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(SeedRandom[11111];\)\), "\[IndentingNewLine]", \(Timing[{min, perm} = QAP[aa, bb, .06, 200, 40, .6]]\)}], "Input", CellLabel->"In[34]:="], Cell[BoxData[ \({17.33`\ Second, {4066, {5, 3, 18, 11, 2, 17, 8, 9, 23, 1, 22, 10, 6, 19, 13, 12, 20, 14, 7, 25, 24, 4, 21, 16, 15}}}\)], "Output", CellLabel->"Out[35]="] }, Open ]], Cell["We now try a longer run.", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(SeedRandom[11111];\)\), "\[IndentingNewLine]", \(Timing[{min, perm} = QAP[aa, bb, .06, 5000, 100, .6]]\)}], "Input", CellLabel->"In[38]:="], Cell[BoxData[ \({1349.22`\ Second, {3836, {5, 2, 25, 11, 24, 12, 17, 4, 18, 21, 20, 3, 8, 14, 16, 15, 23, 9, 6, 7, 13, 22, 10, 19, 1}}}\)], "Output", CellLabel->"Out[39]="] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Method 2", "Subsection"], Cell[TextData[{ "Once again we have a very different approach to this problem. The idea is \ to generate a permutation as a \"shuffle\" of a set of integers. We have for \ ", Cell[BoxData[ \(vector\)]], " a set of integers from ", Cell[BoxData[ \(1\)]], " to ", Cell[BoxData[ \(len\)]], ", the length of the set in question. The range restriction is the only \ stipulation and in particular it may contain repeats. We associate to it a \ unique permutation as follows. We initialize a \"deck\" to contain ", Cell[BoxData[ \(len\)]], " zeros . The first element in ", Cell[BoxData[ \(deck\)]], " is then set to the first element in ", Cell[BoxData[ \(vector\)]], ". We also have a \"marker\" set telling us that that first element is now \ \"used\". We iterate over subsequent elements in ", Cell[BoxData[ \(deck\)]], ", setting them to the corresponding values in ", Cell[BoxData[ \(vector\)]], " provided those values are not yet used. Once done with this iteration we \ go through the elements that have no values, assigning them in sequence the \ values that have not yet been assigned." }], "Text"], Cell[TextData[{ "This notion of associating a list with repeats to a distinct shuffle has a \ clear drawback insofar as earlier elements are more likely to be assigned \ corresponding values in ", Cell[BoxData[ \(vector\)]], ". All the same this provides a reasonable way to make a \"chromosome\" \ vector containing repeats correspond to a permutation. Moreover, one can see \ that any sensible mating process of two chromosomes will less drastically \ alter the objective function than would be the case in method 1, as the \ corresponding permutation now depends far less on overall ordering in the \ chromosomes. The advantage is thus that this method will be less in need of \ intricate crossover\[Hyphen]probability parameter tuning." }], "Text"], Cell[BoxData[ \(\(getPerm = Compile[{{vec, _Integer, 1}}, Module[{p1, p2, len = Length[vec], k}, p1 = \(p2 = Table[0, {len}]\); \[IndentingNewLine]Do[ k = vec[\([j]\)]; \[IndentingNewLine]If[ p2[\([k]\)] \[Equal] 0, \[IndentingNewLine]p2[\([k]\)] = j; \[IndentingNewLine]p1[\([j]\)] = k;], \[IndentingNewLine]{j, len}]; \[IndentingNewLine]k = 1; \[IndentingNewLine]Do[ If[p1[\([j]\)] \[Equal] 0, While[p2[\([k]\)] \[NotEqual] 0, \(k++\)]; \[IndentingNewLine]p1[\([j]\)] = k; \[IndentingNewLine]p2[\([k]\)] = j], {j, len}]; \[IndentingNewLine]p1]];\)\)], "Input", CellLabel->"In[172]:="], Cell[BoxData[ \(QAP2[mat1_, mat2_, cp_, it_, sp_] := Module[{len = Length[mat1], obfunc, vars, vv, nmin, vals, constraints}, \[IndentingNewLine]vars = Array[vv, len]; \[IndentingNewLine]constraints = Prepend[Map[\((1 \[LessEqual] # \[LessEqual] len)\) &, vars], Element[vars, Integers]]; \[IndentingNewLine]obfunc[ vec : {__Integer}] := Apply[Plus, Flatten[mat1* permuteMatrix[mat2, getPerm[vec]]]]; \[IndentingNewLine]{nmin, vals} = NMinimize[{obfunc[vars], constraints}, vars, Method \[Rule] {DifferentialEvolution, SearchPoints \[Rule] sp, CrossProbability \[Rule] cp, PostProcess \[Rule] False}, \.18MaxIterations \[Rule] it]; \[IndentingNewLine]{nmin, getPerm[vars /. vals]}]\)], "Input"], Cell["\<\ Though we suspect that tuning is less important for this method, we \ anyway show details of a \"tuning run\". We take several short runs with a \ given crossover probability parameter value, average them, and see what \ values seem to work best. We then try a longer run using one such value. This \ method is generally useful for problems where default settings may not be \ optimal.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(SeedRandom[111111];\)\), "\[IndentingNewLine]", \(Timing[\(vals = Table[{j, Table[{min, perm} = QAP2[aa, bb, j/100, 200, 10]; min, {5}]}, {j, 5, 95, 5}];\)]\), "\[IndentingNewLine]", \(v2\ = \ Map[{#[\([1]\)], Apply[Plus, #[\([2]\)]]/5. } &, \ vals]\)}], "Input", CellLabel->"In[186]:="], Cell[BoxData[{ \({465.1699999999999`\ Second, Null}\), "\n", \({{5, 4320.400000000001`}, {10, 4362.8`}, {15, 4320.8`}, {20, 4292.`}, {25, 4333.6`}, {30, 4328.8`}, {35, 4353.2`}, {40, 4304.8`}, {45, 4351.2`}, {50, 4359.2`}, {55, 4342.400000000001`}, {60, 4329.2`}, {65, 4312.8`}, {70, 4321.2`}, {75, 4325.6`}, {80, 4262.8`}, {85, 4278.`}, {90, 4238.400000000001`}, {95, 4225.6`}}\)}], "Output", CellLabel->"Out[187]=", CellEditDuplicate->False, GeneratedCell->False, CellAutoOverwrite->False] }, Open ]], Cell[TextData[{ "From this we see that large values seem to work at least slightly better \ than other values. A similar test run over values in the range ", Cell[BoxData[ \(0.90\)]], " through ", Cell[BoxData[ \(0.98\)]], " indicates that ", Cell[BoxData[ \(0.96\)]], " might be best for our purposes." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(SeedRandom[111111];\)\), "\[IndentingNewLine]", \({min, perm} = QAP2[aa, bb, .96, 20000, 200]\)}], "Input", CellLabel->"In[195]:="], Cell[BoxData[ \({3788, {6, 3, 21, 23, 16, 12, 25, 9, 10, 2, 19, 17, 15, 7, 20, 22, 1, 4, 5, 8, 11, 13, 18, 24, 14}}\)], "Output", CellLabel->"Out[196]=", CellEditDuplicate->False, GeneratedCell->False, CellAutoOverwrite->False] }, Open ]], Cell["\<\ This gets us quite close to the global minimum with a scant two \ dozen lines of code. While it is mildly more complicated than method 1 above, \ it has one clear advantage. Both intuition and practical experience indicate \ that it is less in need of careful tuning of relatively obscure algorithm \ parameters. Also note that much of the code complexity is in associating a \ unique permutation to a given vector in our \"search space\". This part is \ likely to be problematic for any algorithm. The fact that we employ a genetic \ one makes it all the more so because we then need it to behave well with \ respect to a mating process, the internals of which are a black box. Hence a \ method that is relatively stable with respect to tuning parameters is all the \ more desirable.\ \>", "Text"], Cell["\<\ Using method 1 above, Brett Champion has achieved even better \ results for this problem. He has found a permutation that gives a function \ value of 3752. But the important point is that we have obtained a quite \ practical heuristic improvement in the objective function relative to random \ values, and this idea may apply even in cases where the absolute minimizer is \ not already known.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["What lies beyond", "Subsection"], Cell[TextData[{ "This example comes from a family, the hardest of which is NUG30. The \ salient features are that the baseline and \"typical\" random permutations \ give values around ", Cell[BoxData[ \(8000\)]], ", and the minimizing permutation gives ", Cell[BoxData[ \(6124\)]], ". With some tuning of ", Cell[BoxData[ \(DifferentialEvolution\)]], " parameters and reasonably long runs we have obtained values within ", Cell[BoxData[ \(100\)]], " of that minimum." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Other approaches for knapsack and related problems", "Section"], Cell[TextData[{ "It should be noted that knapsack problems that have exclusively equality \ constraints can often be done much more readily using lattice reduction \ methods. See [4] for a simple example of how one might tackle, for example, a \ \"subset\[Hyphen]sum\" problem using ", StyleBox["Mathematica", FontSlant->"Italic"], ". The set cover problem above requires inequalities and hence is not \ amenable to the lattice approach." }], "Text"], Cell["\<\ A related application of lattice reduction is to find \"small\" \ solutions to a system of linear integer equations. Details may be found in \ [5].\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Summary and future work", "Section"], Cell[TextData[{ "We have seen several examples of discrete optimization problems and how \ one might tackle them in ", StyleBox["Mathematica", FontSlant->"Italic"], ". The underlying method we utilize is a member of the evolutionary family \ of optimization algorithms and we have seen that it is reasonably well \ adapted for these problems. We have discussed various ways to cast our \ examples so that simple ", StyleBox["Mathematica", FontSlant->"Italic"], " code using ", Cell[BoxData[ \(NMinimize\)]], " may be applied. Indeed, we noticed that there are often very different \ ways to approach the same combinatorial optimization problem." }], "Text"], Cell[TextData[{ "This uses technology presently under development and so it is to be \ expected that it might improve over time. For example, we hope to make it \ adaptive so that one need not \"tune\" the parameters (in essence, they \ become part of the \"chromosomes\" and evolve). We also might allow an \ automated multilevel approach wherein several short runs (similar to tuning \ runs) will be used to initialize values for a longer run. This said, it is \ clear from the examples that ", Cell[BoxData[ \(NMinimize\)]], " is already a powerful tool for handling nontrivial combinatorial \ optimization problems." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["References", "Section"], Cell[TextData[{ "[1] B. Champion (2002). Numerical optimization in Mathematica: an \ insider's view of ", Cell[BoxData[ \(NMinimize\)]], ". These proceedings." }], "Reference"], Cell[TextData[{ "[2] C. Jacob (2001).Illustrating Evolutionary Computation with ", StyleBox["Mathematica", FontSlant->"Italic"], ". Morgan Kaufmann." }], "Reference", CellDingbat->None, FontSize->10], Cell[TextData[{ "[3] D. Lichtblau (2001). ", Cell[BoxData[ \(NMinimize\)]], " in ", StyleBox["Mathematica", FontSlant->"Italic"], " 4.2. 2001 ", StyleBox["Mathematica", FontSlant->"Italic"], " Developer's Conference notebook. An electronic version may be be found \ at:\nhttp://library.wolfram.com/conferences/devconf2001/lichtblau/lichtblau.\ nb" }], "Reference", CellDingbat->None, FontSize->10], Cell["\<\ [4] D. Lichtblau (2002).Usenet news group \ comp.soft-sys.math.mathematica communication. Archived at: http://library.wolfram.com/mathgroup/archive/2002/Feb/msg00410.html\ \>", \ "Reference", CellDingbat->None, FontSize->10], Cell["\<\ [5] D. Lichtblau (2002). Revisiting strong Gr\[ODoubleDot]bner \ bases over Euclidean domains. Submitted.\ \>", "Reference", CellDingbat->None, FontSize->10], Cell[TextData[{ "[6] K. Price and R. Storn (1997). Differential evolution. ", StyleBox["Dr. Dobb's Journal,", "TI"], " April 1997. pp. 18\[Dash]24, 78." }], "Reference", CellDingbat->None, FontSize->10], Cell[TextData[{ "[7] S. Wolfram (1999). ", StyleBox["The Mathematica Book", FontSlant->"Italic"], " (4th edition). Wolfram Media/Cambridge University Press." }], "Reference", CellDingbat->None, FontSize->10] }, Open ]] }, Open ]] }, FrontEndVersion->"4.1 for X", ScreenRectangle->{{0, 1024}, {0, 768}}, Evaluator->"math42", WindowSize->{540, 601}, WindowMargins->{{Automatic, 65}, {Automatic, 5}}, PrintingPageRange->{Automatic, Automatic}, PageHeaders->{{Inherited, Inherited, Inherited}, {None, Inherited, None}}, PageFooters->{{Inherited, Inherited, Inherited}, {Inherited, Cell[ TextData[ { CounterBox[ "Page"]}], "PageNumber"], Inherited}}, PrintingOptions->{"PrintingMargins"->{{43.1875, 43.1875}, {46.75, 54}}, "PaperSize"->{612, 792}, "PaperOrientation"->"Portrait", "PrintCellBrackets"->False, "PrintRegistrationMarks"->True, "PrintMultipleHorizontalPages"->False, "FirstPageHeader"->True, "FirstPageFooter"->False, "FacingPages"->False, "PostScriptOutputFile":>FrontEnd`FileName[{$RootDirectory, "home", "usr1", \ "danl"}, "Lichtblau_SCI2002.nb.ps", CharacterEncoding -> "ISO8859-1"], "Magnification"->1}, StyleDefinitions -> Notebook[{ Cell[CellGroupData[{ Cell["Style Definitions", "Subtitle"], Cell["\<\ Modify the definitions below to change the default appearance of \ all cells in a given style. Make modifications to any definition using commands in the Format menu.\ \>", "Text"], Cell[CellGroupData[{ Cell["Style Environment Names", "Section"], Cell[StyleData[All, "Working"], ScriptMinSize->9], Cell[StyleData[All, "Printout"], PageWidth->PaperWidth, ShowCellLabel->False, ImageSize->{200, 200}, PrivateFontOptions->{"FontType"->"Outline"}] }, Closed]], Cell[CellGroupData[{ Cell["Notebook Options", "Section"], Cell["\<\ The options defined for the style below will be used at the \ Notebook level.\ \>", "Text"], Cell[StyleData["Notebook"], PageHeaders->{{Cell[ TextData[ { CounterBox[ "Page"]}], "PageNumber"], None, Cell[ TextData[ { ValueBox[ "FileName"]}], "Header"]}, {Cell[ TextData[ { ValueBox[ "FileName"]}], "Header"], None, Cell[ TextData[ { CounterBox[ "Page"]}], "PageNumber"]}}, PageHeaderLines->{True, True}, PrintingOptions->{"FirstPageHeader"->False, "FacingPages"->True}, CellLabelAutoDelete->False, CellFrameLabelMargins->6, StyleMenuListing->None] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Headings", "Section"], Cell[CellGroupData[{ Cell[StyleData["Title"], CellMargins->{{18, 30}, {4, 20}}, CellGroupingRules->{"TitleGrouping", 0}, PageBreakBelow->False, CellFrameMargins->9, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, LineSpacing->{0.95, 11}, CounterIncrements->"Title", CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontSize->14, FontWeight->"Bold"], Cell[StyleData["Title", "Printout"], CellMargins->{{18, 30}, {4, 0}}, CellFrameMargins->4, FontSize->14] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Subtitle"], CellMargins->{{18, 30}, {0, 10}}, CellGroupingRules->{"TitleGrouping", 10}, PageBreakBelow->False, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, LineSpacing->{1, 0}, CounterIncrements->"Subtitle", CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontSize->24, FontSlant->"Italic"], Cell[StyleData["Subtitle", "Printout"], CellMargins->{{18, 30}, {0, 10}}, FontSize->18] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["SectionFirst"], CellFrame->{{0, 0}, {0, 3}}, CellMargins->{{18, 30}, {4, 14}}, CellGroupingRules->{"SectionGrouping", 40}, PageBreakBelow->False, CellFrameMargins->3, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, CounterIncrements->"Section", CounterAssignments->{{"Subsection", 0}, {"Subsubsection", 0}}, FontSize->12, FontWeight->"Bold"], Cell[StyleData["SectionFirst", "Printout"], FontSize->11] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Section"], CellMargins->{{18, 30}, {3, 7}}, CellGroupingRules->{"SectionGrouping", 40}, PageBreakBelow->False, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, CounterIncrements->"Section", CounterAssignments->{{"Subsection", 0}, {"Subsubsection", 0}}, FontSize->12, FontWeight->"Bold"], Cell[StyleData["Section", "Printout"], FontSize->11] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Subsection"], CellDingbat->None, CellMargins->{{18, 30}, {1, 4}}, CellGroupingRules->{"SectionGrouping", 50}, PageBreakBelow->False, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, CounterIncrements->"Subsection", CounterAssignments->{{"Subsubsection", 0}}, FontSize->11, FontSlant->"Italic"], Cell[StyleData["Subsection", "Printout"], FontSize->10] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Subsubsection"], CellDingbat->"\[FilledSmallSquare]", CellMargins->{{18, 30}, {4, 12}}, CellGroupingRules->{"SectionGrouping", 60}, PageBreakBelow->False, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, CounterIncrements->"Subsubsection", FontSize->12, FontWeight->"Bold"], Cell[StyleData["Subsubsection", "Printout"], FontSize->10] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["Styles for Body Text", "Section"], Cell[CellGroupData[{ Cell[StyleData["Text"], CellMargins->{{18, 10}, {3, 3}}, InputAutoReplacements->{"TeX"->StyleBox[ RowBox[ {"T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "LaTeX"->StyleBox[ RowBox[ {"L", StyleBox[ AdjustmentBox[ "A", BoxMargins -> {{-0.36, -0.1}, {0, -0}}, BoxBaselineShift -> -0.2], FontSize -> Smaller], "T", AdjustmentBox[ "E", BoxMargins -> {{-0.075, -0.085}, {0, 0}}, BoxBaselineShift -> 0.5], "X"}]], "mma"->"Mathematica", "Mma"->"Mathematica", "MMA"->"Mathematica", Inherited}, TextJustification->1, Hyphenation->True, LineSpacing->{1, 2}, CounterIncrements->"Text", FontSize->10], Cell[StyleData["Text", "Printout"], CellMargins->{{20, 20}, {3, 3}}, LineSpacing->{1, 3}, FontSize->9] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Caption"], CellMargins->{{55, 50}, {5, 5}}, PageBreakAbove->False, Hyphenation->True, FontSize->10], Cell[StyleData["Caption", "Printout"], CellMargins->{{55, 55}, {5, 2}}, FontSize->8] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["Styles for Input/Output", "Section"], Cell["\<\ The cells in this section define styles used for input and output \ to the kernel. Be careful when modifying, renaming, or removing these \ styles, because the front end associates special meanings with these style \ names.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["Input"], CellMargins->{{25, 25}, {5, 8}}, Evaluatable->True, CellGroupingRules->"InputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, CellLabelMargins->{{26, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultInputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, AutoItalicWords->{}, LanguageCategory->"Formula", FormatType->InputForm, ShowStringCharacters->True, NumberMarks->True, LinebreakAdjustments->{0.85, 2, 10, 0, 1}, CounterIncrements->"Input", FontSize->10, FontWeight->"Bold"], Cell[StyleData["Input", "Printout"], CellMargins->{{23, 23}, {0, 4}}, ShowCellLabel->False, LinebreakAdjustments->{0.85, 2, 10, 1, 1}, FontSize->9] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Output"], CellMargins->{{25, 25}, {8, 5}}, CellEditDuplicate->True, CellGroupingRules->"OutputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, CellLabelPositioning->Left, CellLabelMargins->{{26, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultOutputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, AutoItalicWords->{}, LanguageCategory->"Formula", FormatType->InputForm, CounterIncrements->"Output"], Cell[StyleData["Output", "Printout"], CellMargins->{{23, 23}, {5, 4}}, ShowCellLabel->False, FontSize->9] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Message"], CellDingbat->"\[LongDash]", CellMargins->{{55, Inherited}, {Inherited, Inherited}}, CellGroupingRules->"OutputGrouping", PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, CellLabelMargins->{{26, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultOutputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, AutoItalicWords->{}, FormatType->InputForm, CounterIncrements->"Message", StyleMenuListing->None, FontSize->10, FontSlant->"Italic"], Cell[StyleData["Message", "Printout"], CellMargins->{{55, 55}, {0, 3}}, FontSize->8] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Print"], CellMargins->{{55, Inherited}, {Inherited, Inherited}}, CellGroupingRules->"OutputGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GroupPageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, CellLabelMargins->{{26, Inherited}, {Inherited, Inherited}}, DefaultFormatType->DefaultOutputFormatType, TextAlignment->Left, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, AutoItalicWords->{}, FormatType->InputForm, CounterIncrements->"Print", StyleMenuListing->None], Cell[StyleData["Print", "Printout"], CellMargins->{{54, 72}, {2, 10}}, FontSize->8] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Graphics"], CellMargins->{{55, Inherited}, {Inherited, Inherited}}, CellGroupingRules->"GraphicsGrouping", CellHorizontalScrolling->True, PageBreakWithin->False, GeneratedCell->True, CellAutoOverwrite->True, ShowCellLabel->False, DefaultFormatType->DefaultOutputFormatType, FormatType->InputForm, CounterIncrements->"Graphics", StyleMenuListing->None], Cell[StyleData["Graphics", "Printout"], CellMargins->{{55, 55}, {0, 15}}, ImageSize->{0.0625, 0.0625}, ImageMargins->{{35, Inherited}, {Inherited, 0}}, FontSize->8] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["CellLabel"], CellMargins->{{9, Inherited}, {Inherited, Inherited}}, StyleMenuListing->None, FontFamily->"Helvetica", FontSize->9, FontSlant->"Oblique"], Cell[StyleData["CellLabel", "Printout"], CellMargins->{{0, Inherited}, {Inherited, Inherited}}, FontSize->8] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["Unique Styles", "Section"], Cell[CellGroupData[{ Cell[StyleData["Author"], CellMargins->{{45, Inherited}, {2, 20}}, CellGroupingRules->{"TitleGrouping", 20}, PageBreakBelow->False, CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontSize->12], Cell[StyleData["Author", "Printout"], CellMargins->{{36, Inherited}, {2, 14}}, FontSize->11] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Address"], CellMargins->{{45, Inherited}, {10, 2}}, CellGroupingRules->{"TitleGrouping", 30}, PageBreakBelow->False, LineSpacing->{1, 1}, CounterAssignments->{{"Section", 0}, {"Equation", 0}, {"Figure", 0}}, FontSize->10, FontSlant->"Italic"], Cell[StyleData["Address", "Printout"], CellMargins->{{36, Inherited}, {10, 2}}, FontSize->9.5] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Abstract"], CellMargins->{{45, 75}, {Inherited, 6}}, Hyphenation->True, LineSpacing->{1, 0}, FontSize->10], Cell[StyleData["Abstract", "Printout"], CellMargins->{{36, 67}, {Inherited, 6}}, FontSize->9] }, Open ]], Cell[CellGroupData[{ Cell[StyleData["Reference"], CellMargins->{{18, 40}, {2, 2}}, TextJustification->1, Hyphenation->True, LineSpacing->{1, 0}, FontSize->10], Cell[StyleData["Reference", "Printout"], CellMargins->{{18, 40}, {Inherited, 0}}, FontSize->8.5] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Hyperlink Styles", "Section"], Cell["\<\ The cells below define styles useful for making hypertext \ ButtonBoxes. The \"Hyperlink\" style is for links within the same Notebook, \ or between Notebooks.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["Hyperlink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookLocate[ #2]}]&), Active->True, ButtonNote->ButtonData}], Cell[StyleData["Hyperlink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell["\<\ The following styles are for linking automatically to the on-line \ help system.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["MainBookLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "MainBook", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["MainBookLink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["AddOnsLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontFamily->"Courier", FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "AddOns", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["AddOnsLink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["RefGuideLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontFamily->"Courier", FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "RefGuide", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["RefGuideLink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["GettingStartedLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "GettingStarted", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["GettingStartedLink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["OtherInformationLink"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, FontColor->RGBColor[0, 0, 1], FontVariations->{"Underline"->True}, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`HelpBrowserLookup[ "OtherInformation", #]}]&), Active->True, ButtonFrame->"None"}], Cell[StyleData["OtherInformationLink", "Printout"], FontSize->10, FontColor->GrayLevel[0], FontVariations->{"Underline"->False}] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Palette Styles", "Section"], Cell["\<\ The cells below define styles that define standard \ ButtonFunctions, for use in palette buttons.\ \>", "Text"], Cell[StyleData["Paste"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, After]}]&)}], Cell[StyleData["Evaluate"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], SelectionEvaluate[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["EvaluateCell"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionMove[ FrontEnd`InputNotebook[ ], All, Cell, 1], FrontEnd`SelectionEvaluateCreateCell[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["CopyEvaluate"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`SelectionCreateCell[ FrontEnd`InputNotebook[ ], All], FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionEvaluate[ FrontEnd`InputNotebook[ ], All]}]&)}], Cell[StyleData["CopyEvaluateCell"], StyleMenuListing->None, ButtonStyleMenuListing->Automatic, ButtonBoxOptions->{ButtonFunction:>(FrontEndExecute[ { FrontEnd`SelectionCreateCell[ FrontEnd`InputNotebook[ ], All], FrontEnd`NotebookApply[ FrontEnd`InputNotebook[ ], #, All], FrontEnd`SelectionEvaluateCreateCell[ FrontEnd`InputNotebook[ ], All]}]&)}] }, Closed]], Cell[CellGroupData[{ Cell["Styles for Automatic Numbering", "Section"], Cell["\<\ The following styles are useful for numbered equations, figures, \ etc. They automatically give the cell a FrameLabel containing a reference to \ a particular counter, and also increment that counter.\ \>", "Text"], Cell[CellGroupData[{ Cell[StyleData["NumberedEquation"], CellMargins->{{55, 10}, {0, 10}}, CellFrameLabels->{{None, Cell[ TextData[ {"(", CounterBox[ "NumberedEquation"], ")"}]]}, {None, None}}, DefaultFormatType->DefaultInputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, CounterIncrements->"NumberedEquation", FormatTypeAutoConvert->False], Cell[StyleData["NumberedEquation", "Printout"], CellMargins->{{55, 55}, {0, 10}}, FontSize->10] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["NumberedFigure"], CellMargins->{{55, 145}, {2, 10}}, CellHorizontalScrolling->True, CellFrameLabels->{{None, None}, {Cell[ TextData[ {"Figure ", CounterBox[ "NumberedFigure"]}], FontWeight -> "Bold"], None}}, CounterIncrements->"NumberedFigure", FormatTypeAutoConvert->False], Cell[StyleData["NumberedFigure", "Printout"], FontSize->10] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["NumberedTable"], CellMargins->{{55, 145}, {2, 10}}, CellFrameLabels->{{None, None}, {Cell[ TextData[ {"Table ", CounterBox[ "NumberedTable"]}], FontWeight -> "Bold"], None}}, TextAlignment->Center, CounterIncrements->"NumberedTable", FormatTypeAutoConvert->False], Cell[StyleData["NumberedTable", "Printout"], CellMargins->{{18, Inherited}, {Inherited, Inherited}}, FontSize->10] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Formulas and Programming", "Section"], Cell[CellGroupData[{ Cell[StyleData["DisplayFormula"], CellMargins->{{55, 10}, {2, 10}}, CellHorizontalScrolling->True, DefaultFormatType->DefaultInputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, LanguageCategory->"Formula", ScriptLevel->0, SingleLetterItalics->True, UnderoverscriptBoxOptions->{LimitsPositioning->True}], Cell[StyleData["DisplayFormula", "Printout"], FontSize->10] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["ChemicalFormula"], CellMargins->{{55, 10}, {2, 10}}, DefaultFormatType->DefaultInputFormatType, HyphenationOptions->{"HyphenationCharacter"->"\[Continuation]"}, LanguageCategory->"Formula", AutoSpacing->False, ScriptLevel->1, ScriptBaselineShifts->{0.6, Automatic}, SingleLetterItalics->False, ZeroWidthTimes->True], Cell[StyleData["ChemicalFormula", "Printout"], FontSize->10] }, Closed]], Cell[CellGroupData[{ Cell[StyleData["Program"], CellMargins->{{18, 10}, {Inherited, 6}}, Hyphenation->False, LanguageCategory->"Formula", FontFamily->"Courier"], Cell[StyleData["Program", "Printout"], CellMargins->{{18, 30}, {Inherited, 4}}, FontSize->9.5] }, Closed]] }, Closed]] }, Open ]] }] ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1727, 52, 113, 4, 51, "Title"], Cell[1843, 58, 34, 0, 38, "Author"], Cell[1880, 60, 123, 4, 40, "Address"], Cell[CellGroupData[{ Cell[2028, 68, 27, 0, 26, "Section"], Cell[2058, 70, 1391, 24, 202, "Abstract"] }, Open ]], Cell[CellGroupData[{ Cell[3486, 99, 31, 0, 26, "Section"], Cell[3520, 101, 978, 17, 118, "Text"], Cell[4501, 120, 630, 10, 90, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[5168, 135, 35, 0, 26, "Section"], Cell[5206, 137, 299, 9, 37, "Text"], Cell[5508, 148, 299, 7, 48, "Text"], Cell[5810, 157, 392, 10, 48, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[6239, 172, 33, 0, 26, "Section"], Cell[6275, 174, 147, 5, 20, "Text"], Cell[6425, 181, 178, 3, 38, "Input"], Cell[6606, 186, 242, 5, 34, "Text"], Cell[6851, 193, 181, 4, 38, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[7069, 202, 35, 0, 26, "Section"], Cell[7107, 204, 890, 19, 104, "Text"], Cell[CellGroupData[{ Cell[8022, 227, 464, 8, 146, "Input"], Cell[8489, 237, 1001, 15, 172, "Output"] }, Open ]], Cell[9505, 255, 579, 10, 76, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[10121, 270, 37, 0, 26, "Section"], Cell[10161, 272, 517, 16, 48, "Text"], Cell[10681, 290, 826, 30, 76, "Text"], Cell[11510, 322, 192, 4, 51, "Input"], Cell[11705, 328, 383, 12, 48, "Text"], Cell[12091, 342, 200, 4, 64, "Input"], Cell[12294, 348, 111, 3, 20, "Text"], Cell[12408, 353, 383, 6, 90, "Input"], Cell[12794, 361, 490, 11, 62, "Text"], Cell[CellGroupData[{ Cell[13309, 376, 289, 6, 77, "Input"], Cell[13601, 384, 556, 7, 158, "Output"] }, Open ]], Cell[14172, 394, 74, 0, 20, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[14283, 399, 44, 0, 26, "Section"], Cell[14330, 401, 516, 15, 62, "Text"], Cell[CellGroupData[{ Cell[14871, 420, 2369, 33, 428, "Input"], Cell[17243, 455, 38, 1, 28, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[17318, 461, 30, 0, 18, "Subsection"], Cell[17351, 463, 892, 26, 90, "Text"], Cell[18246, 491, 179, 4, 38, "Input"], Cell[18428, 497, 696, 12, 168, "Input"], Cell[CellGroupData[{ Cell[19149, 513, 184, 3, 38, "Input"], Cell[19336, 518, 203, 5, 60, "Output"] }, Open ]], Cell[19554, 526, 565, 15, 62, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[20156, 546, 30, 0, 18, "Subsection"], Cell[20189, 548, 433, 7, 62, "Text"], Cell[20625, 557, 306, 6, 64, "Input"], Cell[20934, 565, 209, 6, 34, "Text"], Cell[21146, 573, 802, 14, 168, "Input"], Cell[CellGroupData[{ Cell[21973, 591, 119, 3, 25, "Input"], Cell[22095, 596, 323, 5, 92, "Output"] }, Open ]], Cell[22433, 604, 163, 5, 20, "Text"], Cell[CellGroupData[{ Cell[22621, 613, 99, 2, 25, "Input"], Cell[22723, 617, 61, 2, 28, "Output"] }, Open ]], Cell[22799, 622, 582, 15, 76, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[23430, 643, 40, 0, 26, "Section"], Cell[23473, 645, 962, 16, 132, "Text"], Cell[CellGroupData[{ Cell[24460, 665, 30, 0, 18, "Subsection"], Cell[24493, 667, 323, 8, 48, "Text"], Cell[24819, 677, 84, 1, 25, "Input"], Cell[24906, 680, 805, 14, 142, "Input"], Cell[25714, 696, 524, 10, 76, "Text"], Cell[26241, 708, 510, 10, 62, "Text"], Cell[26754, 720, 299, 5, 48, "Text"], Cell[CellGroupData[{ Cell[27078, 729, 563, 11, 116, "Input"], Cell[27644, 742, 222, 7, 60, "Output"] }, Open ]], Cell[27881, 752, 156, 4, 34, "Text"], Cell[CellGroupData[{ Cell[28062, 760, 437, 10, 90, "Input"], Cell[28502, 772, 185, 6, 44, "Output"] }, Open ]], Cell[28702, 781, 338, 6, 48, "Text"], Cell[CellGroupData[{ Cell[29065, 791, 169, 3, 38, "Input"], Cell[29237, 796, 187, 3, 60, "Output"] }, Open ]], Cell[29439, 802, 40, 0, 20, "Text"], Cell[CellGroupData[{ Cell[29504, 806, 171, 3, 38, "Input"], Cell[29678, 811, 189, 3, 60, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[29916, 820, 30, 0, 18, "Subsection"], Cell[29949, 822, 1184, 33, 118, "Text"], Cell[31136, 857, 764, 13, 104, "Text"], Cell[31903, 872, 796, 15, 168, "Input"], Cell[32702, 889, 905, 17, 155, "Input"], Cell[33610, 908, 409, 7, 62, "Text"], Cell[CellGroupData[{ Cell[34044, 919, 373, 8, 90, "Input"], Cell[34420, 929, 553, 11, 108, "Output"] }, Open ]], Cell[34988, 943, 348, 12, 34, "Text"], Cell[CellGroupData[{ Cell[35361, 959, 162, 3, 38, "Input"], Cell[35526, 964, 248, 6, 44, "Output"] }, Open ]], Cell[35789, 973, 808, 12, 104, "Text"], Cell[36600, 987, 416, 7, 62, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[37053, 999, 38, 0, 18, "Subsection"], Cell[37094, 1001, 521, 16, 62, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[37664, 1023, 69, 0, 26, "Section"], Cell[37736, 1025, 460, 9, 62, "Text"], Cell[38199, 1036, 171, 4, 34, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[38407, 1045, 42, 0, 26, "Section"], Cell[38452, 1047, 685, 16, 76, "Text"], Cell[39140, 1065, 644, 12, 90, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[39821, 1082, 29, 0, 26, "Section"], Cell[39853, 1084, 189, 6, 28, "Reference"], Cell[40045, 1092, 213, 7, 16, "Reference"], Cell[40261, 1101, 429, 15, 40, "Reference"], Cell[40693, 1118, 239, 7, 40, "Reference"], Cell[40935, 1127, 171, 5, 16, "Reference"], Cell[41109, 1134, 214, 6, 16, "Reference"], Cell[41326, 1142, 221, 7, 28, "Reference"] }, Open ]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)