ZIMPL User Guide
Contents
1. gt and gt are defined Combinations of boolean expressions with and or and xorfl and negation with not are possible The expression tuple in set expression can be used to test set membership of a tuple 4 2 Sets Sets consist of tuples The tuples in a sets are unordered i e each tuple can only be once in a set Sets are delimited by braces and resp Tuples consist of components The components are ordered Each tuple of a specific set has the same number of components The components are either numbers or strings The type of the n th component for all tuples of a set must be the same A tuple starts and ends with lt and gt resp e g lt 1 2 x gt The components are separated by commas If tuples are one dimensional it is possible to omit the tuple delimiters in a list of elements but then they must be omitted from all tuples of the set e g 1 2 3 Sets can be defined with the set statement It consists of the keyword set the name of the set an assignment operator and a valid set expression Sets are referenced by use of an template tuple consisting of placeholders that are replaced by the value of the components of the respective tuple For example a set S consisting of two dimensional tuples could be referenced by lt a b gt in S If any of the placeholders are actual values only those tuples will be extracted that match these values For example lt 1 b gt in S will only get those tuples whos2. IBM97 IBM optimization es guide and reference er For an online reference see IL002 ILOG CPLEX Division 889 Alder Avenue Suite 200 Incline Village NV 89451 USA ILOG CPLEX 8 0 Reference Manual 2002 Information available at http www cplex co Sch03 Alexander Schrijver Combinatorial Optimization Springer 2003 vH99 Pascal van Hentenryck The OPL Optimization Programming Language MIT Press Cambridge Massachusetts 1999 XPR99 XPRESS MP Release 11 Reference Manual Dash Associates 1999 Information available athttp www dashoptimization com 1 29 31
3. each row of the board Each variable can take the value of a column So we have n variables with bounds 1 n Next we use the vabs extended function to model an all different constraint on the variables see constraint cl This makes sure that no queen is located on the same column than any other queen The second constraint c2 is used to block all the diagonals of a queen This is done by demanding that the absolute row and the column distance of each pair of queens is different We model a 4 b by abs a b gt 1 Note that this formulation only works if a queen can be placed in each row i e the board size has to be at least 4 x 4 param queens 8 set I 1 queens set P lt i j gt in I I with i lt j var x I integer gt 1 lt queens subto cl forall lt i j gt in P do vabs x i x 3 gt 1 subto c2 forall lt i j gt in P do vabs vabs x i x 3 abs i j gt 1 Here we do the same with one binary variable for each field of the board The variable is one iff a queen is on this field We compute in advance which other fields are blocked if a queen is placed on a particular field Then we use the extended vif constraint to set the variables of the blocked fields to zero if a queens is placed param columns 8 set I c 1 1 columns set IXT 2 TT Ty set TABU lt i j gt in IxI lt m n gt in IxI with m 1 or n 3 and m i or n j
4. is built by appending the column index to the row index The value entries are separated by commas Any valid expression is allowed here As can be seen in the third example below it is possible to add a list of entries after the table Examples Sete LS ro ar 00 35 set id a tb ten We In ZU F3 param h I J tar VEN Wx N 11 12 17 99 23 13 4 Sed 3667859 ESI 2735 4 3 abs 4 19 1 2 0 3 default 99 param g I I I 15 25 Bril 11 1 0 Ly 0 11 2 E Ly 11 31 0 0 1 12 1 r 0 11 param k I I Top 8 9 141 89 67 55 5 12 13 14 lt 1 2 gt 17 lt 3 4 gt 99 11 ZIMPL 4 4 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 vari able see last declaration in the example Bounds can also be set to infinity and infinity 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 Remember if nothing is specified a lower bound of zero is assumed 4 5 Objective There must be at most o
5. 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 cl x y lt 6 The LP format has also some idiosyncratic restrictions For example variables should not be named e12 or the like And it is not possible to specify ranged constraints ZIMPL and have it automatically translated into MPS or LP format While this looks not much different from what is in the LP 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 x lt 6 And this is how to tell it to ZIMPL set I 1 to 3 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 lil se as subto cons sum lt i gt in I x i lt 6 3 Invocation To run ZIMPL on a model given in the file ex1 zp1 type the command zimpl exl zpl The general case is zimpl options lt input files gt It is possible to give more than one input file They are read one after the other as if they were all one big file If any error occurs while processing ZIMPL will print out an error message and abort In case everything goes well the results will be written into two or three files depending on the options specified The first file is the problem generated from the model in either LP or MPS fo
6. or abs m i abs n j var x IxI binary maximize queens sum lt i j gt in IxI x i j subto cl forall lt i j gt in IxI do vif x i j 1 then sum lt m n gt in TABU i j x m n lt 0 end 22 ZIMPL 6 Error messages Here is a complete list of the incomprehensible error messages ZIMPL can produce 101 Bad filename The name given with the o option is either missing a directory name or starts with a dot 102 File write error Some error occurred when writing to an output file A description of the error follows on the next line For the meaning consult your OS documentation 103 Output format not supported using LP format You tried to select another format then 1p mps or hum 104 File open failed Some error occurred when trying to open a file for writing A description of the error follows on the next line For the meaning consult your OS documentation 105 Duplicate constraint name xxx Two subto statements have the same name 106 Empty LHS constraint trivially violated One side of your constraint is empty and the other not equal to zero Most frequently this happens when a set to be summed up is empty 107 Range must bel lt x lt u oru gt x gt l If you specify a range you must have the same comparison operators on both sides 108 Empty Term with nonempty LHS RHS constraint trivially violated The middle of your constraint is empty and either the left or right hand side of th
7. to generate systems of constraints that mimic conditional constraints The general syntax is as follows note that the else part is optional vif boolean constraint then constraint else constraint end where boolean constraint consists of linear expression involving variables All these variables have to be bounded integer or binary variables It is not possible to use any continuous variables or integer variables with infinite bounds in a boolean constraint All comparison operators lt lt gt gt are allowed Also com bination of several terms with and or and xor and negation with not is possible The conditional constraints those which follow after then or else may include bounded continuous variables Be aware that using this construct will lead to the generation of several additional constraints and variables Examples var x i integer gt 0 lt 20 subto cl vif 3 x 1 x 2 7 then sum lt i gt in I y i lt else sum lt k gt in K z k gt 5 end subto c2 vif x 1 1 and x 2 gt 5 then x 3 7 end subto c3 forall lt i gt in I vif x i gt 2 then x i 1 lt 4 end 4 12 Extended Functions experimental It is possible to use special functions on terms with variables that will automatically converted to a system of inequalities The arguments of these functions have to be linear terms consisting of bounded integer or binary variables The following functions are def
8. TORES lt 1 gt 10 lt 2 gt 14 lt 3 gt 17 lt 4 gt 8 lt 5 gt 9 lt 6 gt 12 lt 7 gt 11 lt 8 gt 15 lt 9 gt 16 Transportation cost from each plant to each store param transport PS ly 27 By 35 Gy Tr 8 9 IAI 55 4 17 33 47 98 19 10 6 B 42 12 4 23 16 78 47 9 82 20 ZIMPL UCM UI S4 Gr 255 Te OT 45 gt 13 aad D 60 8 79 24 28 19 62 18 45 var x PS binary Is plant p suppling store s var z PLANTS binary Is plant p build We want it cheap minimize cost sum lt p gt in PLANTS building p z p sum lt p s gt in PS transport p s x p s Each store is supplied by exactly one plant subto assign forall lt s gt in STORES sum lt p gt in PLANTS x p s 1 To be able to supply a store a plant must be build subto build forall lt p s gt in PS x p s lt z p The plant must be able to meet the demands from all stores that are connected to it subto limit forall lt p gt in PLANTS sum lt s gt in S demand s x p s lt capacitylp The optimal solution in this case is to build plants A and C Stores 2 3 and 4 are served by plant A the rest by plant C Total cost would be 1457 21 ZIMPL 5 4 n Queens Problem We now show two formulations of the n Queens problems using extended constraints and functions The first formulation uses one general integer variable for
9. The set given to build the powerset of was the empty set 147 use value xxx is too big or not an integer The use value must be given as an integer smaller than two billion 148 use value xxx is not positive Negative or zero values for the use parameter are not allowed 26 ZIMPL 149 skip value xxx is too big or not an integer The skip value must be given as an integer smaller than two billion 150 skip value xxx is not positive Negative or zero values for the skip parameter are not allowed 151 Not a valid read template A read template must look something like lt 1n 2n gt There have to be a lt and a gt in this order 152 Invalid read template syntax Apart from any delimiters like lt gt and commas a template must consists of number character pairs like 1n 3s 153 Invalid field number xxx The field numbers in a template have to be between 1 and 255 154 Invalid field type xxx The only possible field types are n and s 155 Invalid read template not enough fields There has to be at least one field inside the delimiters 156 Not enough fields in data The template specified a field number that is higher than the actual number of field found in the data 157 Not enough fields in data value The template specified a field number that is higher than the actual number of field found in the data The error occurred after the index tuple in the value field 158 Read from file found no data Not a single record co
10. ZIMPL User Guide Zuse Institute Mathematical Programming Language Thorsten Koch for Version 2 01 29 October 2003 Contents 3 4 3_ Invocatio 5 10 12 Ll a As de aS 12 BLE Se ly abe ns SEE 12 47 Detailson sumand foralll 2 Ho onen 13 Details on if in constraintsl 2 2 gt Ho Hm 13 14 15 16 4 12 Extended Functions experimental 16 4 13 Thedo print and do checkcommands 17 18 a ii ee EE de sde Be E 18 DE YO e orne AR RN 19 ie pe be eee aba 20 ee enge 22 ZIMPL 6 Error messages 23 ZIMPL Abstract ZIMPL is a little language to translate the mathematical model of a problem into a linear or mixed integer mathematical program expressed in LP or MPS file format which can be read by a LP or MIP solver 1 Preface May the source be with you Luke Most of the things in ZIMPL and a lot more can be found in the excellent book about the modeling language AMPL from Robert Fourer David N Gay and Brian W Kernighan FGK03 But having the source code of a program has its advantages The possibility 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 By now ZIMPL has grown up and matured It has been used in several industry projects and university lectur
11. by the with clause is evaluated for each tuple in the set and only tuples for which the expression evaluated to true are included in the new set ZIMPL Examples set F lt i j gt in Q with i gt Jjandi lt 5 set A S5 Manz No Ton y set B 1 2 3 set V lt a 2 gt in A B with a a or a b will give lt a 2 gt lt b 2 gt Indexed sets It is possible to index one set with another set Here is a list of functions that use this powerset A Generates all subsets of A X X C A subset A n Generates all subsets of A with n elements X X CAA X n indexset A The index set of A 1 A Indexed sets are accessed by adding the index of the set in brackets and like S 7 There are three possibilities how to assign to an indexed set The assignment expression is a list of comma separated pairs consisting of a tuple from the index set and a set expression to assign A set reference expression is given as index then the assignment expression is evaluated for each index tuple By use of a function that returns an indexed set Examples set I O A ESO he set A I sa ala a MMT lt 2 gt mom Man P lt 3 gt en set B lt i gt in I 3 i set P powerset 1 set J indexset P set S subset I 2 set K lt i gt in I if i mod 2 O then i else i end 4 3 Parameters Parameters can be declared with or without an index
12. e first component is 1 Please note that if one of the placeholders is the name of an already defined parameter set or variable it will be substituted This will result either in an error or an actual value a Abvanb ZIMPL Examples set A set B set C 1 2 3 What ha ho Eliza x gt LOO ANA LIET 712667 OR gt 45 For set expressions these functions and operators are defined A B A cross B A B A union B A inter B A B A wi A symdiff B Cross product Union Intersection A B thout B Difference Symmetric difference In m n to m by s Generate default s 1 proj A t Projection t 1 n if a then b else c conditional 1 y Tr AAyE B rje Ee AVa B lrlre AAze Bh rjc E AAz B ze e Ang B Vi reE BrzgA alc n is lt m i No The new set will consist of n tuples with the i th component being the e th component of A An example for the use of the if boolean expression then set expression else set expression end can be found below with the examples for indexed sets Examples set D A cross B set E 6 to 9 union A without lt 2 gt lt 3 gt set F le AO Do RS fe BOY ESLORA MAM NBS Le set G proj F lt 3 1 gt will give lt A 1 gt lt A 2 gt lt B 9 gt Conditional sets It is possible to restrict a set to tuples that satisfy a boolean expression The expression given
13. e range is not zero This most frequently happens when a set to be summed up is empty 109 LHS RHS contradiction constraint trivially violated The lower side of your range is bigger than the upper side e g 15 lt x lt 2 110 Division by zero You tried to divide by zero This is not a good idea 111 Modulo by zero You tried to compute a number modulo zero This does not work well 23 ZIMPL 112 Exponent value xxx is too big or not an integer It is only allowed to raise a number to the power of integers Also trying to raise a number to the power of more than two billion is prohibited 113 Factorial value xxx is too big or not an integer You can only compute the factorial of integers Also computing the factorial of a number bigger then two billion is generally a bad idea See also Error 115 114 Negative factorial value To compute the factorial of a number it has to be positive In case you need it for a negative number remember that for all even numbers the outcome will be positive and for all odd number negative 115 Timeout You tried to compute a number bigger than 1000 See also the footnote to Error 112 116 Illegal value type in min xxx only numbers are possible You tried to build the minimum of some strings 117 Illegal value type in max xxx only numbers are possible You tried to build the maximum of some strings 118 Comparison of different types You tried to compare apples with oranges i e numbers with st
14. emoved If the split is due to a comma semicolon or double colon each occurrence of these characters starts a new field Examples All these lines have three fields Hallo 12 3 Moin 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 an 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 skipped and not counted 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 M nchen gt lt M nchen gt Berlin gt lt Berlin gt set Q read blabla txt as lt 1s 5n 2n gt skip 1 use 2 blabla txt 14 ZIMPL Name Nr X Y No gt skip Hamburg 12 x y 7 gt lt Hamburg 7 12 gt Bremen 4 x y 5 gt lt Bremen 5 4 gt Berlin 2 x y 8 gt skip param cost P read cost txt as lt ls gt 2n comment cost txt Name Price gt skip Hamburg 1000
15. es showing that it is able to cope with large scale models and also with students This would have not been possible without my early adopters Armin Fiigenschuh Marc Pfetsch Sascha Lukac Daniel Junglas and Tobias Achter berg Thanks for there comments and bug reports ZIMPL is licensed under the GNU general public license version 2 For more infor mation on free software see http www gnu org The latest version of ZIMPL can be found at http www zib de koch zimp1 If you find any bugs please send an email tolmailto koch zib de But do not forget to include an example that shows the problem If somebody extends ZIMPL I am interested in getting patches to include them in the main distribution ZIMPL 2 Introduction A linear program LP might look like this min 22 3y subjectto x y lt 6 L Y gt 0 The usual format to store the description of such a problem is MPS invented by IBM 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 NAME exl mps ROWS N OBJECTIV E cl COLUMNS x OBJECTIV 2 x cl 1 y OBJECTIV 3 y cl RHS RHS El 6 ENDATA Another possibility is the LP format ILOO2 which is more readabld but is only supported by a few solvers Minimize COSTE 2 X 43 y Subject to cl 1 x 1 y lt 6 End But since each coefficient of the
16. f in doubt use parenthesis Numeric expressions A number in ZIMPL can be given in the usual format e g as 2 6 5 or 5 234e 12 Numeric expressions consist of numbers numeric valued parameters and any of the following operators and functions ab a b a to the powerofb a atb addition a b a b subtraction a b a b multiplication a b a b division a b a mod b modulo a mod b a div b integer division abs a absolute value la floor a round down la ceil a round up a a factorial a min S minimum of a set minses max S maximum of a set MaXses min a b c n minimum of alist min a b c n max a b c n maximum of a list max a b c n card S cardinality of a set S if a then b else c conditional The following functions are only computed with normal double precision floating point arithmetic So be careful ZIMPL sqrt a square root Ja log a logarithm to base 10 log a ln a natural logarithm Ina exp a exponential function e String expressions A string is delimited by double quotation marks e g Hallo The following is either a numeric or a string expression depending if expression is a string or a numeric expression if boolean expression then expression el se expression end At this time no further functions or operators for strings are implemented Boolean expressions These evaluate either to true or false For numbers and strings the relational operators um
17. g The index expression for the minimization was empty The result used for this expression was zero 187 Maximizing over empty set zero assumed warning The index expression for the maximization was empty The result used for this expression was zero 29 ZIMPL 700 log OS specific domain or range error message Function log was called with a zero or negative argument or the argument was too small to be represented as a double 701 sqrtQ OS specific domain error message Function sqrt was called with a negative argument 702 In OS specific domain or range error message Function 1n was called with a zero or negative argument or the argument was too small to be represented as a double 800 parse error expecting xxx or yyy Parsing error What was found was not what was expected The statement you entered is not valid 801 Parser failed The parsing routine failed This should not happen If you encounter this error please email the zp1 file tomailto koch zib de 900 Check failed A check instruction did not evaluate to true 30 ZIMPL References Chv83 Va ek Chv tal Linear Programming H W Freeman and Company New York 1983 FGK03 R Fourier D M Gray and B W Kernighan AMPL A Modelling Language for Mathematical Programming Brooks Cole Thomson Learning second edition 2003 GNU03 GNU multiple precision arithmetic library GMP version 4 1 2 2003 Code and documentation available at
18. gt lt Hamburg gt 1000 M nchen 1200 gt lt M nchen gt 1200 Berlin 1400 gt lt Berlin gt 1400 param cost Q read haha txt as lt 3s 1n 2n gt 4s haha txt liz ab conl gt lt ab 1 2 gt conil 2 3 bc con2 gt lt be 2 3 gt NeonLl 4 5 de con3 gt lt de 4 5 gt con1 As with table format input it is possible to add a list of tuples or parameter entries after a read statement Examples set A read test txt as lt 2n gt lt 5 gt lt 6 gt param winniepoh X read values txt as lt 1n 2n gt 3n lt 1 2 gt 17 lt 3 4 gt 29 4 10 Function Definitions It is possible to define functions within ZIMPL The value a function returns has to be either a number a string or a set The arguments of a function can only be numbers or strings but within the function definition it is possible to access all otherwise declared sets parameters and variables The definition of a function has to start with defnumb defstrg or defset depending on the return value Then follows the name of the function and a list of argument names put in parenthesis After this comes an assignment operator and a valid expression or set expres sion Examples defnumb dist a b a a b b defstrg huehott a if a lt 0 then hue else hott end 15 ZIMPL defset bigger i lt j gt in K with j gt i 4 11 Extended Constraints experimental ZIMPL has the possibility
19. ined vabs t Absolute value t Be aware that using this construct will lead to the generation of several additional constraints and variables 16 ZIMPL Examples var x i integer gt 5 lt 5 subto cl vabs x 1 gt 5 subto c2 vabs sum lt i gt in I x i lt 15 subto c2 vif vabs x 1 x 2 gt 2 then x 3 7 end 4 13 Thedo print and do check commands The do command is special It has two possible incarnations print and check print will print to the standard output stream whatever numerical string Boolean or set expression or tuple follows it This can be used for example to check if a set has the expected members or if some computation has the anticipated result check always precedes a Boolean expression If this expression does not evalu ated to true the program is aborted with an appropriate error message This can be used to assert that specific conditions are met It is possible to use a forall clause before a print oder check statement Examples set I 1 10 do print I do forall lt i gt in I with i gt 5 do print sqrt i do forall lt p gt in P do check sum lt p i gt in PI 1 gt 1 17 ZIMPL 5 Examples In this section we will show examples how to translate a problem into ZIMPL format 5 1 Diet problem This is the first example in Chapter 1 page 3 It is a classic so called diet problem Given a set of foods F and a set of
20. ing 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 It is possible to declare a default value Parameters are declared in the following way The keyword param is followed by the name of the parameter 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 10 ZIMPL Examples set A 12 30 set C lt 1 2 x gt lt 6 5 y gt param q 5 param u A lt 1 gt 17 lt 2 gt 29 lt 3 gt 12 default 99 param w C lt 1 2 x gt 1 2 lt 6 5 y gt 2 3 param x lt i gt in 1 8 with i mod 2 0 3 i 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 Parameter tables It is possible to initialize multi dimensional indexed parameters from tables This is especially useful for two dimensional parameters The data is put in a table structure with signs on each margin Then a head line with column indices has to be added and one index for each row of the table is needed The column index has to be one dimensional but the row index can be multi dimensional The complete index for the entry
21. inity must have appeared This makes no sense and is therefore ignored 137 Upper bound for var xxx set to infinity ignored warning In the ZIMPL code something like lt infinity must have appeared This makes no sense and is therefore ignored 138 Priority Startval for continuous var xxx ignored warning There has been set a priority or a starting value for a continuous real variable This is not possible and therefore ignored 139 Lower bound for integral var xxx truncated to yyy warning An integral variable can only have an integral bound So the given non integral bound was adjusted 140 Upper bound for integral var xxx truncated to yyy warning An integral variable can only have an integral bound So the given non integral bound was adjusted 141 Infeasible due to conflicting bounds for var xxx The upper bound given for a variable was smaller than the lower bound 142 Unknown index xxx for symbol yyy The index tuple given is not member of the index set of the symbol 143 Size for subsets xxx is too big or not an integer The cardinality for the subsets to generate must be given as an integer smaller than two billion 144 Tried to build subsets of empty set The set given to build the subsets of was the empty set 145 Illegal size for subsets xxx should be between 1 and yyy The cardinality for the subsets to generate must be between and the cardinality of the base set 146 Tried to build powerset of empty set
22. ion of the Traveling Salesmen Problem as given for example in Section 58 5 The data is read in from a file that gives the number of the city and the x and y coordinate Distances between cities are geometric A suitable data file would look like this City Sylt Flensburg Neum nster Husum Schleswig Ausacker Y N wWH MN Wh XK BWwWWN HH The formulation in ZIMPL follows below Please note that P holds all subsets of the cities So don t try to solve a52 city TSP this way It won t work set V read tsp dat as lt 1s gt comment set E lt i j gt inV V with i lt j set P powerset V set K indexset P param px V read tsp dat as lt ls gt 2n comment param py V read tsp dat as lt ls gt 3n comment defnumb dist a b sqrt px a px b 2 pyla l py b 72 var x E binary minimize cost sum lt i j gt in E dist i j x i Jl subto two_connected forall lt v gt in V do sum lt v j gt in E x v j sum lt i v gt in E x i v 2 subto no_subtour forall lt k gt in K with card P k gt 2 and card P k lt card V 2 do sum lt i j gt in E with lt i gt in P k and lt j gt in P k x i j lt card P k 1 19 ZIMPL 5 3 Capacitated Facility Location Problem Here we have a formulation for the Capacitated Facility Location Problem Of course this is also kind of a bin packing proble
23. m with packing costs and variable sized bins or a cutting stock problem with cutting costs Given a set of possible plants P to built and a set of stores S with a certain demand s that has to be satisfied we have to decide which plant should serve which store We have costs c for building plant p and c for transporting the goods from plant p to store s Each plant has only a limited capacity p And we insist that each store is served by exactly one plant Of course we are looking for the cheapest solution gt a ze Cp Cps subject to 5 we 1 Ye 6 peP Tps E amp Weider 7 N bau lt Hp WEP 8 ses Due E 10 17 9 We have binary variables z which are set to one iff plant p is to be build And we have binary variables x which are set to one iff plant p serves shop s Equation 6 demands that each store is assigned to exactly one plant Equation 7 makes sure that a plant that serves a shop is built And Equation 8 restricts the shops that are served by a plant to the plants capacity Putting this into ZIMPL yields set PLANTS A B C D set STORES 1 9 set PS PLANTS STORES How much does it cost to build a plant and what capacity will it then have param building PLANTS lt A gt 500 lt B gt 600 lt C gt 700 lt D gt 800 param capacity PLANTS lt A gt 40 lt B gt 55 lt C gt 73 lt D gt 90 Here is the demand of each store param demand S
24. ne 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 x1 4 4 x2 sum 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 4 6 Constraints The general format for a constraint is subto name term sense term Name can be any name starting with a letter The term is defined as in the objective Sense is one of lt gt and Many constraints can be generated with one statement by the use of the foral 1 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 12 ZIMPL sum lt a b c gt in C zla b c 55 subto c21 6 sum lt i gt in A x i sum lt j gt in B y j gt 2 subto c40 x 1 all 2 sum lt i gt in A do 2 a i x 1 3 4 4 7 Details on sum and forall The general forms are forall index do term and sum index do term It is possible to nest several forall instructions 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 members of the set must match The with part of an index is optional The set can be any expre
25. nutrients N we have a table 7 p of the amount of nutrient n in food f Now Il defines how much intake of each nutriment is needed And Ay describes the maximum number of servings of each food Now given prices cf for each food we have to find a selection of foods that obeys the restrictions and has minimal cost j nTn bject t 1 o Tr subject to 1 Drum gt In meN 2 fer Den E Ar WEeRneN 3 Lin N 4 As implies only complete servings can be obtained Half an egg is not an option Now translating this to ZIMPL looks as follows set Food Oatmeal Chicken Eggs Milk Pie Pork set Nutrients Energy Protein Calcium set Attr Nutrients Servings Price param needed Nutrients lt Energy gt 2000 lt Protein gt 55 lt Calcium gt 800 param data Food Attr Servings Energy Protein Calcium Price Oatmeal 4 110 4 Lory 3 Chicken 3 205 SA 12 24 Eggs De ij 160 I3 54 13 Milk 8 160 8 284 9 Pre 2 420 4 22 20 Pork 25 260 14 80 19 My kcal g mg cents var x lt f gt in Food integer gt 0 lt datalf Servings minimize cost sum lt f gt in Food datalf Price x subto need forall lt n gt in Nutrients do sum lt f gt in Food data f n x f gt needed n 18 ZIMPL 5 2 TSP In this example we show how to generate an exponential descript
26. rings Note that the use of an undefined parameter could also lead to this message 119 Union of incompatible sets To unite two sets both must have the same dimension tuples i e the tuples must have the same number of components 120 Minus of incompatible sets To subtract two sets both must have the same dimension tuples 121 Intersection of incompatible sets To intersect two sets both must have the same dimension tuples 122 Symmetric Difference of incompatible sets Two build the symmetric difference of two sets both must have the same dimen sion tuples 123 from value xxx in range too big or not an integer To generate a set the from number must be an integer with an absolute value of less than two billion gt The behavior of this operation could easily be implemented as for or more elaborate as void 24 ZIMPL 124 upto value xxx in range too big or not an integer To generate a set the upto number must be an integer with an absolute value of less than two billion 125 step value xxx in range too big or not an integer To generate a set the step number must be an integer with an absolute value of less than two billion 126 Zero step value in range The given step value for the generation of a set is zero So the upto value can never be reached 127 Illegal value type in tuple xxx only numbers are possible The selection tuple in a call to the p
27. rmat with extension 1p or mps The next one is the table file which has the extension tbl This file lists all variable and constraint names used in the model and their corresponding names in the problem file The reason for this name translation is that the MPS format can only handle names up to eight characters long Also the the LP format restricts the length of names to 16 characters The third file is and optional CPLEX branching order file The following options are possible only the first two are normally of interest ZIMPL t format Selects the output format Can be either 1p which is default or mps or hum which is only human readable o name Sets the base name for the output files Defaults to the name of the first input file stripped off its path and extension F filter The output is piped through a filter A s in the string is re placed by the output filename For example p gzip c gt s gz would compress all the output files n cform Select the format for the generation of constraint names Can be either cm which will number them 1 with a c in front cn will use the name supplied in the subto statement and number them 1 n within the statement cf will use the name given with the subto then a 1 n number like in cm and then append all the local variables from the forall statements y 1 5 Set the verbosity level O is quiet 1 is default 2 is verbose 3 is chatter and 5 is debug D name
28. roj function can only contain numbers 128 Index value xxx in proj too big or not an integer The value given in a selection tuple of a proj function is not an integer or bigger than two billion 129 Illegal index xxx set has only dimension yyy The index value given in a selection tuple is bigger than the dimension of the tuples in the set 130 Duplicate index xxx for initialization In the initialization of a indexed set two initialization elements have the same index E g set A lt 1 gt 1 lt 1 gt 2 131 Illegal element xxx for symbol The index tuple used in the initialization list of a index set is not member of the index set of the set E g set A 1 to 5 lt 1 gt 1 lt 6 gt 2 132 Values in parameter list missing probably wrong read template Probably the template of a read statement looks like lt 1n gt only having a tuple instead of lt 1n gt 2n 133 Unknown local symbol xxx A local symbol was used that is not defined anywhere in scope 134 Illegal element xxx for symbol The index tuple given in the initialization is not member of the index set of the parameter 135 Index set for parameter xxx is empty The attempt was made to declare an indexed parameter with the empty set as index set Most likely the index set has a with clause which has rejected all elements 25 ZIMPL 136 Lower bound for var xxx set to infinity ignored warning In the ZIMPL code something like gt inf
29. ssion 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 i 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 Note that in the example i and j are set by the forall instruction So they are fixed for all invocations of sum 4 8 Details on if in constraints It is possible to put two variants of a constraint into an i f statement The same applies for terms It is also possible to have a forall statement inside the result part of an Tr Examples subto cl forall lt i gt in I do if i mod 2 0 then 3 x i gt else 2 y i lt 3 end subto c2 sum lt i gt in IT if i mod 2 0 then 3 x i else 2 y i end lt 3 13 ZIMPL 4 9 Initializing sets and parameters from a file It is possible to load the values for a set or a parameter from a file The syntax is read filename as template skip n use n fs 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 into 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 always removed When a field is split all space and tab characters around the splitting are r
30. uld be read out of the data file Either the file is empty or all lines are comments 159 Type error expected xxx got yyy The type found was not the expected one e g subtracting a string from a number would result in this message 160 Comparison of elements with different types xxx yyy warning Two elements from different tuples were compared and found to be of different types Probably you have an index expression with a constant element that does not match the elements of the set Example set B lt i a gt in lt 1 2 gt 161 Line xxx Unterminated string This line has an odd number of characters A String was started but not ended 27 ZIMPL 162 Line xxx Trailing yyy ignored warning Something was found after the last semicolon in the file 163 Line xxx Syntax Error A new statement was not started with one of the keywords set param var minimize maximize subto or do 164 Duplicate element xxx for set rejected warning An element was added to a set that was already in it 165 Comparison of different dimension sets warning Two sets were compared but have different dimension tuples This means they never had a chance to be equal other then being empty sets 166 Duplicate element xxx for symbol yyy rejected warning An element that was already there was added to a symbol 167 Comparison of different dimension tuples warning Two tuples with different dimensions were compared Probably you ha
31. val Sets the parameter name to the specified value This is equiv alent with having this line in the ZIMPL program param name val b Enables bison debugging output f Enables flex debugging output h Prints a help message O Optimize the generated LP by doing some presolve analysis r Writes a CPLEX ord branching order file A typical invocation is for example zimpl o hardone t mps data zpl model zpl This reads the files data zpl and model zp1 and produces hardone mps and hardone tbl If MPS output is specified for a maximization problem the objective function will be inverted 4 Format Each ZPL file consists of six types of statements Sets Parameters Variables Objective ZIMPL Constraints Function definitions Each statement ends with a semicolon Everything from a number sign to the 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 then this file is read instead of the line 4 1 Expressions ZIMPL works on its lowest level with two types of data Strings and numbers Wherever a number or string is required it is also possible to use a parameter of the corresponding value type Usually expressions are allowed instead of just a number or a string The precedence of operators should be the usual one but parenthesis can always be used to specify the evaluation order explicitly I
32. ve an index expression which does not match the dimension of the tuples in the set Example set B lt 1 gt in lt 1 2 gt 168 No program statements to execute No ZIMPL statements were found in the files loaded 169 Execute must return void element This should not happen If you encounter this error please email the zp1 file tomailto koch zib de 170 Use of uninitialized local variable xxx in call of define yyy A define was called and one of the arguments was a name of a variable for which no value was defined 171 Wrong number of arguments xxx instead of yyy for call of define z zz A define was called with a different number of arguments than in its definition 172 Wrong number of entries xxx in table line expected yyy entries Each line of a parameter initialization table must have exactly the same number of entries as the index first line of the table 173 Illegal type in element xxx for symbol A parameter can only have a single value type Either numbers or strings In the initialization both types were present 174 Numeric field xxx read as yyy This is not a number It was tried to read a field with an n designation in the template but what was read is not a valid number 28 ZIMPL 175 Illegal syntax for command line define xxx ignored warning A parameter definition using the command line D flag must have the form name value The name must be a legal identifier i e it has to start
33. with a letter and may consist only out of letters and numbers including the underscore 176 Empty LHS in Boolean constraint warning The left hand side i e the term with the variables is empty 177 Boolean constraint not all integer No continuous real variables are allowed in a Boolean constraint 178 Conditional always true or false due to bounds warning All or part of a Boolean constraint are always either true or false due to the bounds of variables 179 Conditional only possible on bounded constraints A Boolean constraint has at least one variable without finite bounds 180 Conditional constraint always true due to bounds warning The result part of a conditional constraint is always true anyway This is due to the bounds of the variables involved 181 Empty LHS not allowed in conditional constraint The result part of a conditional constraint may not be empty 182 Empty LHS in variable vabs There are no variables in the argument to a vabs function Either everything is zero Or just use abs 183 vabs term not all integer There are non integer variables in the argument to a vabs function Due to numerical reasons continuous variables are not allowed as arguments to vabs 184 vabs term not bounded The term inside a vabs has at least one unbounded variable 185 Term in Boolean constraint not bounded The term inside a vif has at least one unbounded variable 186 Minimizing over empty set zero assumed warnin
Download Pdf Manuals
Related Search