ZIMPL User Guide
Contents
1. 1X XXX XX AXX XX KA VLAAKXX XAA TT NN KKK XY VN Konrad Zuse Zentrum GE en dr 5 German f r Informationstechnik Berlin i THORSTEN KOCH ZIMPL User Guide ZIB Report 01 20 August 2001 ZIMPL Zuse Institute Mathematical Programming Language Thorsten Koch 11 March 2001 Abstract ZIMPL is a little language to translate the mathematical model of a problem into a linear or mixed integer mathematical program expressed in 1p or mps file format which can be read by a LP or MIP solver May the source be with you Luke 1 Introduction Most of the things in ZIMPL and a lot more can be found in the wonderful book about the modelling language AMPL from Robert Fourer David N Gay and Brian W Kernighan FGK93 Indeed if not the guys at ILOG had needed more than three months just to tell me the price of AMPL for CPLEX I would probably use AMPL today On the other hand having the source code of a program has its atvantages The pos sibility to run it regardless of architecture and operating system the ability to modify it to suite the needs and not having to hassle with license managers may make a much less powerful program the better choice And so ZIMPL came into being A linear program LP might look like this min 2g Au subjectto x y lt 6 T Y gt 0 The usual format to store the description of such a problem is mps invented by IBM2. lt a gt in A ula yla sum lt a b c gt in C with a in E and b gt 3 a 2 zla b c Constraints The general format for a constraint is subto name term sense rhs Name can be any name starting with a letter The term is defined as in the objective Sense is one of lt gt and The rhs is any numeric expression Many constraints can be generated with one statement by the use of the forall instruction see below Examples subto time 3 xl 4 x2 lt 7 subto space sum lt a gt in A 2 ula yla gt 50 subto weird forall lt a gt in A sum lt a b c gt in C zla b c 55 Details on sum and forall The general forms are forall index do term and sum index do term The general form of index is tuple in set with boolean expression It is allowed to write a colon instead of do and a vertical bar instead of with The number of components in the tuple and in the components of the mebers of the set must match The with part of an index is optional The set can be any expression giving a set Examples forall lt i j gt in X cross 1 to 5 without lt 2 3 gt with i gt 5 and j lt 2 do sum lt 1i jJ k gt in X cross 1 to 3 cross Z do pli q j wlj k gt if i 2 then 17 else 53 ZIMPL Note that in the example i and j are set by the forall instruction So they are fixed for all invocations of sum Initialising sets and parameters from a file It is possi
3. 11 Reference Manual Dash Associates 1999 10
4. IBM97 long ago Nearly all available LP and MIP solvers can read this format While mps is a nice format to punch into a punch card and at least a reasonable format to read for a computer it is quite unreadable for humans ZIMPL NAME exl mps ROWS N OBJECTIV L cO COLUMNS x OBJECTIV 2 x CU 1 y OBJECTIV 3 y CU RHS RHS CU 6 ENDATA Another possibility is the 1p format ILO00 which is more readable but is only sup ported by a few solvers Minimize cost 2 x 3 y Subject to c0 1x 1 y lt 6 End But since each coefficient of the matrix A must be stated explicitly it is also not a desirable choice to develop a mathematical model Now with ZIMPL it is possible to write this var x var y minimize cost 2 x 3 y subto c0 x y lt 6 and have it automatically translated into mps or 1p format While this looks not much different from what is in the 1p format the difference can be seen if we use indexed variables Here is an example This is the LP min 27 32 1 523 subject to Der lt 6 And this is how to tell it ZIMPL set I Ss EL ee 3 Ee param c I lt 1 gt 2 lt 2 gt 3 lt 3 gt 1 5 var x I gt 0 minimize value sum lt i gt in I c i x i subto cons sum lt i gt in I x i lt 6 ZIMPL 2 Invocation To run ZIMPL on the model given in the file ex1 zp1 type the command zimpl exl zpl The general case is zimpl options lt input files g
5. ble to load the values for a set or a parameter from a file The syntax is read filename as template skip n use n s s comment s filename is the name of the file to read template is a string with a template for the tuples to generate Each input line from the file is split in fields The splitting is done according to the following rules Whenever a space tab comma semicolon or double colon is encountered a new field is started Text that is enclosed in double quotes is not split the quotes are allways removed When a field is split all space and tab charaters around the splitting are removed If the split is due to a comma semicolon or double colon each occurence of these characters starts a new field Examples All these lines have three fields Hallo 12 3 Moin Ek lt 2 Hallo Peter Nice to meet you 77 2 vy For each component of the tuple the number of the field to use for the value is given followed by either a n if the field should be interpreted as a number or s for a string Have a look at the example it is quite obvious how it works After the template some optional modifiers can be given The order does not matter skip n instructs to skip the first n lines of the file use n limits the number of lines to use to n comment s sets a list of characters that start comments in the file Each line is ended when any of the comment characters is found When a file is read empty lines are skiped and not cou
6. e end of the line is treated as a comment and is ignored If a line starts with the word include followed by a filename in double quotation marks this file is read instead of this line ZIMPL works on the lowest level with two types of data Strings and numbers A string is delimited by double quotation marks A number can be given as 2 6 5 or 5 234e 12 Wherever a number or string is required it is also possible to give a ZIMPL parameter of the right value type Also numeric expressions are allowed instead of just a number The precedence of numeric boolean and set operators should be the usual one If in doubt use parenthesis to be save Numeric expressions The following functions are currently implemented mod div A stands for to the power of mod is the modulo function and div gives the integer part of a division can be used as synonym for With min and max it is possible to find the minimum maximum member of an one dimension set of numeric values The following is also a numeric expression if boolean expression then numeric expression else numeric expression end Boolean expressions For numbers lt lt gt gt are defined For strings only and are available The expression tuple in set expression can be used to test set membership of a tuple Combinations of boolean expressions with and or and negation with not are possible Sets The elements of a set are tuples Each
7. meter optionally followed by the indexing set Then after the assignment sign comes a list of pairs The first element of each pair is a tuple from the index set the second element is the value of the parameter for this index Examples param q 5 param u A param w C oe II ne A 1 gt 17 lt 2 gt 29 lt 3 gt 12 12 eh 71 725 lt 6 5 y s 2735 II A In the example no value is given for index lt 787 12 6 oh gt of parameter w that is assignments need not to be complete This is correct as long as it is never referenced Variables Like parameters variables can be indexed A variable has to be one out of three pos sible types Continuous called real binary or integer The default is real Variables may have lower and upper bounds Defaults are zero as lower and infinity as upper bound Binary variables are always bounded between zero and one It is possible to compute the value of the lower or upper bounds depending on the index for the variable see last declaration in the example Examples var xl var x2 binary var y A real gt 2 lt 18 var z lt a b c gt in C integer gt a 10 lt if b lt 3 then p b else 10 end ZIMPL Objective There must be exactly one objective statement in a model The objective can be either minimize or maximize Following the keyword is a name a colon and then a term consisting of variables Example minimize cost 12 xl 4 4 x2 sum
8. nted for the use clause They are counted for the skip clause Examples set P read nodes txt as lt ls gt nodes txt Hamburg gt lt Hamburg gt Munchen gt lt M nchen gt Berlin gt lt Berlin gt ZIMPL set Q read blabla txt as blabla txt Name Nr X Y No Hamburg 12 x y 7 Bremen 4 x y 5 Berlin 2 x y 8 param cost P EOSELERTE Name Price Hamburg Munchen Berlin 1000 1200 1400 param cost Q haha txt 1 2 ab conl 2 33 ee 4 5 de con3 read read gt gt lt 1s 5n 2n gt skip 1 use 2 gt skip gt lt Hamburg 7 12 gt gt lt Bremen 5 4 gt gt skip cost txt as skip lt Hamburg gt lt M nchen gt lt Berlin gt haha txt as lt ab 1 2 gt coni lt bo 2 3 gt conl lt de 4 5 gt conl lt is gt An comment 1000 1200 1400 WZ3epln 2n gt 4g Ee WM ZIMPL 4 Error messages Here are some of the incomprehensible error messages ZIMPL can produce Comparison of different types It is not possible to compare a number with a string xxx of incompatible sets The members of the two sets involved in operation xxx have not the same number of components Illegal element xxx for symbol In the initialisation of a parameter tuple xxx is not a member in the index set WITH not allowed here When initialising the bounds of variables by index the with clause t
9. o exclude some of the elements is not allowed Comparison of different dimension tuples Two tuples were compared which have a different number of components This is never a good idea since such tuples are always different Comparison of elements with different types Two tuples were compared which have a different type for the n th element This is never a good idea since such tuples are always different Type error expected xxx got yyy In some context type xxx was expected but the interpreter found type yyy The meaning of the numbers could be looked up in code bh 5 Remarks ZIMPL is licensed under the GNU general public licence version 2 For more infor mation on free software see www gnu org The latest version of ZIMPL can be found at www zib de koch zimpl If you find any bugs you can email me at koch zib de Please include an example that shows the problem If somebody extends ZIMPL I am interested in getting patches to put them back in the main distri bution ZIMPL References FGK93 R Fourier D M Gray and B W Kernighan AMPL A Modelling Lan guage for Mathematical Programming boyd amp fraser publishing company Danvers Massachusetts 1993 IBM97 IBM Optimization Library Guide and Reference IBM Corp 1997 ILO00 ZLOG CPLEX 7 0 Reference Manual ILOG 2000 vH99 Pascal van Hentenryck The OPL Optimization Programming Language MIT Press Cambridge Massachusetts 1999 XPR99 XPRESS MP Release
10. t It is possible to give more than one input file They are read one after the other and then executed as if they were all in one big file The result of running ZIMPL will be either an error message or two files The two files are the problem generated from the model in either 1p or mps format with extension lp or mps anda file with the extension tb1 which lists all variable and constraint names used in the model and there corresponding name in the problem file The reason for this name translation is that the mps format can only handle names up to eight characters long And in LP format the length of the names is also restricted to 16 characters The following options are possible only the first two are normally of interest t format Selects the output format Can be either 1p which is default or mps oname Sets the base name for the output files Defaults to the first input file striped of the extension b Enables bison debugging output d Enables zimpl debugging output f Enables flex debugging output h Prints a usage message V Enables verbose mode A typical invocation is for example zimpl o hardone t mps data zpl model zpl This reads the files data zpl and model zp1l and produces hardone mps and hardone tbl 3 Format Each ZPL file consists of five types of statements Sets parameters variables an ob jective and constraints Each statement ends with a semicolon Everything from a number sign to th
11. tuple of a set has the same number of compo nents The components are either numbers or strings The type of the n th component of each tuple must be the same A tuple starts and ends with lt and gt resp The components are separated by commas If tuples are one dimensional it is possible to omit the braces in a list of elements but then they must be omitted from all tuples of the set Set functions A cross B Cross product Jr alle Ee AAy B A union B Union rjc e AVa bt A inter B Intersection srlr e AAz B A withoutB Difference ze e AArgB AsymdiffB Symmetric difference x e AAx B V xE BAz A ntom bys Generate Iris n is lt m i No default s 1 It is possible to write instead of cross instead of union or instead of without and instead of to ZIMPL Examples Set Ar 4 1225 3445 set B ha ha ho ka set C lt 1 2 x gt lt 6 5 y gt lt 787 12 6 oh gt set D A cross B set E 6 to 9 union A without lt 2 gt lt 3 gt Parameters Parameters can be declared with or without an indexing set Without indexing the pa rameter is just one value which is either a number or a string For indexed parameters there is one value for each member of the set There are not much uses for string valued parameters so normally they are all numbers Parameters are declared in the following way The keyword Garam is followed by the name of the para
Download Pdf Manuals
Related Search