{ From user David, Model Traveling_salesman at 15-Jan-2013 12:20:37 PM } SoftwareVersion 4.4.5 { System Variables with non-default values: } UseTable := 0 TypeChecking := 1 Checking := 0 SaveOptions := 2 SaveValues := 0 {!40000|Att_ContLineStyle Graph_Primary_Valdim: 4} {!40000|Att_CatLineStyle Graph_Primary_Valdim: 9} {!40300|Sys_DomainSelfIndex := 1} {!40400|Sys_AllNullTreatment := 1} {!40300|ProactivelyEvaluate Index: 1} Attribute UnoptimizedDef Model Traveling_salesman Title: Traveling salesman Description: The traveling salesman problem is a well-known NP-complete problem, meaning that the general problem probably cannot be solved efficiently in all cases. ~ ~ This model contains two formulations of the problem -- one as a non-linear program (NLP) that uses a Grouped Integer decision type to define the space of possible tours. The second as a mixed-integer linear program (MILP). The NLP formulation is very straightforward. The MILP is more challenging, but solves faster and comes with a guarantee that it didn't stop at a local optima.~ ~ The button generates a random collection of cities. Author: Lonnie Chrisman, Ph.D.~ Lumina Decision Systems Date: Tue, Oct 02, 2007 11:08 AM SaveAuthor: David SaveDate: Tue, Jan 15, 2013 12:20 PM DefaultSize: 48,24 DiagState: 2,29,20,619,526,17 WindState: 2,490,197,498,318 FontStyle: Arial, 15 FileInfo: 0,Model Traveling_salesman,2,2,0,0,C:\Documents and Settings\David\Desktop\work\bug reports\12236.ana {!40400|Att_clearTypeFonts: 0} Index City {!40000|Att_PrevIndexValue: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]} Title: City Definition: 1..N NodeLocation: 88,56,1 NodeSize: 48,24 DisplayOutputs: , , , Index To_City {!40000|Att_PrevIndexValue: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]} Title: To City Definition: CopyIndex(City) NodeLocation: 192,56,1 NodeSize: 48,24 Index Lat_long Title: Lat-Long Definition: ['Lat','Long'] NodeLocation: 304,56,1 NodeSize: 48,24 Variable Locations Title: Locations Definition: reset ;random(over:City,Lat_Long) * 100 NodeLocation: 192,120,1 NodeSize: 48,24 ValueState: 2,111,292,687,530,1,MIDM Aliases: Alias Locations2, Alias Locations1 GraphSetup: {!40000|Graph_SymbolKey:1} ReformVal: [City,Undefined] {!40000|Att_XRole: -1} {!40000|Att_YRole: -2} {!40000|Att_SymbolRole: City} {!40000|Att_CoordinateIndex: Lat_long} Variable Distances Title: Distances Definition: sqrt( sum((Locations-Locations[City=To_City])^2, Lat_long) ) NodeLocation: 304,120,1 NodeSize: 48,24 ValueState: 2,64,471,732,263,0,MIDM Aliases: Alias Distances2, Alias Distances1 ReformVal: [To_City,City] Button New_random_cities Title: New random cities NodeLocation: 96,328,1 NodeSize: 80,24 Script: (reset := reset + 1) Variable Reset Definition: 6 NodeLocation: 72,120,1 NodeSize: 48,24 NodeInfo: 1,1,1,1,1,1,0,0,0,0 Variable N Title: Number of cities Definition: 10 NodeLocation: 72,176,1 NodeSize: 48,24 Aliases: FormNode Number_of_cities FormNode Number_of_cities Title: Number of cities Definition: 0 NodeLocation: 128,280,1 NodeSize: 116,13 NodeInfo: 1,0,0,1,0,0,0,72,0,1 Original: N Text Te1 NodeLocation: 148,312,-1 NodeSize: 140,56 NodeInfo: 1,0,0,1,1,1,0,,0, Module MILP_Solution Title: MILP Solution Description: This module formulates the traveling salesman problem as a mixed-integer linear program.~ ~ The linear solution isn't nearly as intuitive as the non-linear one, and was much more difficult to figure out how to do it using only linear operations. However, it has a couple advantages over the NLP formulation. It tends to solve about three times faster, and you can be pretty confident that it will find the global optima, while in the NLP case, there is no way to know that it hasn't stopped with only a local optima. ~ ~ This formulation makes use of two redundant decision variables. Each of these encodes the solution, but in a different fashion, and the constraints serve to make sure they are consistent in the final solution. The first decision, Bool_route, contains a boolean decision for each possible directional link in the tour (either it is in the tour or not). We constrain these values so that each city transitions to exactly one other city, and each city is entered from exact one other city, and you can't stay in the same place.~ ~ With the bool_route alone, we don't exclude the possibility of finding disconnected loops. We need a single loop that visits all the cities. So with the second decision variable, we number the steps in the tour. Using b[x,y] for bool_route from x to y and s[x] for step number of x for shorthand, we want to enforce:~ ~ If b[x,y] then ~ s[y] - s[x] = 1~ ~ { Note: pseudocode, not analytica syntax }~ ~ In other words, as we step through the tour, the step number for the city should increment by one. We want to enforce this for all but the final step in the tour (the final step goes from the last city back to the first -- the first should have already been labelled with 1).~ ~ This constraint as written here isn't linear -- b[x,y] appears in the antecedent. The big trick is figuring out how to encode that in a linear fashion. I was able to find a way to do this by using two constraints (Increment_by_one_lb and Increment_by_one_ub). Together, these constraints enforce something equivalent to what I've written here. Author: Lonnie Chrisman, Ph.D.~ Lumina Decision Systems Date: Fri, Jan 28, 2011 11:46 AM DefaultSize: 48,24 NodeLocation: 304,184,1 NodeSize: 48,24 DiagState: 2,685,19,583,477,17 WindState: 2,40,104,667,564 Library Structured_Opt_Tools Title: Structured Opt Tools Description: Library of functions of use for Structured Optimization models.~ ~ Structured optimization functionality requires Analytica Optimizer. Author: Lonnie Chrisman, Ph.D.~ Lumina Decision Systems Date: Sat, Oct 30, 2010 5:49 PM SaveAuthor: Lonnie SaveDate: Tue, Nov 02, 2010 3:10 PM DefaultSize: 48,24 NodeLocation: 456,416,0 NodeSize: 52,23 NodeInfo: 1,1,1,1,1,1,0,0,0,0 DiagState: 2,334,623,550,181,17 WindState: 2,98,83,476,224 FontStyle: Arial, 15 Function Set_Decisions_To_Opt(optdef : Variable) Title: Set Decisions To Opt Description: Sets the definitions of all the decisions that appear in an Optimization to their optimal solution. This must be called from a Button Script. The parameter, «optdef», must be a variable defined by a call to DefineOptimization.~ ~ This does not preserve the original definitions - see Use_opt_decisions for that.~ This must be run from a button script. Definition: if ParsedExprFunction(fixeddef of optdef)<>Handle(DefineOptimization) then~ Error( "To use " & (identifier of self) & ", " & ~ (identifier of optdef) & ~ " must be defined with DefineOptimization");~ ~ metaindex ds := #ParsedExprParameters(fixeddef of optdef,1);~ var optval := (metavar d[]:=ds do \OptSolution(optdef,d));~ localalias d:=ds do d:=#optval [ds=handle(d)];~ null NodeLocation: 104,64,1 NodeSize: 48,31 WindState: 2,7,197,669,288 Function Use_Opt_Decisions(optdef : Variable) Title: Use Opt Decisions Description: This preserves the original definition (in the event that it isn't already preserved) for each decision node, and then sets each decision to its optimized value.~ ~ This must be used from a button script.~ ~ Optdef must be the variable that is defined using DefineOptimization. Definition: if ParsedExprFunction(fixeddef of optdef)<>handle(DefineOptimization) then~ Error( "To use " & (identifier of self) & ", " & ~ (identifier of optdef) & ~ " must be defined with DefineOptimization");~ metaindex ds := #ParsedExprParameters(fixeddef of optdef,1);~ var optval := (metavar d[]:=ds do \OptSolution(optdef,d));~ localalias d:=ds;~ if IsNull(UnoptimizedDef of d) then ~ UnOptimizedDef of d := Definition of d;~ d:=#optval [ds=handle(d)];~ null~ NodeLocation: 240,64,1 NodeSize: 48,24 WindState: 2,362,110,524,380 Function Restore_Decision_Def(optdef : Variable) Title: Restore Decision Defs Description: This restores all the decisions to their original definitions, after they have previous been set to optimized values with the Use_opt_decisions function.~ ~ This must be used from a button script. Definition: if ParsedExprFunction(fixeddef of optdef)<>handle(DefineOptimization) then~ Error( "To use " & (identifier of self) & ", " & ~ (identifier of optdef) & ~ " must be defined with DefineOptimization");~ ~ metaindex ds := #ParsedExprParameters(fixeddef of optdef,1);~ localalias d:=ds;~ if not IsNull(UnoptimizedDef of d) then (~ Definition of d := UnoptimizedDef of d;~ UnoptimizedDef of d := Undefined~ );~ null NodeLocation: 368,65,1 NodeSize: 48,31 WindState: 2,640,362,554,469 Close Structured_Opt_Tools Button use_solution Title: use solution NodeLocation: 456,352,1 NodeSize: 48,24 Script: Use_opt_decisions(LP) Decision Bool_route Title: Bool route Description: True if the segment from City-->To_City is in the tour (directional) Definition: Table(City,To_City)(~ 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,~ 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,~ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0~ ) NodeLocation: 112,48,1 NodeSize: 48,24 DefnState: 2,180,187,1042,325,0,MIDM ValueState: 2,159,414,768,392,0,MIDM ReformDef: [To_City,City] ReformVal: [To_City,City] Domain: DomDiscreteNumeric {!40300|DomainExpr: Boolean()} Constraint Can_t_step_to_self Title: Can't step to self Definition: Bool_route[To_City=City] = false NodeLocation: 112,120,1 NodeSize: 48,24 Constraint Link_from_every_city Title: Link from every city Definition: Sum(Bool_route,city)=1 NodeLocation: 112,192,1 NodeSize: 48,24 Constraint Link_to_every_city Title: Link to every city Definition: Sum(Bool_route,to_city) = 1 NodeLocation: 112,256,1 NodeSize: 48,24 Objective Tour_dist Title: Tour dist Definition: sum( Bool_route * Distances, City, To_City ) NodeLocation: 240,120,1 NodeSize: 48,24 Variable LP Title: LP Definition: DefineOptimization( ~ Decisions: Bool_route, Step_num, ~ Constraints: Can_t_step_to_self, Link_from_every_city, Link_to_every_city, Increment_by_one_lb, Increment_by_one_ub,~ Minimize: Tour_dist ) NodeLocation: 240,192,1 NodeSize: 48,24 Decision Opt_bool_route Title: Opt bool route Definition: OptSolution(LP,Bool_route) NodeLocation: 360,192,1 NodeSize: 48,24 ValueState: 2,654,38,888,390,0,MIDM ReformVal: [To_City,City] Variable Lp_Tour_order Title: Tour order Definition: Subindex(optsolution(LP,Step_num),City,City) NodeLocation: 472,192,1 NodeSize: 48,24 ValueState: 2,1122,401,351,440,0,MIDM Decision Step_num Title: Step num Description: Represents the step number of each city along the tour. (This is essentially the inverse of the Tour_order used in the NLP formulation).~ ~ A grouped-integer type would work fine here as well (the values will be distinct and from 1..15 in the solution), but that constraint is not necessary. Definition: Table(City)(~ 1,2,3,4,5,6,7,0,0,0,0,0,0,0,0) NodeLocation: 112,328,1 NodeSize: 48,24 WindState: 2,733,100,486,289 Domain: DomDiscreteNumeric {!40300|DomainExpr: Integer(1,N)} Constraint Increment_by_one_lb Title: Increment by one lb Definition: Big*Bool_route[City=All_but_last] - Big +1 <= Step_num[City=To_City] - Step_num[City=All_but_last] NodeLocation: 240,328,1 NodeSize: 48,24 ValueState: 2,72,80,548,230,0,MIDM ReformVal: [To_City,All_but_last] {!40200|OptDimensions: [To_City,All_but_last]} Constant Big Title: Big Definition: 2*size(City) NodeLocation: 112,408,1 NodeSize: 48,24 Constraint Increment_by_one_ub Title: Increment by one ub Description: this pair of constraints enforces the constraint that~ ~ s[y] = s[x] +1~ ~ when b[x,y] is in the route Definition: Step_num[City=To_City] - Step_num[City=All_but_last] <= Big+1 - Big*Bool_route[City=All_but_last] NodeLocation: 240,408,1 NodeSize: 48,24 WindState: 2,663,468,679,224 ValueState: 2,67,349,557,240,0,MIDM ReformVal: [To_City,All_but_last] {!40200|OptDimensions: [To_City,All_but_last]} Index All_but_last Title: All but last Definition: subset(@City