Home

Mosel user guide

1. ct 1 forall a in AREAS do forall s in ct ct NUMSITE a 1 AREA s a ct NUMSITE a end do forall c in CONTR s in SITES PRICE s c gt 0 01 create clean c s Objective Minimize total cost of all cleaning contracts Cost sum c in CONTR s in SITES PRICE s c clean c s Each site must be cleaned by exactly one contractor forall s in SITES sum c in CONTR clean c s 1 Ban same contractor from serving adjacent areas forall c in CONTR a b in AREAS a gt b and ADJACENT a b 1 alloc c a alloc c b lt 1 Specify lower amp upper limits on contracts per area forall a in AREAS LOWCON a 0 sum c in CONTR alloc c a gt LOWCON a forall a in AREAS UPPCON a lt NCONTRACTORS sum c in CONTR alloc c a lt UPPCON a Define alloc c a to be 1 iff some clean c s 1 for sites s in area a forall c in CONTR a in AREAS do alloc c a lt sum s in SITES AREA s a clean c s alloc c a gt 1 0 NUMSITE a sum s in SITES AREA s a clean c s end do forall c in CONTR do forall s in SITES clean c s is_binary forall a in AREAS alloc c a is_binary end do minimize Cost Solve the MIP problem end model In the preceding model we have chosen to implement the constraints that force the variables alloc to become 1 whenever a variable cleans is 1 for some site s in area a in an a
2. Each project starts once and only once forall p in PROJ One p sum m in MONTHS start p m 1 Resource availability A project starting in month m is in its k m 1 st month in month k forall k in MONTHS ResMax k sum p in PROJ m in 1 k RESUSE p k 1 m start p m lt RESMAX k Make all the start variables binary forall p in PROJ m in MONTHS start p m is binary Integer Programming 28 Mosel User Guide maximize MaxBen Solve the MIP problem writeln Solution value is getobjval forall p in PROJ writeln p starts in month getsol sum m in 1 NM DUR p m start p m end model Note that in the solution printout we apply the getsol function not to a single variable but to a linear expression 4 3 The project planning model using Special Ordered Sets The example can be modified to use Special Ordered Sets of type 1 SOS1 The startpm variables for a given p form a set of variables which are ordered by m the month The ordering is induced by the coefficients of the startpm in the specification of the SOS For example start 1 s coefficient 1 is less than start 2 s 2 which in turn is less than start 3 s coefficient and so on The fact that the startpm variables for a given p form a set of variables is specified to Mosel as follows Define SOS 1 sets that ensure that at most one start p m is non zero for each project p Use month index to order the var
3. F_APPEND 56 F_OUTPUT 56 false 31 fclose 56 feasibility tolerance 62 Xpress Mosel User Guide Index file output 56 finalize 44 finalized 23 fixed set 43 flow control 37 fopen 56 forall 12 21 31 39 41 forall do 39 forward 31 51 63 from 31 function 48 function 31 48 getcoeff 52 getobjval 8 getsize 46 getsol 8 29 52 gettype 73 Goal Programming 72 Archimedian 72 lexicographic 72 pre emptive 72 hide constraint 74 if 31 40 if then 37 if then else 40 in 31 46 include 31 index multiple 40 index set 11 13 initialisations 31 initialization array 12 16 set 43 initializations 16 18 23 31 initializations from 16 integer 31 43 integer knapsack problem 67 Integer Programming 29 integer variable 25 inter 31 interrupt loop 42 intersection 45 IP see Integer Programming is_binary 25 31 is_continuous 31 is free 31 is_integer 25 31 is_partint 25 31 is_semcont 26 31 is_semint 26 31 is_sos1 26 29 31 is_sos2 26 31 knapsack problem 10 integer 67 largest common divisor 40 limit see bound linctr 31 43 89 line break 14 Linear Programming 4 29 Linear Programming problem 6 load 8 77 loadprob 83 loop 12 37 39 conditional 40 interrupting 42 nested 42 LP see Linear Programming Mathematical Programming 4 max 31 maximize 83 maximum 38 min 31 minimum 38 MIP see Mixed Integer Prog
4. DSN Excel Files DBO blend x1s SQLexecute select from MyRange COST AVAIL GRADE end model The SQL statement select from MyRange says select everything from the range called MyRange It is possible to have much more complex selection statements than the ones we have used 2 2 4 2 Database example If we use Microsoft Access we might have set up an ODBC DSN called MSAccess and suppose we are extracting data from a table called MyTable in the database blend mdb There are just the four columns ORES columns COST AVAIL and GRADE in MyTable and the data are the same as in the Excel example above We modify the example above to be model Blend 4 uses mmodbc mmxprs declarations REV 125 Unit revenue of product MINGRADE 4 Minimum permitted grade of product MAXGRADE 5 Maximum permitted grade of product ORES 1 2 Range of ores COST array ORES of real Unit cost of ores AVAIL array ORES of real Availability of ores GRADE array ORES of real Grade of ores measured per unit of mass use array ORES of mpvar Quantities of ores used end declarations Read data from database blend mdb SQLconnect DSN Access DBQ blend mdb SQLexecute select from MyTable COST AVAIL GRADE end model To use other databases for instance a mysql database let us call it blend we merely need to modify the connection string provi
5. In the model body the equality sign may only be used in the definition of constraints or in logical expressions Constraints are linear relations between variables but profit has not been defined as a variable so the parser detects an error What we really want is to assign the linear expression 5 small 20 large to Profit For such an assignment we have to use the sign Using just is a very common error 33 Xpress Mosel User Guide As a consequence of this error the linear expression after the equality sign does not have any relevance to the problem that is stated The parser informs us about this fact in the second line it has found a statement with no effect This is not an error that would cause the failure of the compilation taken on its own but simply a warning marked by the w in the error code w 121 that there may be something to look into Since Profit has not been defined it cannot be used in the call to the optimization hence the third error message As we have seen the second and the third error messages are consequences of the first mistake we have made Before looking at the last message that has been displayed we recompile the model with the corrected line Profit 5 small 20 large to get rid of all side effects of this error Unfortunately we still get a few error messages Mosel E 123 at 10 17 of poerror mos maximize is not defined Mosel E 100 at 12 37 of poerror mos Syntax err
6. Procedure hide_a_3 a 15 a 6 9 3 Recursion The following example returns the largest common divisor of two numbers just like the exam ple Lcdiv1 in the previous chapter This time we implement this task using recursive function calls that is from within function 1cdiv we call again function 1cdiv model Lcdiv2 function lcdiv A B integer integer if A B then returned A elif A gt B then returned 1cdiv B A B else returned lcdiv A B A end if end function declarations A B integer end declarations write Enter two integer numbers n A readin A write B readln B writeln Largest common divisor lcdiv A B end model This example uses a simple recursion a subroutine calling itself In Mosel it is also possible to use cross recursion that is subroutine A calls subroutine B which again calls A The only Functions and procedures 50 Mosel User Guide pre requisite is that any subroutine that is called prior to its definition must be declared before itis called by using the forward statement see below 94 forward A subroutine has to be known at the place where it is called in a program In the preceding examples we have defined all subroutines at the start of the programs but this may not always be feasible or desirable Mosel therefore enables the user to declare a subroutine seperately from its definition by using the keyword forward The declaration of of a subroutine sta
7. k Vk MONTHS X Y RESUSE 1 m Startpm lt RESMAX pePROJ m 1 Finally we have to specify that the startpm are binary 0 or 1 variables Vp PROJ m MONTHS startpm 0 1 Note that the start month of a project p is given by NM DUR XO M 5Startom m 1 since if an startpm is 1 the summation picks up the corresponding m 4 2 2 Implementation The model as specified to Mosel is as follows model Pplan uses mmxprs declarations PROJ 1 3 Set of projects NM 6 Time horizon months ONTHS 1 NM Set of time periods months to plan for DUR array PROJ of integer Duration of project p RESUSE array PROJ MONTHS of integer Res usage of proj p in its t th month RESMAX array MONTHS of integer Resource available in month m BEN array PROJ of real Benefit per month once project finished Start array PROJ MONTHS of mpvar 1 if proj p starts in month t else 0 end declarations DUR 3 3 4 RESMAX 5 6 5 5 4 5 BE PLO 12 9 11 2 RESUSE l 3 4 2 RESUSE 2 1 4 1 6 RESUSE 3 1 3 2 1 2 Other RESUSE entries are 0 by default Objective Maximize Benefit If project p starts in month t it finishes in month t DUR p 1 and contributes a benefit of BEN p for the remaining NM t DUR p 1 months MaxBen sum p in PROJ m in 1 NM DUR p BEN p NM m DUR p 1 start p m
8. 46 46 4 gt 7 46 abs 52 addcuts 62 and 31 array 11 declaration 12 dense 81 dynamic 21 23 59 66 initialization 12 16 multi dimensional 12 sparse 81 static 23 array 31 as 31 BIM file 77 binary variable 25 blending constraint 14 boolean 31 43 break 31 42 C interface 77 callback 63 case 31 ceil 65 column see variable column generation 64 comment 6 multiple lines 6 comparison set 46 comparison tolerance 62 compile 8 77 condition 21 37 conditional generation 22 conditional loop 40 constant 11 constant set 43 constraint hide 74 MVLB 60 named 12 non negativity 6 type 73 88 continuation line 14 create 22 cross recursion 50 cut generation 58 cut manager 62 cut manager entry callback 63 cut pool 62 cutting plane method 58 cutting stock problem 65 data sparse format 23 database 17 debugging 33 decision variable 5 see variable array 12 declaration array 12 subroutine 51 declarations 7 31 49 dense 81 deviation variable 73 difference 45 46 diskdata 23 div 31 do 31 dynamic 31 dynamic array 21 23 59 66 dynamic set 43 elif 31 else 31 end 31 end declarations 7 end do 39 end function 48 end initializations 16 end model 7 end procedure 48 enumeration dense array 81 set 80 Sparse array 82 ETC_OUT 56 ETC_SPARSE 56 57 exam 30 exists 21 exportprob 23
9. A end model 56 Mosel User Guide Output File out_1 dat will contain the following MYOUT 2 4 6 12 14 16 22 24 26 If this file contains already a data entry myout it is replaced with this output without modifying or deleting any other contents of this file Otherwise the output is appended at the end of it The nicely formatted output to out_2 dat results in the following A_out 1 and 1 A_out 1 and 2 A_out 1 and 3 A_out 2 and 1 A_out 2 and 2 A_out 2 and 3 A_out 3 and 1 A_out 3 and 2 A out 3 and 3 2 4 mU 12 14 16 22 24 26 The output with diskdata simply prints the contents of the array to out 3 dat with option C C CO PO PO PO rS EF ES WNHRFRWNF WN EE NNNRRROdS DN sos Mos sos oM gt gt ON aA AND Without option ETC_SPARS 2 4 6 12 14 16 22 24 26 ETC_SPARSE each entry is preceded by the corresponding indices 57 E out_3 dat looks as follows Mosel User Guide Chapter 11 More about Integer Programming 11 1 This chapter presents two applications to Mixed Integer Programming of the programming facilities in Mosel that have been introduced in the previous chapters Cut generation 11 1 1 11 1 2 Cutting plane methods add constraints cuts to the problem that cut off parts of the convex hull of the integer solutions thus drawing the solution of the LP relaxation closer to the integ
10. Advanced language features This part takes the reader who wants to use Mosel as a modeling solving and programming en vironment through its powerful programming language facilities The following topics most of which have already shortly been mentioned in the first part are covered in a more detailed way e Selections and loops Chapter 7 e Working with sets Chapter 8 e Functions and procedures Chapter 9 e Output to files and producing formatted output Chapter 10 Whilst the first four chapters in this part present pure programming examples the last two chapters contain some advanced examples of LP and MIP that make use of the programming facilities in Mosel e Cut generation Section 11 1 e Column generation Section 11 2 e Recursion or Successive Linear Pogramming Section 12 1 e Goal Programming Section 12 2 36 Xpress Mosel User Guide Chapter 7 Flow control constructs 7 1 Flow control constructs are mechanisms for controlling the order of the execution of the ac tions in a program In this chapter we are going to have a closer look at two fundamental types of control constructs in Mosel selections and loops Frequently actions in a program need to be repeated a certain number of times for instance for all possible values of some index or depending on whether a condition is fulfilled or not This is the purpose of loops Since in practical applications loops are often interwoven with conditions selection s
11. Boxwood small 3 large lt 200 maximize Profit writeln Solution n Objective getobjval writeln DescrV small getsol small writeln DescrV large getsol large end model The reader may have already remarked another feature that is illustrated by this example the indexing set Allvars is of type mpvar So far only basic types have occurred as index set types but as mentioned earlier sets in Mosel may be of any elementary type including the MP types mpvar and linctr 8 2 Working with sets Sets In all examples of sets given so far sets are used for indexing other modeling objects But they may also be used for different purposes The following example demonstrates the use of basic set operations in Mosel union inter section and difference model Set example declarations Cities rome bristol london paris liverpool Ports plymouth bristol glasgow london calais liverpool Capitals rome london paris madrid berlin end declarations Places Cities Ports Capitals Create the union of all 3 sets In all three Cities Ports Capitals Create the intersection of all 3 sets Cities not cap Cities Capitals Create the set of all cities that are not capitals writeln Union of all places Places writeln Intersection of all three In all three writeln Cities that are not capitals Cities not cap end model Th
12. COST array ORES of real Unit cost of ores AVAIL array ORES of real Availability of ores GRADE array ORES of real Grade of ores measured per unit of mass use array ORES of mpvar Quantities of ores used end declarations Read data from file initializations from DATAFIL COST AVAIL a Some illustrative examples 16 Mosel User Guide GRADE end initializations end model The parameter DATAFILE is recognized as a string and its default value is specified If we have previously compiled the model into say blend2 bim then the command mosel c load blend2 run DATAFILE blend2 dat will read the cost data from the file we want Or to compile load and run the model using a single command exec blend2 DATAFILE blend2 dat mosel c 2 2 4 Reading data from spreadsheets and databases It is quite easy to create and maintain data tables in text files but in many industrial applications data are provided in the form of spreadsheets or need to be extracted from databases So there is a facility in Mosel whereby the contents of ranges within spreadsheets may be read into data tables and databases may be accessed It requires an additional authorization in your Xpress MP license On the Dash website separate documentation is provided for the SQL ODBC interface Mosel module mmodbc To give you a flavor of how Mosel s SQL interface may be used we now read the data of the blending prob
13. Objective 280 x camera 1 Some illustrative examples 13 Mosel User Guide x necklace 1 x vase 1 x picture 1 x tv 0 x video 1 x chest 0 x brick 0 e Continuation lines Notice that the statement ITEMS camera necklace vase picture tv video chest brick was spread over two lines Mosel is smart enough to recognize that the statement is not complete so it automatically tries to continue on the next line If you wish to extend a single statement to another line just cut it after a symbol that implies a continuation like an operator lt or a comma in order to warn the analyzer that the expression continues in the following line s For example ObjMax sum i in Irange j in Jrange TAB i j x i j sum i in Irange TIB i delta i sum j in Jrange TUB j phi j Conversely it is possible to place several statements on a single line separating them by semicolons like x1 lt 4 x2 gt 7 2 2 A blending example A mining company has two types of ore available Ore 1 and Ore 2 The ores can be mixed in varying proportions to produce a final product of varying quality For the product we are interested in the grade a measure of quality of the final product must lie between the specified limits of 4 and 5 It sells for REV 125 per ton The costs of the two ores vary as do their availabilities The objective is to maximize the total net pro
14. forall i in 1 10 j in 1 10 y i j is binary where y i 3 are variables of type mpvar the following equivalent short form may be used forall i j in 1 10 y i j is binary 7 2 1 2 Conditional looping The possibility of adding conditions to a forall loop via the symbol has already been men tioned in Chapter 3 Conditions may be applied to one or several indices and the selection statement s can be placed accordingly Take a look at the following example where A and U are one and two dimensional arrays of integers or reals respectively and y a two dimensional array of decision variables mpvar forall i in 10 10 j in 0 5 A i gt 20 y i j lt U 1 J For all i from 10 to 10 the upper bound U i 3 is applied to the variable y i 3 if the value of A i is greater than 20 The same conditional loop may be reformulated in an equivalent but usually less efficient way using the if statement forall i in 10 10 J in 0 5 if A i 20 vit lt U i j end if If we have a second selection statement on both indices with B a two dimensional array of integers or reals we may either write forall i in 10 10 j in 0 5 A i gt 20 and B i j lt gt 0 y i j lt U i j or more efficiently since the second condition on both indices is only tested if the condition on index i holds forall i in 10 10 A i gt 20 j in 0 5 B 1 3 lt gt 0 y i j lt U i j 7 2 2 while
15. 2 i 1 inDev dev 2 i dev 2 i 1 end do else writeln Wrong constraint type break end case Goal 1 Deviation minimize MinDev writeln Solution Extensions to Linear Programming i Solve the LP problem x getsol x y getsol y 73 Mosel User Guide if getobjval 0 then writeln Cannot satisfy goal i break end if Goal i Deviation Remove deviation variable s from goal end do print_sol i Solution printout end procedure The procedure sethidden c linctr b boolean has already been used in the previous chapter Section 11 2 without giving any further explanation With this procedure constraints can be removed hidden from the problem solved by the optimizer without deleting them in the problem definition So effectively the optimizer solves a subproblem of the problem originally stated in Mosel To complete the model below is the procedure print sol for printing the results procedure print sol i integer declarations STypes CT GEO CT LEO CT EQ ATypes array STypes of string end declarations ATyp S gt n We t writeln Goal strfmt Target 11 strfmt Value 7 forall g in 1 i writeln strfmt g 4 strfmt ATypes gettype Goal g 4 strfmt getcoeff Goal g 6 strfmt getact Goal g getsol dev 2 g getsol dev 2 g 1 8 forall g in 1 NGOALS if getsol dev 2 g gt 0 then write
16. 4 of Mosel it becomes possible to redirect the BIM file that is generated by the compilation Instead of writing it out to a physical file it may for instance be kept in memory or be written out in compressed format The interested reader is refered to the whitepaper Generalized file handling in Mosel 13 1 2 Executing a model in C The example in this section shows how a Mosel binary model file BIM can be executed in C The BIM file can of course be generated within the same program where it is executed 77 Xpress Mosel User Guide but here we leave out this step A BIM file is an executable version of a model but it does not include any data that is read in by the model from external files It is portable that is it may be executed on a different type of architecture than the one it has been generated on A BIM file produced by the Mosel compiler first needs to be loaded into Mosel function xPRMloadmod and can then be run by a call to function xPRMrunmod To use these functions we need to include the header file xoxm rt h at the beginning of our program include lt stdio h gt include xprm_rt h int main XPRMmodel mod int result iff XPRMinit Initialize Mosel return 1 if mod XPRMloadmod burglar2 bim NULL NULL Load a BIM file return 2 if XPRMrunmod mod amp result NULL Run the model return 3 return 0 The compile load run sequence may also be performed with a
17. 5RX UK For the latest news and Xpress MP software and documentation updates please visit the Xpress MP website at http www dashoptimization com or subscribe to our mailing list Contents Using the Mosel language 1 Introduction 2 What you need to know before using Mosel o o eee 2 Symbols and conventions c lll 3 The structure Of this guide 2 22 llle 4 1 Getting started with Mosel 5 1 1 The chess set problem description e ee 5 1 4 1 Afirst formulation lt e lt a axa caa ee Redon bee bob eee D a 5 1 2 Solving the chess set problem ce mm 6 1 2 1 Building the model 2 2 mx a 6 1 2 2 Obtaining a solution using Mosel anaana aaa aa 7 1 2 3 Running Mosel from a command line 8 124 Using Apress iVE oe ee eee eee Le ee EPP a 9 2 Some illustrative examples 10 2 1 The burglar problem o oo e 10 2 1 1 Model formulation 2 2 0 0 685 2 eee a a bee ee m 10 2 1 2 Implementation aaa aa a a 10 2 1 3 The burglar problem revisited a 13 2 2 Ablendingexample lll 14 2 41 Model formulation o a 14 2 22 limplementati tl 2 2 noe De eee ee m E E ox X RE R 9ORCRO3 3 kx x7 15 2 43 Re running the model with newdata rn 16 2 2 4 Reading data from spreadsheets and databases 17 2 2 4 4 Spreadsheet example ls 17 2 2
18. Get the number of dimensions of the array indices int malloc dim sizeof int sets XPRMset malloc dim sizeof XPRMset XPRMgetarrsets varr sets Get the indexing sets XPRMgetfirstarrtruentry varr indices Get the first true index tuple 81 Mosel User Guide 13 3 4 C interface do printf flow for i 0 i lt dim 1 i printf Ss XPRMgetelsetval sets i indices i amp rvalue gt string printf s XPRMgetelsetval sets dim 1 indices dim 1 amp rvalue string while XPRMgetnextarrtruentry varr indices Get next true index tuple printf in free sets free indices return 0 In this example we first get the number of indices dimensions of the array of variables varr using function XPRMgetarrdim We use this information to allocate space for the arrays sets and indices that will be used to store the indexing sets and single index tuples for this array respectively We then read the indexing sets of the array function XPRMgetarrsets to be able to produce a nice printout The enumeration starts with the first defined index tuple obtained with function XPRMget firstarrtruentry and continues with a series of calls to XPRMgetnextarrt ruent ry until all defined entries have been enumerated Problem solving in C with Xpress Optimizer In certain cases for instance if the user wants to re use parts of algorithms that he has written in
19. Index sets may also be initialized indirectly during the initialization of dynamic arrays declarations REGION set of string DEMAND array REGION of real end declarations initializations from transprt dat DEMAND end initilizations If file transprt dat contains the data DEMAND Scotland 2840 North 2800 West 2600 SEast 2820 Midlands 2750 then printing the set REGION after the initialization will give the following output Scotland North West SEast Midlands Once a set is used for indexing an array of data decision variables etc it is fixed that is its elements can no longer be removed but it may still grow in size The indirect initialization of index sets is not restricted to the case that data is input from file In the following example we add an array of variable descriptions to the chess problem introduced in Chapter 1 These descriptions may for instance be used for generating a nice output Since the array DescrV and its indexing set Allvars are dynamic they grow with each new variable description that is added to Descrv model Chess 3 uses mmxprs declarations Allvars set of mpvar DescrV array Allvars of string small large mpvar end declarations DescrV small Number of small chess sets DescrV large Number of large chess sets Profit 5 small 20 large 44 Mosel User Guide Lathe 3 small 2 large lt 160
20. Shell sort algorithm for sorting an array of numbers into numerical order The idea of this algorithm is to first sort by straight insertion small groups of numbers Then several small groups are combined and sorted This step is repeated until the whole list of numbers is sorted The spacings between the numbers of groups sorted on each pass through the data are called the increments A good choice is the sequence which can be generated by the recurrence inci 1 ince 3 inc 1 k21 2 model Shell sort declarations N integer Size of array ANum ANum array range of real Unsorted array of numbers end declarations N 50 forall i in 1 N ANum i round random 100 writeln Given list of numbers size N forall i in 1 N write ANum i writeln inc 1 Determine the starting increment repeat inc 3 inc 1 until inc gt N repeat Loop over the partial sorts inc inc div 3 forall i in inc 1 N do Outer loop of straight insertion v ANum i j i while ANum j inc gt v do Inner loop of straight insertion ANum j ANum j inc j inc if j inc then break end if end do ANum 3 v end do until inc lt 1 Flow control constructs 41 Mosel User Guide writeln Ordered list forall i in 1 N write ANum i writeln end model The example introduces a new statement break It can be used to interrupt one or several loops In our case it stops the inner while loop Since we
21. and large can take will always be constrained by some physical or technological limits they may be constrained to be equal to less than or greater than some constant In our case we note that the joinery has a maximum of 160 hours of machine time available per week Three hours are needed to produce each small chess set and two hours are needed to produce each large set So the number of hours of machine time actually used each week is 3 small 2 large One constraint is thus 3 small 2 large lt 160 lathe hours 5 Xpress Mosel User Guide which restricts the allowable combinations of small and large chess sets to those that do not exceed the lathe hours available In addition only 200 kg of boxwood is available each week Since small sets use 1 kg for every set made against 3 kg needed to make a large set a second constraint is 1 small 3 large lt 200 kg of boxwood where the left hand side of the inequality is the amount of boxwood we are planning to use and the right hand side is the amount available The joinery cannot produce a negative number of chess sets so two further non negativity constraints are small gt 0 large gt 0 In a similar way we can write down an expression for the total profit Recall that for each of the large chess sets we make and sell we get a profit of 20 and one of the small chess set gives us a profit of 5 The total profit is the sum of the individual profits from making and
22. are jumping out of a single loop we could as well write break 1 If we wrote break 3 the break would make the algorithm jump 3 loop levels higher that is outside of the xepeat until loop Note that there is no limit to the number of nested levels of loops and or selections in Mosel Flow control constructs 42 Mosel User Guide Chapter 8 Sets A set collects objects of the same type without establishing an order among them as is the case with arrays In Mosel sets may be defined for all elementary types that is the basic types integer real string boolean and the MP types mpvar and linct y This chapter presents in a more systematic way the different possibilities how sets may be initialized all of which the reader has already encountered in the examples in the first part and shows also more advanced ways of working with sets 8 1 Initializing sets In the revised formulation of the burglar problem in Chapter 2 and also in the models in Chapter 3 we have already seen different examples for the use of index sets We recall here the relevant parts of the respective models 8 1 1 Constant sets In the Burglar example the index set is assigned directly in the model declarations ITEMS camera necklace vase picture tv video chest brick end declarations Since in this example the set contents is set in the declarations section the index set ITEMS is a constant set its contents cannot be c
23. are taken into account However if the sums involve exactly the index sets that have been used in the declaration of the variables here this is the case for the objective function MinCost adding the existence test helps to speed up the enumeration of the existing index tuples The following section introduces the conditional generation in a more systematic way More advanced modeling features 21 Mosel User Guide 3 2 Conditional generation the operator Suppose we wish to apply an upper bound to some but not all members of a set of variables x There are MAXI members of the set The upper bound to be applied to x is U but it is only to be applied if the entry in the data table TAB is greater than 20 If the bound did not depend on the value in TAB then the statement would read forall i in 1 MAXI x i lt U i Requiring the condition leads us to write forall i in 1 MAXI TAB i gt 20 x i lt U i The symbol can be read as such that or subject to Now suppose that we wish to model the following MAXI 3 Xj X 15 i 1 Aj gt 20 In other words we just want to include in a sum those x for which A is greater than 20 This is accomplished by CC sum i in 1 MAXI A i gt 20 x i lt 15 3 2 1 Conditional variable creation and create As we have already seen in the transport example Section 3 1 with Mosel we can condition ally create variables In this section we show a few more examples Su
24. at the beginning of period t We now also replace the balance balance in the product with dx by a guess By_ and a deviation db _ iinterest 92 365 balances 4 X Bi 4 dbi 4 dx 92 365 balance 4 X B _1 dx db _ dx which can be approximated by dropping the product of the deviation variables interest 92 365 balances 4 X Bri dx To ensure feasibility we add penalty variables ep us and eminus for positive and negative deviations in the formulation of the constraint interest 92 365 balance _ X B _1 dx eplus eminus The objective of the problem is to get feasible that is to minimize the deviations minimize Y eplus eminus tc QUARTERS Implementation The Mosel model then looks as follows note the balance variables balance as well as the deviation dx and the quarterly nets net are defined as free variables that is they may take any values between minus and plus infinity model Recurse uses mmxprs forward procedure solve_recurs declarations T 6 Time horizon QUARTERS 1 T Range of time periods P R V array QUARTERS of real Payments B array QUARTERS of real Initial guess as to balances b t X real Initial guess as to interest rate x interest array QUARTERS of mpvar Interest net array QUARTERS of mpvar Net balance array QUARTERS of mpvar Balance x mpvar Interest rate dx mpvar Chang
25. break 2 end if 61 Mosel User Guide 11 1 5 11 1 6 writeln Pass npass gettime starttime sec objective value objval cuts added npcut total ncut if npcut 0 then break else loadprob Cost Reload the problem loadbasis 1 Load the saved basis end if end do Display cut generation status write Cut phase completed if ncut gt MAXCUTS then writeln space for cuts exhausted elif npass gt MAXPASS then writeln maximum number of passes reached else writeln no more violations or no improvement to objective end if end procedure Assuming we add the definition of procedure top cut gen to the end of our model we need to add its declaration at the beginning of the model forward procedure topcutgen and the call to this function immediately before the optimization top cut gen Constraint generation at top node minimize Cost Solve the MIP problem Since we wish to use our own cut strategy we switch off the default cut generation in Xpress Optimizer setparam XPRS_CUTSTRATEGY 0 We also turn the presolve off since we wish to access the solution to the original problem after solving the LP relaxations setparam XPRS_PRESOLVE 0 Comparison tolerance In addition to the parameter settings we also retrieve the feasibility tolerance used by Xpress Optimizer the Optimizer works with tolerance values for integer feasibility and solution fe
26. constraint type obtained with gettype of the goals we need one for inequalities or two for equalities deviation variables Let us have a closer look at the first goal Goa a gt constraint the left hand side all terms with decision variables must be at least 40 to satisfy the constraint To ensure this we add a dev The goal constraint becomes 7 x 3 y dev gt 40 and the objective function is to minimize dev If this is feasible 0 valued objective then we remove the deviation variable from the goal thus turning it into a hard constraint It is not required to remove it from the objective since minimization will always force this variable to take the value 0 We then continue with Goah since this is an equation we need variables for positive and negative deviations dev and dev4 We add dev dev to the constraint turning it into 10 x 5 y dev dev 60 and the objective now is to minimize the absolute deviation dev dev3 And so on procedure preemptiv Remove hide forall i in 1 NGOALS i 0 while xu sethidden Goal i 1 lt NGOALS do false case gettype Goal i of goal constraint from the problem sethidden Goal 1 true Add unhide th next goal Add deviation variable s CT_GEQ do Deviation dev 2 1 inDev Deviation end do CT_LEQ do Deviation dev 2 i 1 inDev dev 2 i 1 end do CT BO do Deviation dev 2 i dev
27. exists Mosel closely mimics the mathematical notation an analyst uses to describe a problem So provided you are happy using the above mathematical notation the step to using a modeling language will be straightforward Symbols and conventions We have used the following conventions within this guide e Mathematical objects are presented in italics Examples of commands models and their output are printed in a Courier font File names are given in lower case Courier Decision variables have lower case names in the most example problems these are verbs such as use take Constraint names start with an upper case letter followed by mostly lower case e g Profit TotalCost Data arrays and sets and constants are written entirely with upper case e g DEMAND COST ITEMS The vertical bar symbol is found on many keyboards as a vertical line with a small gap in the middle but often confusingly displays on screen without the small gap In the UNIX world it is referred to as the pipe symbol Note that this symbol is not the same as the character sometimes used to draw boxes on a PC screen In ASCII the symbol is 7C in hexadecimal 124 in decimal Introduction 3 Mosel User Guide The structure of this guide This user guide is structured into these main parts Part describes the use of Mosel for people who want to build and solve Mathematical Programming MP problems These will typically be Linear Progr
28. if XPRSgetintattrib prob XPRS COLS amp ncol return 9 if sol double malloc ncol sizeof double NULL return 10 if XPRSgetsol prob sol NULL NULL NULL return 11 Get the primal solution values if XPRSgetintattrib prob XPRS NAMELENGTH amp len return 11 Get the maximum name length if names char malloc len 8 1 ncol sizeof char NULL return 12 if XPRSgetnames prob 2 names 0 ncol 1 return 13 Get the variable names for i 0 i lt ncol i Print out the solution printf Ss Sg n names len 8 1 1 sol i 83 Mosel User Guide free names free sol return 0 Since the Mosel language provides ample programming facilities in most applications there will be no need to switch from the Mosel language to problem solving in C If nevertheless this type of implementation is chosen it should be noted that it is not possible to get back to Mosel once the Xpress Optimizer has been called directly from C the solution information and any possible changes made to the problem directly in the optimizer are not communicated to Mosel C interface 84 Mosel User Guide Chapter 14 Other programming language interfaces In this chapter we show how the examples from Sections 13 1 and 13 2 may be written with other programming languages namely Java and Visual Basic 14 1 Java To use the Mosel Java classes th
29. left justified print ing positive right justified When writing a real a third argument may be used to specify the maximum number of digits after the decimal point For example if file o mos contains model FO parameters r 1 0 A real i 0 An integer end parameters writeln i is i writeln i is strfmt i 6 writeln i is strfmt i 6 writeln r is r i r writeln r is strfmt r 6 r is strfmt r 10 4 l and we run Mosel thus mosel s c exec fo i 123 r 1 234567 we get output is 123 is 123 zs 123 is 1 23457 is 1 23457 is 1 2346 ROR K b H H The following example prints out the solution of model Transport Section 3 1 in table for mat The reader may be reminded that the objective of this problem is to compute the product flows from a set of plants PLANT to a set of sales regions REGION so as to minimize the total cost The solution needs to comply with the capacity limits of the plants PLANTCAP and satisfy the demand DEMAND of all regions 54 Xpress Mosel User Guide procedure print_table declarations rsum array psum prsum c end declarati Prin writeln nPr t heading and the first line of the tabl oduct Distribution n t writeln strfmt Sales Region 44 write strfmt ww 14 forall r in REGION write strfmt r 9 writeln strfmt TOTAL 9 Prin cale ct 0 forall p in P ct 1
30. of constraints to formulate the problem 1 Each site must be cleaned by exactly one contractor Vs SITES 5 cleans 1 ce CONTR 58 Xpress Mosel User Guide 2 Adjacent areas must not be allocated to the same contractor Vc CONTR a b AREAS a gt b and ADJACENT a b 2 1 allOcea alloc lt 1 3 The lower and upper limits on the number of contractors per area must be respected Va AREAS 5 alloc gt LOWCON cE CONTR va AREAS X allocca lt UPPCON CECONTR To express the relation between the two sets of variables we need more constraints a contrac tor c is allocated to an area a if and only if he is allocated a site s in this area that is Yca is 1 if and only if some xq for a site s in area a is 1 This equivalence is expressed by the following two sets of constraints one for each sense of the implication AREA is the area a site s belongs to and NUMSITE the number of sites in area a Vc CONTR a AREAS allocca lt 5 cleanes SESITES AREAs a 1 D Vc CONTR a AREAS alloca gt NUMSITE 5 cleang SESITES AREAs a 11 1 3 Implementation The resulting Mosel program is the following The variables clean s are defined as a dynamic array and are only created if contractor c bids for site s that is PRICE gt 0 or taking into account inaccuracies in the data PRICE gt 0 01 Another implementation detail that the reader may notice is the separate initia
31. orders The rolls can be cut into NWIDTHS different sizes The orders are given as demands for each width i DEMAND The objective of the paper mill is to satisfy the demand with the smallest possible number of paper rolls in order to minimize the losses Model formulation The objective of minimizing the total number of rolls can be expressed as choosing the best set of cutting patterns for the current set of demands Since it may not be obvious how to calculate More about Integer Programming 64 Mosel User Guide 11 2 3 all possible cutting patterns by hand we start off with a basic set of patterns PATTERNS PATTERNS ywiorm that consists of cutting small rolls all of the same width as many times as possible out of the large roll This type of problem is called a cutting stock problem If we define variables use to denote the number of times a cutting pattern j j WIDTHS 1 NWIDTH is used then the objective becomes to minimize the sum of these variables subject to the constraints that the demand for every size has to be met minimize X use jeWIDTHS Y PATTERNS use gt DEMAND jeWIDTHS Vj WIDTHS use lt ceil DEMAND PATTERNS use integer Function ceil means rounding to the next larger integer value Implementation The first part of the Mosel model implementing this problem looks as follows model Papermill uses mmxprs forward procedure column_gen forward function knapsack C array
32. partint 5 Integer up to 5 then continuous 25 Xpress Mosel User Guide Semi continuous variables decision variables that can take either the value 0 or a value between some lower limit and upper limit Semi continuous variables help model situa tions where if a variable is to be used at all it has to be used at some minimum level x 2 is_semcont 6 A hole between 0 and 6 then continuous Semi continuous integer variables decision variables that can take either the value 0 or an integer value between some lower limit and upper limit Semi continuous integer variables help model situations where if a variable is to be used at all it has to be used at some minimum level and has to be integer x 3 is_semint 7 A hole between 0 and 7 then integer Special Ordered Sets of type one SOS1 an ordered set of variables at most one of which can take a non zero value Special Ordered Sets of type two SOS2 an ordered set of variables of which at most two can be non zero and if two are non zero these must be consecutive in their ordering If the coefficients in the WEIGHT array determine the ordering of the variables we might form a SOS1 or SOS2 set MYSOS by MYSOS sum i in IRng WEIGHT i x i is_sosX where is_sosX is either is sosi for SOS1 sets or is sos2 for SOS2 sets Alternatively if the set s holds the members of the set and the linear constraint L contains the set variables coefficients used in ord
33. range of real A array range of real B real xbest array range of integer pass integer real forward procedure show new pat dj real vx array range of integer declarations NWIDTHS 5 Number of different widths WIDTHS 1 NWIDTHS Range of widths RP range Range of cutting patterns AXWIDTH 94 Maximum roll width EPS le 6 Zero tolerance WIDTH array WIDTHS of real Possible widths DEMAND array WIDTHS of integer Demand per width PATTERNS array WIDTHS WIDTHS of integer Basic cutting patterns use array RP of mpvar Rolls per pattern soluse array RP of real Solution values for variables use Dem array WIDTHS of linctr Demand constraints MinRolls linctr Objective function KnapCtr KnapObj linctr Knapsack constrainttobjective x array WIDTHS of mpvar Knapsack variables end declarations WIDTH 17 21 22 5 24 29 5 DEMAND 150 96 48 108 227 Make basic patterns forall j in WIDTHS PATTERNS 3 3 floor MAXWIDTH WIDTH j forall j in WIDTHS do create use 3 Create NWIDTHS variables use use j is_integer Variables are integer and bounded use j lt integer ceil DEMAND 3 PATTERNS j 3 end do MinRolls sum j in WIDTHS use j Objective minimize no of rolls More about Integer Programming 65 Mosel User Guide forall i in WIDTHS Satisfy all demands Dem i sum j in WIDTHS PATTERNS i j us
34. readable output The following C program reads in the Mosel model and solves the problem by direct calls to Xpress Optimizer To be able to address the problem loaded into the optimizer we need to retrieve the optimizer problem pointer from Mosel Since this information is a parameter XPRS_PROBLEM that is provided by module mmxprs we first need to obtain the reference of this library by using function XPRMfinddso tinclude lt stdio h gt tinclude xprm_rt h tinclude xprs h int main PRMmodel mod PRMdsolib dso PRSprob prob nt result ncol len i ouble sol val har names QQ H X K if XPRMinit Initialize Mosel return 1 if mod XPRMloadmod burglar4 bim NULL NULL Load a BIM file return 2 if XPRMrunmod mod amp result NULL Run the model no optimization return 3 Retrieve the pointer to the problem loaded in the Xpress Optimizer if dso XPRMfinddso mmxprs NULL return 4 if XPRMgetdsoparam mod dso XPRS PROBLEM amp result XPRMalltypes amp prob return 5 if XPRSmaxim prob g Solve the problem return 6 if XPRSgetintattrib prob XPRS MIPSTATUS amp result return 7 Test whether a solution is found if result 4 result 6 if XPRSgetdblattrib prob XPRS_MIPOBJVAL amp val return 8 printf Objective value g n val Print the objective function value
35. selling the small small sets and the large large sets i e Profit 5 small 20 large Profit is the objective function a linear function which is to be optimized that is maximized In this case it involves all of the decision variables but sometimes it involves just a subset of the decision variables In maximization problems the objective function usually represents profit turnover output sales market share employment levels or other good things In minimization problems the objective function describes things like total costs disruption to services due to breakdowns or other less desirable process outcomes The collection of variables constraints and objective function that we have defined are our model It has the form of a Linear Programming problem all constraints are linear equations or inequalities the objective function also is a linear expression and the variables may take any non negative real value 1 2 Solving the chess set problem 1 2 1 Building the model The Chess Set problem can be solved easily using Mosel The first stage is to get the model we have just developed into the syntax of the Mosel language Remember that we use the nota tion that items in italics for example small are the mathematical variables The corresponding Mosel variables will be the same name in non italic courier for example sma11 We illustrate this simple example by using the command line version of Mosel The model ca
36. set of months to plan for The data are DURp the duration of project p RESUSEp the resource usage of project p in its t month RESMAXm the resource available in month m BEN the benefit per month when project finishes We introduce the binary decision variables startpm that are 1 if project p starts in month m and 0 otherwise The objective function is obtained by noting that the benefit coming from a project only starts to accrue when the project has finished If it starts in month m then it finishes in month m DUR 1 So in total we get the benefit of BEN for NM mx DUR 1 NU m DURp 1 months We must consider all the possible projects and all the starting months that let the project finish before the end of the planning period For the project to complete it must start no later than month NM DUR Thus the profit is NM DUR Y Y BEN NM m DUR 1 startom pcPROJ m 1 Each project must be done once so it must start in one of the months 1 to NM DUR Vp PROJ M start z 1 mcMONTHS We next need to consider the implications of the limited resource availability each month Note that if a project p starts in month m it is in its k m 1 month in month k and so will be using RESUSE m4 units of the resource Adding this up for all projects and all starting Integer Programming 27 Mosel User Guide months up to and including the particular month k under consideration gives
37. single function call to XPRMex ecmod in this case we need to include the header file xprm_mc h tinclude lt stdio h gt include xprm_mc h int main int result if XPRMinit Initialize Mosel return 1 Execute compile load run a model if XPRMexecmod NULL burglar2 mos NULL amp result NULL return 2 return 0 13 2 Parameters In Part the concept of parameters in Mosel has been introduced when a Mosel model is executed from the command line it is possible to pass new values for its parameters into the model The same is possible with a model run in C If for instance we want to run model Prime from Section 8 2 to obtain all prime numbers up to 500 instead of the default value 100 set for the parameter LIMIT in the model we may start a program with the following lines XPRMmodel mod int result if XPRMinit Initialize Mosel return 1 C interface 78 Mosel User Guide if mod XPRMloadmod prime bim NULL NULL Load a BIM file return 2 if XPRMrunmod mod amp result LIMIT 500 Run the model return 3 To use function XPRMexecmod instead of the compile load run sequence we have int result if XPRMinit Initialize Mosel return 1 Execute with new parameter settings if XPRMexecmod NULL prime mos LIMIT 500 amp result NULL return 2 13 3 Accessi
38. that it must be integral too Special Ordered Sets of type 1 are often used in modeling choice problems where we have to select at most one thing from a set of items The choice may be from such sets as the time period in which to start a job one of a finite set of possible sizes for building a factory which machine type to process a part on Special Ordered Sets of type 2 are typically used to model non linear functions of a variable They are the natural extension of the concepts of Separable Programming but when embedded in a Branch and Bound code see below enable truly global optima to be found and not just local optima A local optimum is a point where all the nearest neighbors are worse than it but where we have no guarantee that there is not a better point some way away A global optimum is a point which we know to be the best In the Himalayas the summit of K2 is a local maximum height whereas the summit of Everest is the global maximum height Theoretically models that can be built with any of the entities we have listed above can be modeled solely with binary variables The reason why modern IP systems have some or all of the extra entities is that they often provide significant computational savings in computer Integer Programming 26 Mosel User Guide time and storage when trying to solve the resulting model Most books and courses on Integer Programming do not emphasize this point adequately We have found that careful use of
39. the following steps e get the solution values e identify violated inequalities and add them to the problem It is implemented as follows we restrict the generation of cuts to the first three levels i e depth 4 ofthe search tree function cb node boolean declarations ncut integer Counters for cuts cut array range of linctr LI Cuts cutid array range of integer Cut type identification type array range of integer Cut constraint type end declarations returned fals Call this function once per node depth getparam XPRS NODEDEPTH node getparam XPRS NODES if depth 4 then ncut 0 Get the solution values setparam XPRS_SOLUTIONFILE 0 forall c in CONTR do More about Integer Programming 63 Mosel User Guide 11 2 forall a in AREAS sola c a getsol alloc c a forall s in SITES solc c s getsol clean c s end do setparam XPRS_SOLUTIONFILE 1 Search for violated constraints forall c in CONTR s in SITES if solc c s gt sola c AREA s then cut ncut alloc c AREA s clean c s cutid ncut 1 type ncut CT_GEO ncut 1 end if Add cuts to the problem if ncut gt 0 then returned true Call this function again addcuts cutid type cut writeln Cuts added ncut depth depth node node obj getparam XPRS LPOBJVAL end if end if end function The prototype of this function is pres
40. vbNullString If ret lt gt 0 Then sgBox Execution error amp ret Exit Sub End If End Sub 14 2 2 Parameters When executing a Mosel model in Visual Basic it is possible to pass new values for its param eters into the model The following program extract shows how we may run model Prime from Section 8 2 to obtain all prime numbers up to 500 instead of the default value 100 set for the parameter LIMIT in the model We use a slightly modified version prime3 mos of the model where we have redirected the output printing to the file prime out txt Private Sub prime Click Dim model As Long Dim ret As Long Dim result As Long Initialize Mosel ret XPRMinit If ret lt gt 0 Then sgBox Initialization error amp ret amp Exit Sub End If Compile prime3 mos ret XPRMcompmod vbNullString prime3 mos vbNullString Prime numbers If ret 0 Then sgBox Compile error amp ret amp Exit Sub End If Load prime3 bim model XPRMloadmod prime3 bim vbNullString If model 0 Then sgBox Error loading model Exit Sub End If Run model with new parameter settings ret XPRMrunmod model result LIMIT 500 If ret 0 Then sgBox Execution error amp ret amp Exit Sub End If End Sub Other programming language interfaces 87 Mosel User Guide Index 7 45 14 45 46 ja 14 14 45 46 lt 7 14
41. zero This is also the easiest way to input data into data tables with more than two dimensions An added advantage is that less memory is used by Mosel The main areas covered in this chapter are related to this property e dynamic arrays e sparse data e conditional generation e displaying data We start again with an example problem The following sections deal with the different topics in more detail 3 1 A transport example A company produces the same product at different plants in the UK Every plant has a different production cost per unit and a limited total capacity The customers grouped into customer regions may receive the product from different production locations The transport cost is proportional to the distance between plants and customers and the capacity on every delivery route is limited The objective is to minimize the total cost whilst satisfying the demands of all customers 3 1 1 Model formulation Let PLANT be the set of plants and REGION the set of customer regions We define decision variables flow for the quantity transported from plant p to customer region r The total cost of the amount of product p delivered to region r is given as the sum of the transport cost the distance between p and r multiplied by a factor FUELCOST and the production cost at plant p minimize X M FUELCOST DISTANCEp PLANTCOST floWpr p PLANT rc REGION 19 Xpress Mosel User Guide The limits on plant capac
42. 13 3 2 C interface return 0 To print the contents of set SPrime that contains the desired result prime numbers between 2 and 500 we first retrieve the Mosel reference to this object using function XPRMfindident We are then able to enumerate the elements of the set using functions XPRMget firstsetndx and XPRMgetlastsetndx and obtain their respective values with XPRMgetelsetval Retrieving solution values The following program executes the model Burglar3 the same as model Burglar2 from Chapter 2 but with all output printing removed and prints out its solution include lt stdio h gt include xprm_rt h int main XPRMmodel mod XPRMalltypes rvalue itemname XPRMarray varr darr XPRMmpvar x XPRMset set int indices 1 result type double val if XPRMinit Initialize Mosel return 1 if mod XPRMloadmod burglar3 bim NULL NULL Load a BIM file return 2 if XPRMrunmod mod amp result NULL Run the model includes optimization return 3 if XPRMgetprobstat mod amp XPRM_PBRES XPRM_PBOPT return 4 Test whether a solution is found printf Objective value g n XPRMgetobjval mod Print the obj function value type XPRMfindident mod take amp rvalue Get the model object take if XPRM_TYP type XPRM_TYP_MPVAR Check the type XPRM_STR type XPRM_STR_ARR it must be an mpvar ar
43. 13 C interface 13 1 Basic tasks cc dae epee epee eee bbe Gade EES 13 1 1 Compiling a model iN C coo eek wees Contents iii Xpress Mosel User Guide Contents 13 1 2 Executing a model in 2 2 2 5 88 ea ER x eee Ra dE RS 77 Taa Paame CRM I A ei AAA A A we 78 13 3 Accessing modeling objects and solution values 79 1231 ACESSSIMO SEIS ocio soe ex Xo x a AA 39 XX E cw ox 79 13 3 2 Retrieving solution values 80 13 3 3 Sparse arrays os ee ee a ee ee 81 13 3 4 Problem solving in C with Xpress Optimizer rns 82 14 Other programming language interfaces 85 rer 2 saw ee Sw SRE PELIS T 85 14 1 1 Compiling and executing a model in Java 85 ULA POOTO Loos oes A AAA a eee a 85 14 2 Visual BASTE acum komo ko Romo ea Oa ee Row ROM RC HR EC OR RU UR x s 86 14 2 1 Compiling and executing a model in VisualBasic 86 14 2 2 Parameters ocioso ee oro X XU ROS x ee 87 Index 88 iv Xpress Mosel User Guide I Using the Mosel language Introduction Mosel is not an acronym It is pronounced like the German river mo zul It is an advanced modeling and solving language and environment where optimization problems can be speci fied and solved with the utmost precision and clarity Here are some of the features of Mosel e Mosel s easy syntax is regular and described formally in the reference manual Mosel suppo
44. 1600 Glasgow 4500 2000 Oxford 4000 2100 DIST CAP ROUTES Corby North 400 1000 Corby SWest 400 1000 Corby SEast 300 1000 Corby idlands 100 2000 Deeside Scotland 500 1000 Deeside North 200 2000 Deeside SWest 200 1000 Deeside SEast 200 1000 Deeside Midlands 400 300 Glasgow Scotland 200 3000 Glasgow North 400 2000 Glasgow SWest 500 1000 Glasgow SEast 900 200 Oxford Scotland 800 E Oxford North 600 2000 Oxford SWest 300 2000 Oxford SEast 200 2000 Oxford Midlands 400 500 FUELCOST 17 where we give the ROUTES data only for possible plant region routes indexed by the plant and region It is possible that some data are not specified for instance there is no Corby Scotland route So the data are sparse and we just create the flow variables for the routes that exist The for the Oxford Scotland entry in the capacity column indicates that the entry does not exist we may write 0 instead in this case the corresponding flow variable will be created but bounded to be 0 by the transport capacity limit The condition whether an entry in a data table is defined is tested with the Mosel function exists With the help of the operator we add this test to the forall loop creating the variables It is not required to add this test to the sums over these variables only the flow variables that have been created
45. 20 2750 Total cost of distribution 81 018 million File output Output If we do not want the output of procedure print_tab in the previous section to be displayed on screen but to be saved in the file out txt we simply open the file for writing at the beginning of the procedure by adding fopen out txt F_OUTPUT before the first writeln statement and close it at the end of the procedure after the last writeln statement with fclose F_OUTPUT If we do not want any existing contents of the file out txt to be deleted so that the result table is appended to the end of the file we need to write the following for opening the file closing it the same way as before fopen out txt F_OUTPUT F_APPEND As with input of data from file there are several ways of outputting data e g solution values to a file in Mosel The following example demonstrates three different ways of writing the contents of an array A to a file model Trio output uses mmetc declarations A array 1 3 1 3 of real end declarations A 2 4 6 12 14 16 22 24 26 First method use an initializations block initializations to out 1l dat A as MYOUT end initializations Second method use the built in writeln function fopen out 2 dat F OUTPUT forall i j in 1 3 writeln A out i and J9 j A i fclose F OUTPUT Third method use diskdata diskdata ETC_OUT ETC_SPARSE out_3 dat
46. 4 2 Database example ee 18 3 More advanced modeling features 19 3 1 JAdransportexamplB c corsa a a E ARRE Gn 19 3 1 1 Model formulation 6200852002 22 eRe eee Ee 19 312 Implementation 2 cc ky bee hb ko ek x eee R RR ee eee es 20 3 2 Conditional generation the Operator llle 22 3 2 1 Conditional variable creation and create 22 3 3 Reading sparse data sasaaa 23 4 Integer Programming 25 4 1 Integer Programming entities in Mosel o o e 25 4 2 A project planning model oo e ee 27 4 2 1 Model formulation llle 27 422 Implementation o icm b pre ea Pe Pee Ee pom x08 28 4 3 The project planning model using Special Ordered Sets 29 5 Overview of subroutines and reserved words 30 Bb Modules 26 6 4 bed x cae ae SO OS RR e DORADE hbo on RC 30 5 2 Reserved words 2 31 ii Xpress Mosel User Guide 6 Correcting syntax errors in Mosel Il Advanced language features 7 Flow control constructs Po SelSC 0g PRECES LE WOODS isa AR a PEERS ee Row wo Jul forall im oo eee oe ee wee dk me d 7 2 1 1 Multipleindices 7 2 1 2 Conditional looping Ted Ml ciues a a Ek ENE E i 4 4 3 6peast UNELI a esee RR RUE A OE Roo m dh 8 Sets BT InitializingSets s a ages dino ee ae a 4S 8 1 1 Constant Sets c ccce seassa maa a 8 1 2 Set initialization from file finalize
47. A while loop is typically employed if the number of times that the loop needs to be executed is not know beforehand but depends on the evaluation of some condition a set of statements is repeated while a condition holds As with fora11 the while statement exists in two versions an inline version while and a version while do that is to be used with a block of program statements The following example computes the largest common divisor of two integer numbers A and B that is the largest number by which both A and B can be divided without remainder Since there is only a single if then else statement in the while loop we could use the inline version of the loop but for clarity s sake we have given preference to the while do version that marks where the loop terminates clearly model Lcdivl declarations A B integer end declarations write Enter two integer numbers n A Flow control constructs 40 Mosel User Guide readln A write B readin B while A lt gt B do if A gt B then A A B else B B A end if end do writeln Largest common divisor A end model 7 2 3 repeat until The repeat until structure is similar to the while statement with the difference that the actions in the loop are executed once before the termination condition is tested for the first time The following example combines the three types of loops forall while repeat until that are available in Mosel It implements a
48. ADI ORE El El COST AVAIL GRADE of real l of real L of real l array ORES array ORES array ORES use array ORES end declarations of mpvar l Read data from file blend dat initializations from blend dat COST AVAIL GRADI end initializations Fle Objective Profit maximize total profit sum o in ORES REV COST Unit revenue of product Minimum permitted grad Maximum permitted grad Range of ores of product of product Unit cost of ores Availability of ores Grade of ores measured per unit of mass Quantities of ores used o use o Lower and upper bounds on ore quality sum o in ORES sum o in ORES GRADE 0 MINGRADE MAXGRADE GRADE 0 Set upper bounds on variables forall o in ORES use o lt AVAIL maximize Profit Print out the solution writeln Solution n Objective forall o in ORES writeln use end model use o gt 0 use o gt 0 o Solve the LP problem getobjval o getsol use o The file blend dat contains the following Some illustrative examples Mosel User Guide Data file for blend mos COST 85 93 AVAIL 60 45 GRADE 2 1 6 3 The initializations from end initializations block is new here telling Mosel where to get data from to initialize named arrays The order of the data items in the file doe
49. C for the Xpress Optimizer it may be necessary to pass from a problem formulation with Mosel to solving the problem in C by direct calls to the Xpress Optimizer The following exam ple shows how this may be done for the Burglar problem We use a slightly modified version of the original Mosel model model Burglar4 uses mmxprs declarations WIMAX 102 Maximum weight allowed ITEMS camera necklace vase picture tv video chest brick Index set for items VALUE array ITEMS of real Value of items WEIGHT array ITEMS of real Weight of items take array ITEMS of mpvar 1 if we take item i 0 otherwise end declarations Item ca ne va pi tv vi ch br VALUE 15 100 90 60 40 15 10 1 WEIGHT 2 20 20 30 40 30 60 10 Objective maximize total value MaxVal sum i in ITEMS VALUE i take i Weight restriction sum i in ITEMS WEIGHT i take i lt WTMAX All variables are 0 1 forall i in ITEMS take i is binary setparam XPRS LOADNAMES true Enable loading of object names loadprob MaxVal Load problem into the optimizer end model 82 Mosel User Guide C interface The procedure maximize to solve the problem has been replaced by loadprob This procedure loads the problem into the optimizer without solving it We also enable the loading of names from Mosel into the optimizer so that we may obtain an easily
50. ITES sola array CONTR AREAS objval starttime real cut array range of linctr end declarations npcut integer of of starttime gettime setparam XPRS_CUTSTRATEGY setparam XPRS_PRESOLVE 0 feastol getparam XPRS_FEASTOL setparam ZEROTOL feastol 10 ncut 0 npass 0 while ncut lt MAXCUTS and npass lt MAXPASS npass 1 npcut 0 minimize XPRS_LIN Cost if npass gt 1 and objval getobjval savebasis 1 objval getobjval forall c in CONTR do forall a in AREAS sola c forall s in SITES solc c end do Max no of constraints added in total Max no of constraints added per pass Max no passes Counters for cuts and passes Zero tolerance real Sol values for variables clean real Sol values for variables alloc 0 Disable automatic cuts Switch presolve off Get the Optimizer zero toleranc Set the comparison tolerance of Mosel do Solve the LP then break end if Save the current Get the objectiv basis valu Get the solution a getsol alloc c a S getsol clean c s values Search for violated constraints and add them to the problem forall c in CONTR it soretes cut ncut ncut 1 npcut 1 if end if More about Integer Programming npcut gt MAXPCUTS or ncut gt MAXCUTS s in SITES gt sola c AREA s alloc c AREA s then gt clean c s then
51. Max max p in SNumbers p It is good programming practice to indent the block of statements in loops or selections as in the preceding example so that it becomes easy to get an overview where the loop or the selection ends At the same time this may serve as a control whether the loop or selection has been terminated correctly i e no end if or similar key words terminating loops have been left out Flow control constructs 38 Mosel User Guide 7 2 Loops Loops group actions that need to be repeated a certain number of times either for all values of some index or counter forall or depending on whether a condition is fulfilled or not while repeat until This section presents the complete set of loops available in Mosel namely forall forall do while while do and repeat until 7 2 4 forall The forall loop repeats a statement or block of statements for all values of an index or counter If the set of values is given as an interval of integers range the enumeration starts with the smallest value For any other type of sets the order of enumeration depends on the current internal order of the elements in the set The forall loop exists in two different versions in Mosel The inline version of the forall loop i e looping over a single statement has already been used repeatedly for example as in the following loop that constrains variables x i i 1 10 to be binary forall i in 1 10 x i is binary The sec
52. T is the same as RAINBOW false Sets 47 Mosel User Guide Chapter 9 Functions and procedures When programs grow larger than the small examples presented so far it becomes necessary to introduce some structure that makes them easier to read and to maintain Usually this is done by dividing the tasks that have to be executed into subtasks which may again be subdivided and indicating the order in which these subtasks have to be executed and which are their activation conditions To facilitate this structured approach Mosel provides the concept of subroutines Using subroutines longer and more complex programs can be broken down into smaller subtasks that are easier to understand and to work with Subroutines may be employed in the form of procedures or functions Procedures are called as a program statement they have no return value functions must be called in an expression that uses their return value Mosel provides a set of predefined subroutines for a comprehensive documentation the reader is referred to the Mosel Reference Manual and it is possible to define new functions and pro cedures according to the needs of a specific program A procedure that has occured repeatedly in this document is writeln Typical examples of functions are mathematical functions like abs floor 1n sin etc 9 1 Subroutine definition User defined subroutines in Mosel have to be marked with procedure end procedure and function end function respect
53. There seem to be three major areas where non linear facilities are required e where entities must inherently be selected from a discrete set e in modeling logical conditions and e in finding the global optimum over functions Mosel lets you model these non linearities using a range of discrete global entities and then the Xpress MP Mixed Integer Programming MIP optimizer can be used to find the overall global optimum of the problem Usually the underlying structure is that of a Linear Pro gram but optimization may be used successfully when the non linearities are separable into functions of just a few variables 4 1 Integer Programming entities in Mosel We shall show how to make variables and sets of variables into global entities by using the following declarations declarations IR 1 8 Index range WEIGHT array IR of real Weight table x array IR of mpvar end declarations WEIGHT 2 5 7 10 14 18 22 30 Xpress MP handles the following global entities e Binary variables decision variables that can take either the value O or the value 1 do don t do variables We make a variable say x 4 binary by x 4 is binary e Integer variables decision variables that can take only integer values We make a variable say x 7 integer by x 7 is integer e Partial integer variables decision variables that can take integer values up to a specified limit and any value above that limit x 1 is
54. a sibility that are typically of the order of 10 9 by default When evaluating a solution for instance by performing comparisons it is important to take into account these tolerances After retrieving the feasibility tolerance of the Optimizer we set the comparison tolerance of Mosel ZEROTOL to this value This means for example the test x 0 evaluates to true if x lies between ZEROTOL and ZEROTOL x lt 0 is true if the value of x is at most ZEROTOL and x gt 0 is fulfilled if x is greater than ZEROTOL Comparisons in Mosel always use a tolerance with a very small default value By resetting this parameter to the Optimizer feasibility tolerance Mosel evaluates solution values just like the Optimizer Branch and Cut The cut generation loop presented in the previous subsection only generates violated inqual ities at the top node before entering the Branch and Bound search and adds them to the problem in the form of additional constraints We may do the same using the cut manager of Xpress Optimizer In this case the violated constraints are added to the problem via the cut pool We may even generate and add cuts during the Branch and Bound search A cut added at a node using addcuts only applies to this node and its descendants so one may use More about Integer Programming 62 Mosel User Guide this functionality to define local cuts however in our example all generated cuts are valid globally The cut manager is set up wi
55. amming LP Mixed Integer Programming MIP or Quadratic Programming QP problems The part has been designed to show the modeling aspects of Mosel omitting most of the more advanced programming constructs Part Il is designed to help those users who want to use the powerful programming lan guage facilities of Mosel using Mosel as a modeling solving and programming environ ment Items covered include looping with examples more about using sets producing nicely formatted output functions and procedures We also give some advanced MP ex amples including Branch and Cut column generation Goal Programming and Successive Linear Programming Part lll shows how Mosel models can be embedded into large applications using program ming languages like C Java or Visual Basic This user guide is deliberately informal and is not complete It must be read in conjunction with the Mosel reference manual where features are described precisely and completely Introduction 4 Mosel User Guide Chapter 1 Getting started with Mosel In this chapter we will take you through a very small manufacturing example to illustrate the basic building blocks of Mosel Models are entered into a Mosel file using a standard text editor do not use a word processor as an editor as this may not produce an ASCII file If you have access to Windows Xpress IVE is the model development environment to use The Mosel file is then loaded into Mosel and compiled F
56. as in other programming languages the declaration of local parameters may hide these parameters Mosel considers this as a possible mistake and prints a warning during compilation without any consequence for the execution of the program model Simple subroutines declarations a integer end declarations function three integer returned 3 end function function times_two b integer integer returned 2 b end function procedure print_start writeln The program starts here end procedure procedure hide_a_1 declarations a integer end declarations a 7 writeln Procedure hide_a_l a a end procedure procedure hide_a_2 a integer writeln Procedure hide_a_2 a a end procedure procedure hide_a_3 a integer declarations a integer end declarations a 15 writeln Procedure hide a 3 a a end procedure print start Functions and procedures 49 Mosel User Guide a three writeln a a a times_two a writeln a a hide_a_1 writeln a a hide_a_2 10 writeln a a hide_a_3 a writeln a a end model During the compilation we get the warning Mosel W 165 at 30 3 of subrout mos Declaration of a hides a parameter This is due to the redefinition of the parameter in procedure hide_a_3 The program results in the following output The program starts here a 3 a 6 Procedure hide_a_l a 7 a 6 Procedure hide_a_2 a 10 a 6
57. best O checks whether zbest lies within EPS of 0 see explanation in Section 11 1 procedure column gen declarations dualdem array WIDTHS of real xbest array WIDTHS of integer dw zbest objval real end declarations Setparam XPRS CUTSTRATEGY 0 Disable automatic cuts setparam XPRS PRESOLVE 0 Switch presolve off setparam zerotol EPS Set comparison tolerance of Mosel npatt NWIDTHS npass 1 while true do minimize XPRS_LIN MinRolls Solve the LP savebasis 1 Save the current basis objval getobjval Get the objective valu Get the solution values forall j in 1 npatt soluse 3 getsol use 3 forall i in WIDTHS dualdem i getdual Dem i Solve a knapsack problem zbest knapsack dualdem WIDTH MAXWIDTH xbest npass 1 0 More about Integer Programming 66 Mosel User Guide write Pass npass if zbest 0 then writeln no profitable column found n break else show_new_pat zbest xbest Print the new pattern npatt 1 create use npatt Create a new var for this pattern use npatt is_integer MinRolls use npatt Add new var to the objective dw 0 forall i in WIDTHS if xbest i gt 0 then Dem i xbest i use npatt Add new var to demand constr s dw maxlist dw ceil DEMAND i xbest i end if use npatt dw Set upper bound on the new var loadprob MinRolls Reload the problem loadbasis 1 Loa
58. cribed by the type of the callback see the Xpress Optimizer Reference Manual and the chapter on mmxprs in the Mosel Language Reference Manual At every node this function is called repeatedly followed by a re solution of the current LP as long as it returns true Remark if one wishes to access the solution values in a callback function the Xpress Optimizer parameter XPRS_SOLUTIONFILE must be set to 0 before getting the solution and after getting the solutions it must be set back to 1 Column generation 11 2 1 11 2 2 The technique of column generation is used for solving linear problems with a huge number of variables for which it is not possible to generate explicitly all columns of the problem matrix Starting with a very restricted set of columns after each solution of the problem a column generation algorithm adds one or several columns that improve the current solution These columns must have a negative reduced cost in a minimization problem and are calculated based on the dual value of the current solution For solving large MIP problems column generation typically has to be combined with a Branch and Bound search leading to a so called Branch and Price algorithm The example problem described below is solved by solving a sequence of LPs without starting a tree search Example problem A paper mill produces rolls of paper of a fixed width MAXWIDTH that are subsequently cut into smaller rolls according to the customer
59. d and fixed sets 82 Working withsets o pi pess biss Edi 82 1 Set operators o o ll rn 9 Functions and procedures 9 1 Subroutine definition o 9 2 Parameters ooo es 9 3 REOGUISION cosas a XL DOS aaa Qu Torvard ror yia aaa a A a a x0 9 5 Overloading Of subroutines lens 10 Output 10 1 Producing formatted output o oo 10 2 File GUEDUE Lusso hx Re Rom m RR RR ES RR donnees E 11 More about Integer Programming TRI CUr generation s e ere e AAA 11 1 1 Example problem o o 11 1 2 Model formulation oo 11 1 3 Implementation o ooo 11 1 4 Cut and Branch o tees 11 1 5 Comparison tolerance 11 1 6 Branch and Cut o o oo o 11 2 Column generation o 11 2 1 Example problem o 11 2 2 Model formulation oo 11 2 3 Implementation ooo 12 Extensions to Linear Programming 12 1 RECUESION lt s ee o a n m ee d 12 1 1 Example problem aa 12 1 2 Model formulation oo o 12 1 3 Implementation o oo 12 2 Goal Programming o c soon ee Se Gone xc kon 12 2 1 Example problemi o s s s src 9 RR we eS 12 2 2 Implementation RR RR lll Working with the Mosel libraries
60. d the saved basis end if npass 1 end do writeln Solution after column generation objval rolls getsize RP patterns write Rolls per pattern forall i in RP write soluse i writeln end procedure The preceding procedure column_gen calls the following auxiliary function knapsack to solve an integer knapsack problem of the form maximize z o gt G Xj jeWIDTHS 5 Aj Xj lt B J WIDTHS Vj WIDTHS x integer The function knapsack solves a second optimization problem that is independent of the main cutting stock problem since the two have no variables in common We thus effectively work with two problems in a single Mosel model For efficiency reasons we have defined the knapsack variables and constraints globally The in tegrality condition on the knapsack variables remains unchanged between several calls to this function so we establish it when solving the first knapsack problem On the other hand the knapsack constraint and the objective function have different coefficients at every execution so we need to replace them every time the function is called We reset the knapsack constraints to 0 at the end of this function so that they do not unnec essarily increase the size of the main problem The same is true in the other sense hiding the demand constraints while solving the knapsack problem makes life easier for the optimizer but is not essential for getting the correct solution functio
61. dModel prime bim System out println Executing prime mod run LIMIT 500 System out println prime returned mod getResult 14 2 Visual Basic In Visual Basic a Mosel model needs to be embedded into a project In this section we shall only show the parts relevant to the Mosel functions assuming that the execution of a model is trigged by the action of clicking on some object 14 2 1 Compiling and executing a model in Visual Basic As with the other programming languages to execute a Mosel model in Visual Basic we need to perform the standard compile load run sequence as shown in the following example We use a slightly modified version burglar5 mos of the burglar problem where we have redirected the output printing to the file burglar out txt Private Sub burglar Click Dim model As Long Dim ret As Long Dim result As Long Initialize Mosel ret XPRMinit If ret lt gt 0 Then sgBox Initialization error amp ret amp Exit Sub End If Compile burglar5 mos ret XPRMcompmod vbNullString burglar5 mos vbNullString Knapsack If ret 0 Then sgBox Compile error amp ret amp Exit Sub End If Load burglar5 bim model XPRMloadmod burglar5 bim vbNullString If model 0 Then sgBox Error loading model Exit Sub End If Other programming language interfaces 86 Mosel User Guide Run the model ret XPRMrunmod model result
62. ded that we have given the same names to the data table and its columns SOLconnect DSN mysql DB blend ODBC just like Mosel s text file format may also be used to output data The reader is referred to the ODBC SQL documentation for more detail With version 1 4 of Mosel it becomes possible to access data sources through ODBC directly from initializations blocks with the same syntax as what has been shown previously for ordinary text format data files In this case the SQL commands for reading or writing data are generated by Mosel The whitepaper Generalized file handling in Mosel gives several examples of this simplified use of ODBC Some illustrative examples 18 Mosel User Guide Chapter 3 More advanced modeling features This chapter introduces some more advanced features of the modeling language in Mosel We shall not attempt to cover all its features or give the detailed specification of their formats These are covered in greater depth in the Mosel Reference Manual Almost all large scale LP and MIP problems have a property known as sparsity that is each variable appears with a non zero coefficient in a very small fraction of the total set of con straints Often this property is reflected in the data tables used in the model in that many values of the tables are zero When this happens it is more convenient to provide just the non zero values of the data table rather than listing all the values the majority of which are
63. e Flow on each route create flow p r Objective minimize total cost MinCost sum p in PLANT r in REGION exists flow p r FUELCOST DISTANCE p r PLANTCOST p flow p r Limits on plant capacity forall p in PLANT sum r in REGION flow p r lt PLANTCAP p Satisfy all demands forall r in REGION sum p in PLANT flow p r DEMAND r Bounds on flows forall p in PLANT r flow p r More advanced modeling features in REGION lt TRANSCAP p r 20 exists flow p r Mosel User Guide minimize MinCost Solve the problem end model REGION and PLANT are declared to be sets of strings as yet of unknown size The data arrays DEMAND PLANTCAP PLANTCOST TRANSCAP and DISTANCE and the array of variables flow are indexed by members of REGION and PLANT their size is therefore not known at their decla ration they are created as dynamic arrays There is a slight difference between dynamic arrays of data and of decision variables type mpvar an entry of a data array is created automatically when it is used in the Mosel program entries of decision variable arrays need to be created explicitly see Section 3 2 1 below The data file transprt dat contains the problem specific data It might have for instance DEMAND Scotland 2840 North 2800 SWest 2600 SEast 2820 Midlands 2750 CAP COST PLANTDATA Corby 3000 1700 Deeside 2700
64. e j gt DEMAND i column_gen Column generation at top node minimize MinRolls Compute the best integer solution for the current problem including the new columns writeln Best integer solution getobjval rolls write Rolls per pattern forall i in RP write getsol use i The paper mill can satisfy the demand with just the basic set of cutting patterns but it is likely to incur significant losses through wasting more than necessary of every large roll and by cutting more small rolls than its customers have ordered We therefore employ a column generation heuristic to find more suitable cutting patterns The following procedure column gen defines a column generation loop that is executed at the top node this heuristic was suggested by M Savelsbergh for solving a similar cutting stock problem The column generation loop performs the following steps solve the LP and save the basis get the solution values compute a more profitable cutting pattern based on the current solution generate a new column cutting pattern add a term to the objective function and to the corresponding demand constraints load the modified problem and load the saved basis To be able to increase the number of variables use in this function these variables have been declared at the beginning of the program as a dynamic array without specifying any index range By setting Mosel s comparison tolerance to EPS the test z
65. e line import com dashoptimization must be added at the beginning of the program 14 1 1 Compiling and executing a model in Java With Java it is not required to initialize Mosel explicitly To execute a Mosel model in Java we merely need to call the three Mosel functions performing the standard compile load run sequence as shown in the following example import java io import com dashoptimization public class ugcomp public static void main String args throws java io IOException XPRMmodel mod System out println Compiling burglar2 XPRM compile burglar2 mos System out println Loading burglar2 mod XPRM loadModel burglar2 bim System out println Executing burglar2 mod run System out println burglar2 returned mod getResult 14 1 2 Parameters When executing a Mosel model in Java it is possible to pass new values for its parameters into the model If for instance we want to run model Prime from Section 8 2 to obtain all prime numbers up to 500 instead of the default value 100 set for the parameter LIMIT in the model we may write the following program 85 Xpress Mosel User Guide import java io import com dashoptimization public class ugparam public static void main String args throws java io IOException XPRMmodel mod System out println Compiling prime XPRM compile prime mos System out println Loading prime mod XPRM loa
66. e output of this example will look as follows Union of all places rome bristol london paris liverpool plymouth bristol glasgow calais liverpool rome paris madrid berlin Intersection of all three london Cities that are not capitals bristol liverpool Sets in Mosel are indeed a powerful facility for programming as in the following example that calculates all prime numbers between 2 and some given limit Starting with the smallest one the algorithm takes every element of a set of numbers SNum bers positive numbers between 2 and some upper limit that may be specified when running the model adds it to the set of prime numbers SPrime and removes the number and all its multiples from the set SNumbers 45 Mosel User Guide model Prime parameters LIMIT 100 Search for prime numbers in 2 LIMIT end parameters declarations SNumbers set of integer Set of numbers to be checked SPrime set of integer Set of prime numbers end declarations SNumbers 2 LIMIT writeln Prime numbers between 2 and LIMIT n 2 repeat while not n in SNumbers n 1 SPrime n n is a prime number i n while i LIMIT do Remove n and all its multiples SNumbers 1 it n end do until SNumbers writeln SPrime writeln getsize SPrime prime numbers end model This example uses a new f
67. e to x eplus eminus array QUARTERS of mpvar and deviations end declarations X 0 00 B ls hae Ty 1 ds 1 P 1000 0 0 0 0 0 R 206 6 206 6 206 6 206 6 206 6 0 Vim 22 95 0 0 0 0 0 net payments interest forall t in QUARTERS net t P t R t V t interest t Money balance across periods forall t in QUARTERS balance t if t 1 balance t 1 0 net t forall t in 2 T Interest t Approximation of interest 365 92 interest t X balance t 1 B t 1 dx eplus t eminus t O Extensions to Linear Programming 70 Mosel User Guide Def X dx x Define the interest rate x X dx Feas sum t in QUARTERS eplus t eminus t Objective get feasibl interest 1 0 Initial interest is zero forall t in QUARTERS net t is_free forall t in 1 T 1 balance t is_free balance T 0 Final balance is zero dx is_free minimize Feas Solve the LP problem solve_recurse Recursion loop Print the solution writeln nThe interest rate is getsol x wrlteistrimbp t 5 strfmt 41 forall t in QUARTERS write strfmt t 5 strfmt 3 write nBalances forall t in QUARTERS write strfmt getsol balance t 8 2 write nInterest forall t in QUARTERS write strfmt getsol interest t 8 2 end model In the model above we have declared the procedure solve_recurse that execute
68. el User Guide loadprob Feas Reload the problem into the optimizer loadbasis 1 Reload previous basis minimize Feas Re solve the LP problem variation abs getsol x oldxval Change in dx end do end procedure With the initial guesses 0 for X and 1 for all B the model converges to an interest rate of 5 94413 x 0 0594413 12 2 Goal Programming Goal Programming is an extension of Linear Programming in which targets are specified for a set of constraints In Goal Programming there are two basic models the pre emptive lex icographic model and the Archimedian model In the pre emptive model goals are ordered according to priorities The goals at a certain priority level are considered to be infinitely more important than the goals at the next level With the Archimedian model weights or penal ties for not achieving targets must be specified and we attempt to minimize the sum of the weighted infeasibilities If constraints are used to construct the goals then the goals are to minimize the violation of the constraints The goals are met when the constraints are satisfied The example in this section demonstrates how Mosel can be used for implementing pre emptive Goal Programming with constraints We try to meet as many goals as possible taking them in priority order 12 2 1 Example problem The objective is to solve a problem with two variables x and y the constraint 100 x 60 y lt 600 and the three goal constrai
69. er feasible solutions and improving the bound provided by the solution of the relaxed problem The Xpress Optimizer provides automated cut generation see the optimizer documentation for details To show the effects of the cuts that are generated by our example we switch off the automated cut generation Example problem The problem we want to solve is the following a large company is planning to outsource the cleaning of its offices at the least cost The NSITES office sites of the company are grouped into areas set AREAS 1 NAREAS Several professional cleaning companies set CONTR 1 NCONTRACTORS have submitted bids for the different sites a cost of 0 in the data meaning that a contractor is not bidding for a site To avoid being dependent on a single contractor adjacent areas have to be allocated to differ ent contractors Every site s s in SITES 1 NSITES is to be allocated to a single contractor but there may be between LOWCON and UPPCON contractors per area a Model formulation For the mathematical formulation of the problem we introduce two sets of variables clean s indicates whether contractor c is cleaning site s allocc4 indicates whether contractor c is allocated any site in area a The objective to minimize the total cost of all contracts is as follows where PRICE is the price per site and contractor minimize gt 5 PRICE cleans CECONTR scSITES We need the following three sets
70. ering the variables the so called reference row entries then we can do thus makesos1 S L with the obvious change for SOS2 sets This method must be used if the coefficient here WEIGHT i of an intended set member is zero With is sosX the variable will not appear in the set since it does not appear in the linear expression Another point to note about Special Ordered Sets is that the ordering coefficients must be distinct or else they are not doing their job of supplying an order The most commonly used entities are binary variables which can be employed to model a whole range of logical conditions General integers are more frequently found where the un derlying decision variable really has to take on a whole number value for the optimal solution to make sense For instance we might be considering the number of airplanes to charter where fractions of an airplane are not meaningful and the optimal answer will probably in volve so few planes that rounding to the nearest integer may not be satisfactory Partial integers provide some computational advantages in problems where it is acceptable to round the LP solution to an integer if the optimal value of a decision variable is quite large but unacceptable if it is small Semi continuous variables are useful where if some variable is to be used its value must be no less than some minimum amount If the variable is a semi continuous integer variable then it has the added restriction
71. fit 2 2 1 Model formulation Denote the amounts of the ores to be used by use and use Maximizing net profit i e sales revenue less cost COST of raw material gives us the objective function 5 REV COST use OCORES We then have to ensure that the grade of the final ore is within certain limits Assuming the grades of the ores combine linearly the grade of the final product is Mocores GRADE uses gt ocores US o This must be greater than or equal to 4 so cross multiplying and collecting terms we have the constraint Y GRADE 4 use gt 0 OE ORES Similarly the grade must not exceed 5 Mocores GRADE useo 2 ocores USEo i Some illustrative examples 14 Mosel User Guide So we have the further constraint 2 6 oc ORES GRADE Use gt 0 Finally there is a limit to the availability AVA L of each of the ores We model this with the constraints Vo ORES use lt AVAIL 2 2 2 Implementation The above problem description sets out the relationships which exist between variables but contains few explicit numbers Focusing on relationships rather than figures makes the model much more flexible In this example only the selling price REV and the upper lower limits on the grade of the final product MINGRADE and MAXGRADE are fixed Enter the following model into a file blend mos Blend mmxprs model uses declarations REV 125 MINGRADI MAXGR
72. functions provided by the underlying operating system e Delete a file directory fdelete removedir e Move a file fmove e Current working directory getcwd e Get an environment variable s value getenv e File status getfstat e Returns the system status getsysstat e Time gettime e Make a directory makedir e General system call system Other modules mentioned in this manual are mmodbc and mmetc See the module reference manuals for full details 5 2 Reserved words The following words are reserved in Mosel The upper case versions are also reserved i e AND and and are keywords but not And Do not use them in a model except with their built in meaning and array as boolean break case declarations div do dynamic elif else end false forall forward from function if in include initialisations initializations integer inter is_binary is_continuous is_free is_integer is_partint is_semcont is_semint is_sosl is_sos2 Lincte xs max min mod model mpvar Overview of subroutines and reserved words 31 Mosel User Guide next not of options or parameters procedure public prod range real repeat set string sum then to true union until uses while Overview of subroutines and reserved words 32 Mosel User Guide Chapter 6 Correcting syntax errors in Mosel The parser of Mosel is able to detect a large number of errors that may occur when writing a model In this c
73. ggregated way this type of constraint is usually referred to as Multiple Variable Lower Bound MVLB constraints Instead of forall c in CONTR a in AREAS E a alloc c a gt 1 0 NUMSITI sum s in SITES AREA s a clean c s we could also have used the stronger formulation forall c in CONTR s in SITES alloc c AREA s gt clean c s More about Integer Programming 60 Mosel User Guide but this considerably increases the total number of constraints The aggregated constraints are sufficient to express this problem but this formulation is very loose with the consequence that the solution of the LP relaxation only provides a very bad approximation of the integer solution that we want to obtain For large data sets the Branch and Bound search may therefore take a long time 11 14 Cut and Branch To improve this situation without blindly adding many unnecessary constraints we implement a cut generation loop at the top node of the search that only adds those constraints that are violated be the current LP solution The cut generation loop procedure top_cut_gen performs the following steps e solve the LP and save the basis e get the solution values e identify violated constraints and add them to the problem e load the modified problem and load the previous basis procedure top_cut_gen declarations MAXCUTS 2500 MAXPCUTS 1000 MAXPASS 50 nout pass feastol real solc array CONTR S
74. hanged To declare it as a dynamic set the contents needs to be assigned after its declaration declarations ITEMS set of string end declarations ITEMS camera necklace vase picture tv video chest brick 8 1 2 Setinitialization from file finalized and fixed sets In Chapter 3 the reader has encountered several examples how the contents of sets may be initialized from data files The contents of the set may be read in directly as in the following case declarations WHICH set of integer end declarations 43 Xpress Mosel User Guide Sets initilizations from idata dat WHICH end initializations Where idata dat contains data in the following format WHICH 1 4 7 11 14 Unless a set is constant arrays that are indexed by this set are created as dynamic arrays Since in many cases the contents of a set does not change any more after its initialization Mosel provides the inalize statement that turns a dynamic set into a constant set Consider the continuation of the example above finalize WHICH declarations x array WHICH of mpvar end declarations The array of variables x will be created as a static array without the inalize statement it would be dynamic since the index set WHICH may still be subject to changes Declaring arrays in the form of static arrays is preferable if the indexing set is known before because this allows Mosel to handle them in a more efficient way
75. hapter we shall try to analyze and correct some of these If we compile the model model Plenty of errors declarations small large mpvar end declarations Profit 5 small 20 large Boxwood small 3 large lt 200 Lathe 3 small 2 large lt 160 maximize Profit writeln Best profit is getobjval end model we get the following output Mosel E 100 at 1 7 of poerror mos Syntax error before V Parsing failed The second line of the output informs us that the compilation has not been executed correctly The first line tells us exactly the type of the error that has been detected namely a syntax error with the code E 100 where E stands for error and its location line 1 character 7 The problem is caused by the apostrophe or something preceding it Indeed Mosel expects either single or double quotes around the name of the model if the name contains blanks We therefore replace it by and compile the corrected model resulting in the following display Mosel E 100 at 6 8 of poerror mos Syntax error before Mosel W 121 at 6 29 of poerror mos Statement with no effect Mosel E 100 at 10 16 of poerror mos Profit is not defined Mosel E 123 at 10 17 of poerror mos maximize is not defined Mosel E 100 at 12 37 of poerror mos Syntax error Parsing failed There is a problem with the sign in the 6 line Profit 5 small 20 large
76. he immense flexibility of readin As a third possibility one may use the diskdata subroutine from module mmet c to read in comma separated value CSV files More advanced modeling features 23 Mosel User Guide model Trio input uses mmetc Required for diskdata declarations Al A2 A3 array range range of real i j integer end declarations First method use an initializations block initializations from data 1 dat Al as MYDATA end initializations Second method use the built in readln function fopen data 2 dat F INPUT repeat readlin Tut i and j A2 i j until getparam nbread 6 fclose F_INPUT Third method use diskdata diskdata ETC_IN ETC_SPARSE data_3 dat A3 Now let us see what we have writeln Al is Al writeln A2 is A2 writeln A3 is A3 end model The data files could be set up thus File data 1 dat MYDATA 1 1 12 5 2 3 5 6 10 9 7 1 32 1 File data 2 dat Pu Pu Pu ut File data_3 dat Tepe ily lw dp e D 0 40494 ad Be 23 d When printing any of the three arrays A1 A2 or A3 we get the following output 17L 12 5 275 3 950 4 3725y1 4 105 9 7 1 More advanced modeling features 24 Mosel User Guide Chapter 4 Integer Programming Though many systems can accurately be modeled as Linear Programs there are situations where discontinuities are at the very core of the decision making problem
77. herwise so there is no need to specify non negativity constraints on variables Here is an example of a constraint Lathe 3 small 2 large lt 160 The name of the constraint is Lathe The actual constraint then follows If the constraint is unconstrained for example it might be an objective function then there is no lt gt or part In Mosel you enter the entire model before starting to compile and run it Any errors will be signaled when you try to compile the model or later when you run it see Chapter 6 on correcting syntax errors 1 2 2 Obtaining a solution using Mosel So far we have just specified a model to Mosel Next we shall try to solve it The first thing to do is to specify to Mosel that it is to use Xpress Optimizer to solve the problem Then assuming we can solve the problem we want to print out the optimum values of the decision variables small and large and the value of the objective function The model becomes model Chess 2 uses mmxprs We shall use Xpress Optimizer declarations small large mpvar Decision variables produced quantities end declarations Profit 5 small 20 large Objective function Lathe 3 small 2 large lt 160 Lathe hours Boxwood small 3 large lt 200 kg of boxwood maximize Profit Solve the problem writeln Make getsol small small sets writeln Make getsol large large sets writeln Best profit is getobjval end mode
78. iables forall p in PROJ XSet p sum m in MONTHS m start p m is_sosl The is_sos1 specification tells Mosel that Xset p is a Special Ordered Set of type 1 The lin ear expression specifies both the set members and the coefficients that order the set members It says that all the startpm variables for m in the MONTHS index range are members of an SOS1 with reference row entries m The specification of the startpm as binary variables must now be removed The binary nature of the startpm is implied by the SOS1 property since if the startpm must add up to 1 and only one of them can differ from zero then just one is 1 and the others are 0 If the two formulations are equivalent why were Special Ordered Sets invented and why are they useful The answer lies in the way the reference row gives the search procedure in Integer Programming IP good clues as to where the best solution lies Quite frequently the Linear Programming LP problem that is solved as a first approximation to an Integer Program gives an answer where startp is fractional say with a value of 0 5 and start yy takes on the same fractional value The IP will say my job is to get variables to 0 or 1 Most of the variables are already there so will try moving xp1 or xpT Since the set members must add up to 1 0 one of them will go to 1 and one to O So think that we start the project either in the first month or in the last month A much better guess is to see
79. iangle or alternatively choose Build gt Run The Build pane at the bottom of the workspace is automatically displayed when compilation starts If syntax errors are found in the model they are displayed here with details of the line and character position where the error was detected and a description of the problem if available Clicking on the error takes the user to the offending line When a model is run the Output Input pane at the right hand side of the workspace window is selected to display program output Any output generated by the model is sent to this window IVE will also provide graphical representations of how the solution is obtained which are generated by default whenever a problem is optimized The right hand window contains a number of panes for this purpose dependent on the type of problem solved and the particular algorithm used IVE also allows the user to draw graphs by embedding subroutines in Mosel models see the documentation on the website for further detail IVE makes all information about the solution available through the Entities pane in the left hand window By expanding the list of decision variables in this pane and hovering over one with the mouse pointer its solution and reduced cost are displayed Dual and slack values for constraints may also be obtained Getting started with Mosel 9 Mosel User Guide Chapter 2 Some illustrative examples This chapter develops the basics of modeling set out in Chap
80. if ct 2 the write Pl else write end if psum 0 forall r in Capacity t the solution values of the flow variables and ulate totals per region and per plant LANT do n ant strfmt p 8 strfmt p 8 REGION do iflow integer getsol flow p r psum i flow rsum r iflow if iflow 0 then write strfmt iflow 9 else write end if end do writeln str end do Prin write n s prsum 0 forall r in R fmt psum 9 strfmt integer PLANTCAP p 9 t the column totals trfmt TOTAL 14 EGION do prsum rsum r write strfm end do writeln strfm Prin t rsum r 9 t prsum 9 t demand of every region write strfmt Demand 14 forall r in R EGION write strfmt integer DEMAND r 9 Print objective function value writeln n nTotal cost of distribution million end procedure REGION of integer Auxiliary data table for printing t iflow integer Counters ons strfmt getobjval 1e6 0 3 With the data from Chapter 3 the procedure print table produces the following output 55 Mosel User Guide 10 2 Product Distribution Sales Region Scotland North SWest SEast Midlands TOTAL Capacity Corby 180 820 2000 3000 3000 Plant Deeside 1530 920 250 2700 2700 Glasgow 2840 1270 4110 4500 Oxford 1500 2000 500 4000 4000 TOTAL 2840 2800 2600 2820 2750 13810 Demand 2840 2800 2600 28
81. implemented with Mosel as follows model Burglar uses mmxprs declarations WIMAX 102 Maximum weight allowed 10 Xpress Mosel User Guide ITEMS 1 8 Index range for items VALUE array ITEMS of real Value of items WEIGHT array ITEMS of real Weight of items take array ITEMS of mpvar 1 if we take item i 0 otherwise end declarations Item 1 2 3 4 5 6 7 8 VALUE 15 100 90 60 40 15 10 1 WEIGHT 2 20 20 30 40 30 60 10 Objective maximize total value MaxVal sum i in ITEMS VALUE i take i Weight restriction sum i in ITEMS WEIGHT i take i lt WIMAX All variables are 0 1 forall i in ITEMS take i is_binary maximize MaxVal Solve the MIP problem Print out the solution writeln Solution n Objective getobjval forall i in ITEMS writeln take i getsol take i end model When running this model we get the following output Solution Objective 280 take 1 take 2 take take take take take C0 1 OY O iS Ww oororerep Lake In this model there are a lot of new features which we shall now explain e Constants WTMAX 102 declares a constant called wTMAX and gives it the value 102 Since 102 is an integer WTMAX is an integer constant Anything that is given a value in a declarations block is a constant e Ranges ITEMS 1 8 defines a range se
82. inally the compiled file can be run This chapter will show the stages in action 1 1 The chess set problem description To illustrate the model development and solving process we shall take a very small example A joinery makes two different sizes of boxwood chess sets The smaller size requires 3 hours of machining on a lathe and the larger only requires 2 hours because it is less intricate There are four lathes with skilled operators who each work a 40 hour week The smaller chess set requires 1 kg of boxwood and the larger set requires 3 kg However boxwood is scarce and only 200 kg per week can be obtained When sold each of the large chess sets yields a profit of 20 and one of the small chess set has a profit of 5 The problem is to decide how many sets of each kind should be made each week to maximize profit 1 1 1 A first formulation Within limits the joinery can vary the number of large and small chess sets produced there are thus two decision variables or simply variables in our model one decision variable per product We shall give these variables abbreviated names small the number of small chess sets to make large the number of large chess sets to make The number of large and small chess sets we should produce to achieve the maximum contri bution to profit is determined by the optimization process In other words we look to the optimizer to tell us the best values of small and large The values which small
83. ity are give through the constraints Vp PLANT X flow lt PLANTCAP reREGION We want to meet all customer demands Vr REGION X flow DEMAND pEPLANT The transport capacities on all routes are limited Vp PLANT r REGION flowp lt TRANSCAP pr For simplicity s sake in this mathematical model we assume that all routes p r are defined and that we have TRANSCAP 0 to indicate that a route cannot be used Implementation This problem may be implemented with Mosel as shown in the following model Transport uses mmxprs declarations REGION set of string PLANT set of string DEMAND array REGION of real PLANTCAP array PLANT of real PLANTCOST array PLANT of real TRANSCAP array PLANT REGION of real DISTANCE array PLANT REGION of real FUELCOST real flow array PLANT REGION of mpvar end declarations initializations from DEMAND PLANTCAP PLANTCOST DISTANCE TRANSCAP FUELCOST end initializations FO Du Lu Create the flow var forall p in PLANT r transprt dat PLANTDATA ROUTES l as as iables that exist in REGION exists TRANSCAP p r Set of customer regions Set of plants Demand at regions Production capacity at plants Unit production cost at plants Capacity on each route plant gt region Distance of each route plant gt region Fuel cost per unit distanc
84. ive Linear Programming is a technique whereby LP may be used to solve certain non linear problems Some coefficients in an LP problem are defined to be functions of the optimal values of LP variables When an LP problem has been solved the coefficients are re evaluated and the LP re solved Under some assumptions this process may converge to a local though not necessarily a global optimum 12 1 1 Example problem Consider the following financial planning problem We wish to determine the yearly interest rate x so that for a given set of payments we obtain the final balance of O Interest is paid quarterly according to the following formula interest 92 365 balance interest_rate The balance at time t t 1 T results from the balance of the previous period t 1 and the net of payments and interest net Payments interest balance balance net 12 1 2 Model formulation This problem cannot be modeled just by LP because we have the T products balance interest_rate which are non linear To express an approximation of the original problem by LP we replace the interest rate variable x by a constant guess X of its value and a deviation variable dx x X dx The formula for the quarterly interest payment i therefore becomes interest 92 365 balance x 92 365 balance 4 X dx 92 365 balance 1 X balance dx 69 Xpress Mosel User Guide 12 1 3 where balance is the balance
85. ively The return value of a function has to be assigned to returned as shown in the following example model Simple subroutines declarations a integer end declarations function three integer returned 3 end function procedure print start writeln The program starts here end procedure print start a three writeln a a end model This program will produce the following output The program starts here ar 3 48 Xpress Mosel User Guide 9 2 Parameters In many cases the actions to be performed by a procedure or the return value expected from a function depend on the current value of one or several objects in the calling program It is therefore possible to pass parameters into a subroutine The list of parameter s is added in parantheses behind the name of the subroutine function times_two b integer integer returned 2 b end function The structure of subroutines being very similar to the one of model they may also include declarations sections for declaring local parameters that are only valid in the correspond ing subroutine It should be noted that such local parameters may mask global parameters within the scope of a subroutine but they have no effect on the definition of the global pa rameter outside of the subroutine as is shown below in the extension of the example Simple subroutines Whilst it is not possible to modify function procedure parameters in the corre sponding subroutine
86. l The line uses mmxprs tells Mosel that Xpress Optimizer will be used to solve the LP The Mosel modules mmxprs module provides us with such things as maximization handling bases etc Getting started with Mosel 7 Mosel User Guide The line maximize Profit tells Mosel to maximize the objective function called Profit More complicated are the writeln statements though it is actually quite easy to see what they do If some text is in quotation marks then it is written literally getsol and getobjval are special Mosel functions that return respectively the optimal value of the argument and the optimal objective function value writeln writes a line terminator after writing all its arguments to continue writing on the same line use write instead writeln can take many arguments The statement writeln small getsol small large getsol large will result in the values being printed all on one line 1 2 3 Running Mosel from a command line When you have entered the complete model into a file let us call it chess mos we can proceed to get the solution to our problem Three stages are required 1 Compiling chess mos to a compiled file chess bim 2 Loading the compiled file chess bim 3 Running the model we have just loaded We start Mosel at the command prompt and type the following sequence of commands mosel compile chess load chess run quit which will compile load and run the model We will see o
87. lem from a spreadsheet and then later from a database 2 2 4 4 Spreadsheet example Let us suppose that in a Microsoft Excel spreadsheet called blend x1s you have inserted the following into the cells indicated Table 2 1 Spreadsheet example data A B C D E F 1 2 ORES COST AVAIL GRADE 3 1 85 60 2 1 4 2 93 45 6 3 5 and called the range B2 E4 MyRange In Windows you need to set up a User Data Source called Excel Files by clicking Aad selecting Microsoft Excel Driver xls and filling in the ODBC Microsoft Excel Setup dialog Click Options gt gt and clear the Read Only check box The following model reads the data for the arrays COST AVAIL and GRADE from the Excel range MyRange Note that we have added mmodbc to the uses statement to indicate that we are using the Mosel SQL ODBC module model Blend 3 uses mmodbc mmxprs declarations REV 125 Unit revenue of product MINGRADE 4 Minimum permitted grade of product MAXGRADE 5 Maximum permitted grade of product ORES 1 2 Range of ores COST array ORES of real Unit cost of ores Some illustrative examples 17 Mosel User Guide AVAIL array ORES of real Availability of ores GRADE array ORES of real Grade of ores measured per unit of mass use array ORES of mpvar Quantities of ores used end declarations Read data from spreadsheet blend xls SQLconnect
88. lization of the array sizes we are thus able to create all arrays with fixed sizes with the exception of the previously mentioned array of variables that is explicitly declared dynamic This allows Mosel to handle them in a more efficient way model Office cleaning uses mmxprs mmsystem declarations PARAM array 1 3 of integer end declarations initializations from clparam dat PARAM end initializations declarations NSITES PARAM 1 Number of sites NAREAS PARAM 2 Number of areas subsets of sites NCONTRACTORS PARAM 3 Number of contractors AREAS 1 NAREAS CONTR 1 NCONTRACTORS SITES 1 NSITES AREA array SITES of integer Area site is in NUMSITE array AREAS of integer Number of sites in an area LOWCON array AREAS of integer Lower limit on the number of contractors per area UPPCON array AREAS of integer Upper limit on the number of contractors per area ADJACENT array AREAS AREAS of integer 1 if areas adjacent 0 otherwise PRICE array SITES CONTR of real Price per contractor per site More about Integer Programming 59 Mosel User Guide clean dynamic array CONTR SITES of mpvar 1 iff contractor c cleans site s alloc array CONTR AREAS of mpvar 1 iff contractor allocated to a site in area a end declarations initializations from cldata dat NUMSITE LOWCON UPPCON as AREA ADJACENT PRICE end initializations
89. ln Goal g deviation from target getsol dev 2 9 lif getsol dev 2 g 1 gt 0 then writeln Goal g deviation from target getsol dev 2 g 1 end if end procedure end model When running the program one finds that the first two goals can be satisfied but not the third Extensions to Linear Programming 74 Mosel User Guide IIl Working with the Mosel libraries Whilst the two previous parts have shown how to work with the Mosel Language this part introduces the programming language interface of Mosel in the form of the Mosel C libraries The C interface is provided in the form of two libraries it may especially be of interest to users who e want to integrate models and or solution algorithms written with Mosel into some larger system want to re use already existing parts of algorithms written in C e want to interface Mosel with other software for instance for graphically displaying re sults Other programming language interfaces available for Mosel are its Java and Visual Basic inter faces They will be introduced with the help of small examples All these programming language interfaces only enable the user to access models but not to modify them The latter is only possible with the Mosel Native Interface Even more impor tantly the Native Interface makes it possible to add new constants types and subroutines to the Mosel Language For more detail the reader is referred to the Native In
90. n be entered into a file named perhaps chess mos as follows model Chess declarations small mpvar Number of small chess sets to make large mpvar Number of large chess sets to make end declarations Profit 5 small 20 large Objective function Lathe 3 small 2 large lt 160 Lathe hours Boxwood small 3 large lt 200 kg of boxwood end model Indentations are purely for clarity The symbol signifies the start of a comment which continues to the end of the line Comments over multiple lines start with and terminate with Getting started with Mosel 6 Mosel User Guide Notice that the character is used to denote multiplication of the decision variables by the units of machine time and wood that one unit of each uses in the Lathe and Boxwood con straints The modeling language distinguishes between upper and lower case so Sma11 would be rec ognized as different from small Let s see what this all means A model is enclosed in a mode1 end model block The decision variables are declared as such in the declarations end declarations block Every decision variable must be declared LP MIP and QP variables are of type mpvar Several decision variables can be declared on the same line so declarations small large mpvar end declarations is exactly equivalent to what we first did By default Mosel assumes that all mpvar variables are constrained to be non negative unless it is informed ot
91. n integer variable i e one that can only take on integral values in a MIP problem we would have xintvar is_integer 2 1 3 The burglar problem revisited Consider this model model Burglar2 uses mmxprs declarations WIMAX 102 Maximum weight allowed ITEMS camera necklace vase picture tv video chest privek Index set for items VALUE array ITEMS of real Value of items WEIGHT array ITEMS of real Weight of items take array ITEMS of mpvar 1 if we take item i 0 otherwise end declarations Item ca ne va pi tv vi ch br VALUE 15 100 90 60 40 15 10 1 WEIGHT 2 20 20 30 40 30 60 10 Objective maximize total value Weight restriction sum i in ITEMS WEIGHT i take i lt WTMAX MaxVal sum i in ITEMS VALUE i take i All variables are 0 1 forall i in ITEMS take i is_binary maximize MaxVal Solve the MIP problem Print out the solution writeln Solution n Objective getobjval forall i in ITEMS writeln take i getsol take i end model What have we changed The answer is not very much e String indices ITEMS camera necklace vase picture tv video chest briek declares that this time ITEMS is a set of strings The indices now take the string values camera necklace etc If we run the model we get Solution
92. n knapsack C array range of real A array range of real B real xbest array range of integer pass integer real Hide the demand constraints forall j in WIDTHS sethidden Dem j true More about Integer Programming 67 Mosel User Guide Define the knapsack problem KnapCtr sum j in WIDTHS A j x j lt B KnapObj sum j in WIDTHS C 3 x 3 Integrality condition if pass 1 then forall j in WIDTHS x j is integer end if maximize KnapObj returned getobjval forall j in WIDTHS xbest 3 round getsol x 3 Reset knapsack constraint and objective unhide demand constraints KnapCtr 0 KnapObj 0 forall j in WIDTHS sethidden Dem j false end function To complete the model we add the following procedure show_new_pat to print every new pattern we find procedure show new pat dj real vx array range of integer declarations dw real end declarations writeln new pattern found with marginal cost dj write Widths distribution dw 0 forall i in WIDTHS do write WIDTH i vx i y dw WIDTH i vx i end do writeln Total width dw end procedure end model More about Integer Programming 68 Mosel User Guide Chapter 12 Extensions to Linear Programming The two examples recursion and Goal Programming in this chapter show how Mosel can be used to implement extensions of Linear Programming 12 1 Recursion Recursion more properly known as Success
93. n using two separate i then statements but it is more efficient to use if then elif then else if the cases that are tested are mutually exclusive e case Depending on the value of an expression do something case A of MAX INT 10 x gt 39 20 MAX_ INT x lt 7 12 15 x 1 else x 0 endif Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20 and the lower bound 35 is applied if the value of A is less or equal 10 In addition x is fixed to 1 if A has value 12 or 15 and fixed to 0 for all remaining values An example for the use of the case statement is given in Section 12 2 The following example uses the if then elif then statement to compute the minimum and the maximum of a set of randomly generated numbers model Minmax declarations SNumbers set of integer LB 1000 Elements of SNumbers must be between LB UB 1000 and UB end declarations Generate a set of 50 randomly chosen numbers forall i in 1 50 SNumbers round random 200 100 writeln Set SNumbers size getsize SNumbers minval UB maxval LB forall p in SNumbers if p lt minval then minval p elif p gt maxval then maxval p end 1f writeln Min minval Max maxval end model Instead of writing the loop above it would of course be possible to use the corresponding operators min and max provided by Mosel writeln Min min p in SNumbers p
94. ng modeling objects and solution values Using the Mosel libraries it is not only possible to compile and run models but also to access information on the different modeling objects 13 3 1 Accessing sets A complete version of a program for running the model Prime mentioned in the previous section may look as follows we work with a model prime2 that corresponds to the one printed in Section 8 2 but with all output printing removed because we are doing this in C include lt stdio h gt include xprm_mc h int main XPRMmodel mod XPRMalltypes rvalue setitem XPRMset set int result type i size first last if XPRMinit Initialize Mosel return 1 if XPRMexecmod NULL prime2 mos LIMIT 500 amp result amp mod return 2 Execute the model type XPRMfindident mod SPrime amp rvalue Get the object SPrime if XPRM_TYP type XPRM_TYP_INT Check the type XPRM_STR type XPRM_STR_SET it must be a set of integers return 3 set rvalue set size XPRMgetsetsize set Get the size of the set if size gt 0 first XPRMgetfirstsetndx set Get number of the first index last XPRMgetlastsetndx set Get number of the last index printf Prime numbers from 2 to d n LIM for i first i lt last i Print all set elements printf d XPRMgetelsetval set i amp setitem integer printf Xn C interface 79 Mosel User Guide
95. nts Goal 7 x 3 y gt 40 Goah 10 x 5 y 60 Goal3 5 x 4 y gt 35 where the order given corresponds to their priorities 12 2 2 Implementation To increase readability the implementation of the Mosel model is organized into three blocks the problem is stated in the main part procedure preempt ive implements the solution strat egy via preemptive Goal Programming and procedure print_sol produces a nice solution printout model GoalCtr uses mmxprs forward procedure preemptiv forward procedure print_sol i integer declarations NGOALS 3 Number of goals x y mpvar Decision variables Extensions to Linear Programming 72 Mosel User Guide dev array 1 2 NGOALS MinDev linctr Goal array 1 NGOALS end declarations 100 x 60 y lt 600 Define the goal constraints Goal 1 T x 3 y gt 40 Goal 2 10 5 y 60 Goal 3 DER 4 y gt 35 preemptive of mpvar of linctr Deviation from goals Objective function Goal constraints Define a constraint Pre emptive Goal Programming At the end of the main part we call procedure preemptive to solve this problem by pre emptive Goal Programming In this procedure the goals are at first entirely removed from the problem hidden We then add them successively to the problem and re solve it until the problem becomes infeasible that is the deviation variables forming the objective function are not all 0 Depending on the
96. ond version of this loop foral1 do may enclose a block of statements the end of which is marked by end do Note that the indices of a forall loop can not be modified inside the loop Furthermore they must be new objects a symbol that has been declared cannot be used as index of a forall loop The following example that calculates all perfect numbers between 1 and a given upper limit combines both types of the forall loop A number is called perfect if the sum of its divisors is equal to the number itself model Perfect parameters LIMIT 100 end parameters writeln Perfect numbers between 1 and LIMIT forall p in 1 LIMIT do sumd 1 forall d in 2 p 1 if p mod d 0 then Mosel s built in mod operator sumd d The same as sum sum d end if if p sumd then writeln p end if end do end model The outer loop encloses several statements we therefore need to use orall do The inner loop only applies to a single statement if statement so that we may use the inline version forall If run with the default parameter settings this program computes the solution 1 6 28 Flow control constructs 39 Mosel User Guide 7 2 1 1 Multiple indices The forall statement just like the sum operator and any other statement in Mosel that re quires index set s may take any number of indices with values in sets of any basic type or ranges of integer values If two or more indices have the same set of values as in
97. or There is still a problem in line 10 this time it shows up at the very end of the line Although everything appears to be correct the parser does not seem to know what to do with maximi ze The solution to this enigma is that we have forgotten to load the module mmxprs that provides the optimization function maximize To tell Mosel that this module is used we need to add the line uses mmxprs immediately after the start of the model before the declarations block Forgetting to specify mmxprs is another common error We now have a closer look at line 12 which has now be come line 13 due to the addition of the uses statement All subroutines called in this line writeln and getobjval are provided by Mosel so there must be yet another problem we have forgotten to close the parentheses After adding the closing parenthesis after getobjval the model finally compiles without displaying any errors If we run it we obtain the desired output Best profit is 1333 33 Returned value 0 Besides the detection of syntax errors Mosel may also give some help in finding run time errors It should only be pointed out here that it is possible to add the flag g to the compile command to obtain some information about where the error occurred in the program Also useful is turning on verbose reporting for instance setparam XPRS_VERBOSE true setparam XPRS_LOADNAMES true Correcting syntax errors in Mosel 34 Mosel User Guide Il
98. ort 41 silent option 9 solution value 80 solving 7 sorting algorithm 41 51 sparse 21 23 57 81 sparsity 19 Special Ordered Set of type one 26 29 Special Ordered Set of type two 26 spreadsheet 17 strfmt 54 string 32 43 subproblem 74 subroutine 48 declaration 51 definition 51 overloading 52 parameter 49 subscript 11 subset 46 90 Successive Linear Programming 69 sum 32 summation 12 superset 46 syntax error 33 table see array tape set 43 then 32 to 32 tolerance value 62 transport problem 19 81 true 32 type constant 11 constraint 73 union 45 union 32 until 32 uses 17 32 variable 5 binary 13 25 conditional creation 22 integer 13 25 partial integer 25 semi continuous 26 semi continuous integer 26 warning 34 while 32 39 42 46 while do 39 40 write 8 54 writeln 8 23 54 56 XPRMexecmod 78 79 XPRMfinddso 83 XPRMfindident 80 XPRMgetarrdim 82 XPRMgetarrsets 82 XPRMgetelsetval 80 XPRMgetfirstarrentry 81 XPRMget firstarrtruentry 82 XPRMget firstsetndx 80 XPRMgetlastsetndx 80 XPRMgetnextarrentry 81 XPRMgetnextarrtruentry 82 XPRMloadmod 78 XPRMrunmod 78 XPRS_LOADNAMES 34 XPRS_PROBLEM 83 XPRS_SOLUTIONFILE 64 XPRS_VERBOSE 34 ZEROTOL 62 Xpress Mosel User Guide
99. ppose that we have a set of decision variables x i where we do not know the set of i for which x 1 exist until we have read data into an array WHICH model doesx declarations IR 1 15 WHICH set of integer x dynamic array IR of mpvar end declarations Read data from file initializations from doesx dat WHICH end initializations Create the x variables that exist forall i in WHICH create x i Build a little model to show what esists Obj sum i in IR x i C sum i in IR i x i gt 5 exportprob 0 0b3 Display the model end model If the data in doesx dat are WHICH 1 4 7 11 14 the output from the model is More advanced modeling features 22 Mosel User Guide Minimize x 1 x 4 x 7 x 11 x 14 Subject To C x 1 4 x 4 7 x 7 11 x 11 14 x 14 gt 5 Bounds End Note exportprob 0 Obj isa nice idiom for seeing on screen the problem that has been created The key point is that x has been declared as a dynamic array and then the variables that exist have been created explicitly with create In the transport example in Section 3 1 we have seen a different way of declaring dynamic arrays the arrays are implicitly declared as dynamic arrays since the index sets are unknown at their declaration When we later take operations over the index set of x for instance summing we only include those x that have been created Another way to do this is model does
100. ramming Mixed Integer Programming 4 25 58 mmetc 23 31 mmodbc 17 31 mmsystem 31 mmxprs 7 30 34 83 mod 31 model 6 compile 77 execute 8 run 8 model 7 31 model file 77 module 30 MP see Mathematical Programming mpvar 7 12 21 31 43 multiple indices 40 multiple problems 67 MVLB constraint 60 name constraint 12 negation 46 nested loops 42 next 32 non negativity constraint 6 not 32 46 objective function 6 7 of 32 opearator set 46 optimization 7 options 32 or 32 output 8 file 56 formatted 72 formatting 54 overloading 52 parameter 16 global 49 local 49 subroutine 49 parameters 32 partial integer variable 25 Xpress Mosel User Guide Index perfect number 39 prime number 45 79 problem multiple 67 solving 7 procedure 48 procedure 32 48 prod 32 project planning problem 27 public 32 Quadratic Programming 4 quick sort 51 range 32 39 range set 11 real 32 43 recursion 50 69 reference row entries 26 repeat 32 repeat until 39 41 42 returned 48 row see constraint run 8 77 selection statements 37 semi continuous integer variable 26 semi continuous variable 26 set 43 79 comparison 46 constant 23 43 dynamic 43 finalized 23 fixed 43 44 initialization 43 maximum 38 minimum 38 string indices 13 type 43 set 32 set of strings 13 set operation 45 set operator 46 sethidden 67 74 shell s
101. ray return 5 varr rvalue array type XPRMfindident mod VALUE amp rvalue Get the model object VALUE if XPRM_TYP type XPRM_TYP_REAL Check the type XPRM_STR type XPRM_STR_ARR it must be an array of reals return 6 darr rvalue array type XPRMfindident mod ITEMS amp rvalue Get the model object ITEMS if XPRM_TYP type XPRM_TYP_STRING Check the type XPRM_STR type XPRM_STR_SET it must be a set of strings return 7 set rvalue set XPRMgetfirstarrentry varr indices Get the first entry of array varr we know that the array is dense 80 Mosel User Guide 13 3 3 C interface and has a single dimension do XPRMgetarrval varr indices 8 x Get a variable from varr XPRMgetarrval darr indices tval Get the corresponding value printf take s g t item value g n XPRMgetelsetval set indices 0 amp itemname string XPRMgetvsol mod Xx val Print the solution value while XPRMgetnextarrentry varr indices Get the next index tuple return 0 The array of variables varr is enumerated using the array functions XPRMgetfirstarren try and XPRMgetnextarrentry These functions may be applied to arrays of any type and dimension for higher numbers of dimensions merely the size of the array indices that is used to store the index tuples ha
102. red to as overloading An example of an overloaded function in Mosel is get sol if a variable is passed as a parameter it returns its solution value if the parameter is a constraint the function returns the evaluation of the corresponding linear expression using the current solution Function abs for obtaining the absolute value of a number has different return types de pending on the type of the input parameter if an integer is input it returns an integer value if it is called with a real value as input parameter it returns a real Function getcoeff is an example of a function that takes different numbers of parameters if called with a single parameter of type linctr it returns the constant term of the input constraint if a constraint and a variable are passed as parameters it returns the coefficient of the variable in the given constraint The user may define additional overloaded versions of any subroutines defined by Mosel as well as for his own functions and procedures Note that it is not possible to overload a function with a procedure and vice versa Using the possibility to overload subroutines we may rewrite the preceding example Quick sort as follows model Quick sort 2 parameters LIM 50 end parameters forward procedure qsort L array range of integer declarations T array 1 LIM of integer end declarations forall i in 1 LIM T i round 5 random LIM writeln T qsort T writeln T Function
103. rts dynamic objects which do not require pre sizing For instance you do not have to specify the maximum sizes of the indices of a variable x e Mosel models are pre compiled Mosel compiles a model into a binary file which can be run on any computer platform and which hides the intellectual property in the model if so required e Mosel is embeddable There is a runtime library which can be called from your favorite programming language if required You can access any of the model s objects from your programming language e Mosel is easily extended through the concept of modules It is possible to write a set of functions which together stand alone as a module Several modules are supplied by Dash including the Xpress MP Optimizer Support for user written functions and procedures is provided e The use of sets of objects is supported Constraints and variables etc can be added incrementally For instance column genera tion can depend on the results of previous optimizations so sub problems are supported The modeling component of Mosel provides you with an easy to use yet powerful language for describing your problem It enables you to gather the problem data from text files and a range of popular spreadsheets and databases and gives you access to a variety of solvers which can find optimal or near optimal solutions to your model What you need to know before using Mosel Before using Mosel you should be comfortable with the u
104. s dash optimization Xpress Mosel User Guide Release 1 4 Last update 1 April 2004 Published by Dash Optimization Ltd Copyright Dash Associates 1998 2003 All rights reserved All trademarks referenced in this manual that are not the property of Dash Associates are acknow ledged All companies products names and data contained within this user guide are completely fictitious and are used solely to illustrate the use of Xpress MP Any similarity between these names or data and reality is purely coincidental How to Contact Dash USA Canada and all Americas Dash Optimization Inc Information and Sales info dashoptimization com Licensing license usa dashoptimization com Product Support support usa dashoptimization com Tel 1 201 567 9445 Fax 1 201 567 9443 Dash Optimization Inc 560 Sylvan Avenue Englewood Cliffs NJ 07632 USA Japan Dash Optimization Japan Information and Sales info jp dashoptimization com Licensing license jp dashoptimization com Product Support support jp dashoptimization com Tel 81 43 297 8836 Fax 81 43 297 8827 WBG Marive East 21F FASuC B2124 2 6 Nakase Mihama ku 261 7121 Chiba Japan Worldwide Dash Optimization Ltd Information and Sales info dashoptimization com Licensing license dashoptimization com Product Support support dashoptimization com Tel 44 1926 315862 Fax 44 1926 315854 Quinton Lodge Binswood Avenue Leamington Spa Warwickshire CV32
105. s and procedures 52 Mosel User Guide procedure swap L array range of integer i j integer e same procedure body as in the preceding example end procedure procedure qsort L array range of integer s e integer A same procedure body as in the preceding example end procedure Start of the sorting process procedure qsort L array r range of integer asort L getfirst r getlast r end procedure end model The procedure qsort_start is now also called qsort The procedure bearing this name in the first implementation keeps its name too it has got two additional parameters which suffice to ensure that the right version of the procedure is called To the contrary it is not possible to give procedure swap the same name qsort because it takes exactly the same parameters as the original procedure qsort and hence it would not be possible to differentiate between these two procedures any more Functions and procedures 53 Mosel User Guide Chapter 10 Output 10 1 Producing formatted output In some of the previous examples the procedures write and writeln have been used for displaying data solution values and some accompanying text To produce better formatted output these procedures can be combined with the formatting procedure strfmt In its sim plest form st rfmt s second argument indicates the minimum space reserved for writing the first argument and its placement within this space negative values mean
106. s not have to be the same as that in the initializations block equally acceptable would have been the statements initializations from blend dat AVAIL GRADE COST end initializations Alternatively since all data arrays have the same indices they may be given in the form of a single record such as BLENDDATA in the following data file blendb dat COST AVAIL GRADE BLENDDATA 85 60 241 93 45 6 3 In the initializations block we need to indicate the label of the data record and in which order the data of the three arrays is given initializations from blendb dat COST AVAIL GRADE as BLENDDATA end initializations 2 2 3 Re running the model with new data There is a problem with the model we have just presented the name of the file contain ing the costs date is hard wired into the model If we wanted to use a different file say blend2 dat then we would have to edit the model and recompile it Mosel has parameters to help with this situation A model parameter is a symbol the value of which can be set just before running the model often as an argument of the run command of the command line interpreter model Blend 2 uses mmxprs parameters DATAFILE blend dat end parameters declarations REV 125 Unit revenue of product MINGRADE 4 Minimum permitted grade of product MAXGRADE 5 Maximum permitted grade of product ORES 1 2 Range of ores
107. s the recur sion but it has not yet been defined The recursion on x and the balance t 1 T 1 is implemented by the following steps a The B _1 in constraints Interest get the prior solution value of balance 4 b The X in constraints Interest get the prior solution value of x c The X in constraint Def gets the prior solution value of x We say we have converged when the change in dx variation is less than 0 000001 TOLE RANCE By setting Mosel s comparison tolerance to this value the test variation gt O checks whether variation is greater than TOLERANCE procedure solve_recurs declarations TOLERANCE 0 000001 Convergence toleranc variation real Variation of x BC array QUARTERS of real end declarations setparam zerotol TOLERANCE Set Mosel comparison tolerance variation 1 0 ct 0 while variation 0 do savebasis 1 Save the current basis ct 1 forall t in 2 T BC t 1 getsol balance t 1 Get solution values for balance t s XC getsol x and x write Round ct x getsol x variation variation writeln Simplex iterations getparam XPRS_SIMPLEXITER forall t in 2 T do Update coefficients Interest t BC t 1 B t 1 dx B t 1 BC t 1 Interest t XC X balance t 1 end do Def XC X X XC oldxval XC Store solution value of x Extensions to Linear Programming 71 Mos
108. s to be adapted With these functions we run systematically through all possible combinations of index tuples hence the hint at dense arrays in the exam ple In the case of sparse arrays it is preferrable to use different enumeration functions that only enumerates those entries that are defined see next section Sparse arrays In Chapter 3 the problem Transport has been introduced The objective of this problem is to calculate the flows flow from a set of plants to a set of sales regions that satisfy all demand and supply constraints and minimize the total cost Not all plants may deliver goods to all regions The flow variables flow are therefore defined as a sparse array The following example prints out all existing entries of the array of variables include lt stdio h gt include xprm_rt h int main XPRMmodel mod XPRMalltypes rvalue XPRMarray varr XPRMset sets int indices dim result type i iff XPRMinit Initialize Mosel return 1 if mod XPRMloadmod transport bim NULL NULL Load a BIM file return 2 if XPRMrunmod mod amp result NULL Run the model return 3 type XPRMfindident mod flow amp rvalue Get the model object named flow if XPRM_TYP type XPRM_TYP_MPVAR Check the type XPRM_STR type XPRM_STR_ARR it must be an array of unknowns return 4 varr rvalue array dim XPRMgetarrdim varr
109. se of symbols such as x or y to rep resent unknown quantities and the use of this sort of variable in simple linear equations and inequalities for example X y lt 6 Experience of a basic course in Mathematical or Linear Programming is worthwhile but is not essential Similarly some familiarity with the use of computers would be helpful For all but the simplest models you should also be familiar with the idea of summing over a range of variables For example if produce is used to represent the number of cars produced 2 Xpress Mosel User Guide on production line j then the total number of cars produced on all N production lines can be written as N p produce j 1 This says sum the output from each production line produce over all production lines j from j21tojzN If our target is to produce at least 1000 cars in total then we would write the inequality N 5 produce gt 1000 j 1 We often also use a set notation for the sums Assuming that LINES is the set of production lines 1 N we may write equivalently y produce gt 1000 jELINES This may be read sum the output from each production line produce over all production lines jin the set LINES Other common mathematical symbols that are used in the text are IN the set of non negative integer numbers 0 1 2 n and U intersection and union of sets and v logical and and or the all quantifier V read for all and 3 read
110. t that is a set of consecutive integers from 1 to 8 This range is used as an index set for the data arrays VALUE and WEIGHT and for the array of decision variables take e Arrays VALUE array ITEMS of real defines a one dimensional array of real values indexed by the range ITEMS Exactly equiv alent would be VALUE array 1 8 of real Value of items Some illustrative examples 11 Mosel User Guide Multi dimensional arrays are declared in the obvious way e g VAL3 array ITEMS 1 20 ITEMS of real declares a 3 dimensional real array Arrays of decision variables type mpvar are declared likewise as shown in our example x array ITEMS of mpvar declares an array of decision variables take 1 take 2 take 8 All objects scalars and arrays declared in Mosel are always initialized with a default value real integer 0 boolean false string i e the empty string In Mosel reals are double precision e Assigning values to arrays The values of data arrays may either be assigned in the model as we show in the example or initialized from file see Section 2 2 VALUE 15 100 90 60 40 15 10 1 fills the VALUE array as follows VALUE 1 gets the value 15 VALUE 2 gets the value 100 VALUE 8 gets the value 1 For a 2 dimensional array such as declarations array 1 2 1 3 of real end declarations we migh
111. t write Pis Pll 12 13 21 22 23 which of course is the same as 111 12 13 21 22 23 but much more intuitive Mosel places the values in the tuple into EE going across the rows with the last subscript varying most rapidly For higher dimensions the principle is the same e Summations MaxVal sum i in Items VALUE 1 x 1 defines a linear expression called Maxval as the sum 5 VALUE Xi icltems e Naming constraints Optionally constraints may be named as in the chess set example In the remainder of this manual we shall name constraints only if we need to refer to them at other places in the model In most examples only the objective function is named here Maxval to be able to refer to it in the call to the optimization here maximize MaxVal e Simple Looping forall i in ITEMS take i is binary illustrates looping over all values in an index range Recall that the index range ITEMS is 1 8 SO the statement says that take 1 take 2 take 8 are all binary variables There is another example of the use of forall at the penultimate line of the model when writing out all the solution values Some illustrative examples 12 Mosel User Guide e Integer Programming variable types To make an mpvar variable say variable xbinvar into a binary 0 1 variable we just have to say xbinvar is_binary To make an mpvar variable a
112. tatements these are introduced first Selections Mosel provides several statements to express a selection between different actions to be taken in a program The simplest form of a selection is the if then statement e if then If a condition holds do something For example if A gt 20 then x lt 7 endif For an integer number A and a variable x of type mpvar x is constrained to be less or equal to 7 if Ais greater or equal 20 Note that there may be any number of expressions between then and endi not just a single one In other cases it may be necessary to express choices with alternatives e if then else If a condition holds do this otherwise do something else For example if A gt 20 then x lt 7 else x gt 35 endif Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20 otherwise the lower bound 35 is applied to it e if then elif then else If a condition holds do this otherwise if a second condition holds do something else etc if A gt 20 then x lt 7 elif A lt 10 then x gt 35 else x 0 endif 37 Xpress Mosel User Guide Here the upper bound 7 is applied to the variable x if the value of A is greater or equal 20 and if the value of A is less or equal 10 then the lower bound 35 is applied to x In all other cases that is A is greater than 10 and smaller than 20 x is fixed to 0 Note that this could also be writte
113. ter 1 It presents some further examples of the use of Mosel and introduces new features e Use of subsripts Almost all models of any size have subscripted variables We show how to define arrays of data and decision variables introduce the different types of sets that may be used as index sets for these arrays and also simple loops over these sets e Working with data files Mosel provides facilities to read from and write to data files in text format and also from other data sources databases and spreadsheets 2 1 The burglar problem A burglar sees 8 items of different worths and weights He wants to take the items of greatest total value whose total weight is not more than the maximum WTMAX he can carry 2 1 1 Model formulation We introduce binary variables take for all in the set of all items ITEMS to represent the decision whether item i is taken or not take has the value 1 if item i is taken and O other wise Furthermore let VALUE be the value of item and WEIGHT its weight A mathematical formulation of the problem is then given by maximize 5 VALUE take icITEMS 5 WEIGHT take lt WTMAX weight restriction icITEMS Vi ITEMS take 0 1 The objective function is to maximize the total value that is the sum of the values of all items taken The only constraint in this problem is the weight restriction This problem is an example of a knapsack problem 2 1 2 Implementation It may be
114. terface user guide that is provided as a separate document The Mosel Native Interface requires an additional licence 76 Xpress Mosel User Guide Chapter 13 C interface This chapter gives an introduction to the C interface of Mosel It shows how to execute models from C and how to access modeling objects from C It is not possible to make changes to Mosel modeling objects from C using this interface but the data and parameters used by a model may be modified via files or run time parameters 13 1 Basic tasks To work with a Mosel model in the C language or with the command line interpreter it always needs to be compiled then loaded into Mosel and executed In this section we show how to perform these basic tasks in C 13 1 1 Compiling a model in C The following example program shows how Mosel is initialized in C and how a model file extension mos is compiled into a binary model BIM file extension bim To use the Mosel Model Compiler Library we need to include the header file xprm_mc h at the start of the C program For the sake of readability in this program as for all others in this chapter we only implement a rudimentary testing for errors tinclude lt stdlib h gt tinclude xprm_mc h int main if XPRMinit Initialize Mosel return 1 if XPRMcompmod NULL burglar2 mos NULL Knapsack example return 2 Compile the model burglar2 mos output the file burglar2 bim return 0 With version 1
115. tes its name the parameters type and name and in the case of a function the type of the return value The definition that must follow later in the program contains the body of the subroutine that is the actions to be executed by the subroutine The following example implements a quick sort algorithm for sorting a randomly generated array of numbers into ascending order The procedure qsort that starts the sorting algorithm is defined at the very end of the program it therefore needs to be declared at the beginning before it is called Procedure qsort start calls the main sorting routine qsort Since the definition of this procedure precedes the place where it is called there is no need to declare it but it still could be done Procedure qsort calls yet again another subroutine swap The idea of the quick sort algorithm is to partition the array that is to be sorted into two parts The left part containing all values smaller than the partitioning value and the right part all the values that are larger than this value The partitioning is then applied to the two subarrays and so on until all values are sorted model Quick sort 1 parameters LIM 50 end parameters forward procedure qgsort start L array range of integer declarations T array 1 LIM of integer end declarations forall i in 1 LIM T i round 5 random LIM writeln T qsort start T writeln T Swap the positions of two numbers in an arra
116. th a call to procedure tree_cut_gen before starting the optimiza tion preceded by the declaration of the procedure using forward earlier in the program To avoid initializing the solution arrays and the feasibility tolerance repeatedly we now turn these into globally defined objects declarations feastol real Zero tolerance solc array CONTR SITES of real Sol values for variables clean sola array CONTR AREAS of real Sol values for variables alloc end declarations tree_cut_gen Set up cut generation in B amp B tree minimize Cost Solve the MIP problem As we have seen before procedure tree cut gen disables the default cut generation and turns presolve off It also indicates the number of extra rows to be reserved in the matrix for the cuts we are generating procedure tree cut gen Setparam XPRS CUTSTRATEGY 0 Disable automatic cuts Setparam XPRS PRESOLVE 0 Switch presolve off Setparam XPRS EXTRAROWS 5000 Reserve extra rows in matrix feastol getparam XPRS FEASTOL Get the zero toleranc Setparam zerotol feastol 10 Set the comparison tolerance of Mosel setcallback XPRS CB CM cb node end procedure The last line of this procedure defines the cut manager entry callback function that will be called by the optimizer from every node of the Branch and Bound search tree This cut gener ation routine function cb node performs
117. that the startpm are ordered and the LP solution is telling us it looks as if the best month to start is somewhere midway between the first and the last month When sets are present the IP can branch on sets of variables It might well separate the months into those before the middle of the period and those later It can then try forcing all the early startpm to 0 and restricting the choice of the one start that can be 1 to the later startpm It has this option because it now has the information to know what is an early and what is a late startpm whereas these variables were unordered in the binary formulation The power of the set formulation can only really be judged by its effectiveness in solving large difficult problems When it is incorporated into a good IP system such as Xpress MP it is often found to be an order of magnitude better than the equivalent binary formulation for large problems Integer Programming 29 Mosel User Guide Chapter 5 Overview of subroutines and reserved words There is a range of built in functions and procedures available in Mosel They are described fully in the Mosel Language Reference Manual Here is a summary e Accessing solution values getsol getact getcoeff getdual getrcost getslack getobjval e Arithmetic functions arctan cos sin ceil floor round exp 1n log sqrt isodd e List functions maxlist minlist e String functions strfmt substr e Dynamic array handling create finali
118. the non binary global entities often yields very considerable reductions in solution times over ones that just use binary variables To illustrate the use of Mosel in modeling Integer Programming problems a small example follows The first formulation uses binary variables This formulation is then modified use Special Ordered Sets For the interested reader an excellent text on Integer Programming is Integer Programming by Laurence Wolsey Wiley Interscience 1998 ISBN 0 471 28366 5 4 2 A project planning model A company has several projects that it must undertake in the next few months Each project lasts for a given time its duration and uses up one resource as soon as it starts The resource profile is the amount of the resource that is used in the months following the start of the project For instance project 1 uses up 3 units of resource in the month it starts 4 units in its second month and 2 units in its last month The problem is to decide when to start each project subject to not using more of any resource in a given month than is available The benefit from the project only starts to accrue when the project has been completed and then it accrues at BEN per month for project p up to the end of the time horizon Below we give a mathematical formulation of the above project planning problem and then display the Mosel model form 4 2 1 Model formulation Let PROJ denote the set of projects and MONTHS 1 NM the
119. unction getsize that if applied to a set returns the number of elements of the set The condition in the wnile loop is the logical negation of an expression marked with not the loop is repeated as long as the condition n in SNumbers is not satisfied 8 2 1 Setoperators The preceding example introduces the operator to add sets to a set there is also an operator to remove subsets from a set Another set operator used in the example is in denoting that a single object is contained in a set We have already encountered this operator in the enumeration of indices for the fora11 loop Mosel also defines the standard operators for comparing sets subset lt superset gt dif ference end equality 2 Their use is illustrated by the following example model Set comparisons declarations RAINBOW red orange yellow green blue purple BRIGHT yellow orange DARK blue brown black end declarations writeln BRIGHT is included in RAINBOW BRIGHT lt RAINBOW writeln RAINBOW is a superset of DARK RAINBOW gt DARK writeln BRIGHT is different from DARK BRIGHT lt gt DARK writeln BRIGHT is the same as RAINBOW BRIGHT RAINBOW end model As one might have expected this example produces the following output BRIGHT is included in RAINBOW true Sets 46 Mosel User Guide RAINBOW is a superset of DARK false BRIGHT is different from DARK true BRIGH
120. utput something like that below where we have highlighted Mosel s output in bold face mosel Xpress Mosel c Copyright Dash Associates 1998 2002 gt compile chess Compiling chess load chess gt run Make 0 small sets Make 66 6667 large sets Best profit is 1333 33 Returned value 0 quit Exiting Since the compile load run sequence is so often used it can be abbreviated to cl chess run or simply exec chess The same steps may be done immediately from the command line mosel c cl chess run or Getting started with Mosel 8 Mosel User Guide mosel c exec chess The c option is followed by a list of commands enclosed in double quotes With Mosel s silent s option mosel s c exec chess the only output is Make 0 small sets Make 66 6667 large sets Best profit is 1333 33 1 2 4 Using Xpress IVE Under Microsoft Windows you may also use Xpress IVE sometimes called just IVE the Xpress Interactive Visual Environment for working with your Mosel models Xpress IVE is a complete modeling and optimization development environment that presents Mosel in an easy to use Graphical User Interface GUI with a built in text editor To execute the model file chess mos you need to carry out the following steps e Start up IVE e Open the model file by choosing File gt Open The model source is then displayed in the central window the IVE Editor e Click the Run button green tr
121. x2 declarations WHICH set of integer end declarations initializations from doesx dat WHICH end initializations finalize WHICH declarations x array WHICH of mpvar Here the array is not dynamic end declarations because the set has been finalized Obj sum i in WHICH x i C sum i in WHICH i x i gt 5 exportprob 0 Obj end model By default an array is of fixed size if all of its indexing sets are of fixed size i e they are either constant or have been finalized Finalizing turns a dynamic set into a constant set consisting of the elements that are currently in the set All subsequently declared arrays that are indexed by this set will be created as static fixed size The second method has two advantages it is more efficient and it does not require us to think of the limits of the range IR a priori 3 3 Reading sparse data Suppose we want to read in data of the form i j value from an ASCII file setting up a dynamic array A range range with just the A i 3j value jj for the pairs i j which exist in the file Here is an example which shows three different ways of doing this We read data from differently formatted files into three different arrays and using writeln show that the arrays hold identical data The first method using the initializations block has already been introduced transport problem in Section 3 1 The second way of setting up and accessing data demonstrates t
122. y procedure swap L array range of integer i j integer k L i i L 3 L 3 k end procedure Main sorting routine procedure qsort L array range of integer s e integer v L ste div 2 Determine the partitioning value i s j e repeat Partition into two subarrays while L i lt v i 1 while L j v 3 1 if i lt j then swap L i j i 1 j 1 end if until i j Functions and procedures 51 Mosel User Guide Recursively sort the two subarrays if j e and s j then qsort L s j end if if i gt s and i e then qsort L i e end 1f end procedure Start of the sorting process procedure qsort start L array r range of integer qsort L getfirst r getlast r end procedure end model The quick sort example above demonstrates typical uses of subroutines namely grouping ac tions that are executed repeatedly qsort and isolating subtasks swap in order to structure a program and increase its readability The calls to the procedures in this example are nested procedure swap is called from qsort which is called from qsort start in Mosel there is no limit as to the number of nested calls to subroutines it is not possible though to define subroutines within a subroutine 9 5 Overloading of subroutines In Mosel it is possible to re use the names of subroutines provided that every version has a different number and or types of parameters This functionality is commonly refer
123. ze e File handling fclose fflush fopen fselect fskipline getfid iseof read readin e Accessing control parameters getparam setparam e Getting information getsize gettype getvars e Hiding constraints sethidden ishidden e Miscellaneous functions exportprob bittest random setcoeff settype exit 5 1 Modules The distribution of Mosel contains several modules that add extra functionality to the lan guage A full list of the functionality of a module can be obtained by using Mosel s exam command for instance mosel c exam mmsystem In this manual we always use Xpress Optimizer as solver Access to the corresponding opti mization functions is provided by the module mmxprs In the mmxprs module are the following useful functions e Optimize minimize maximize e MiP directives setmipdir clearmipdir e Handling bases savebasis loadbasis delbasis 30 Xpress Mosel User Guide Force problem loading loadprob Accessing problem status getprobstat Deal with bounds set1b setub getlb getub Model cut functions setmodcut clearmodcut For example here is a nice habit to get into when solving a problem with the Xpress MP Optimizer declarations Status array XPRS OPT XPRS UNF XPRS INF XPRS UNB of string end declarations Status Optimum found Unfinished Infeasible Unbounded minimize Obj writeln status getprobstat In the mmsystem module are various useful

Mosel user guide

Contents

Download Pdf Manuals

Related Search

Related Contents