Optimisation and Operations Research

1 Optimisation and Operations ResearchLecture 14: ILPs in Matlab and AMPLM atthew of Mathematical Sciences,University of AdelaideJuly 12, 2017 Section 1 Integer Programming: MatlabMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20172 / 26 MatlabbintprogSimilar to thelinprogcommand in Matlab for linear programs that havevariables which can take on real solutions, there exists a commandbintprog1for those linear programs that are also constrained to havevariables to bebinary, ,which can only take on the values 0 or is, bintprog solves binary linear programming problems of the formminxfTx,such that Ax bAeqx=beqx {0,1}n, ,a binary vectorwhere,f,b, andbeqare vectors,AandAeqare matrices, and the solutionxis required to be a binary integer functionbintprogis being replaced in future versions ofMatlab, withintlinprogbut using binary programming is instructive for a starting Roughan (School of Mathematical Sciences, University of Adelaide)

2 OORIIJuly 12, 20173 / 26 MATLAB bintprogexampleCommands:> f = [-9; -5; -6; -4];> A = [6,3,5,2; 0,0,1,1; -1,0,1,0; 0,-1,0,1];> b = [9; 1; 0; 0];> x = bintprog(f,A,b)Output:x = 1100 Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20174 / 26 Integer binary conversionWhat about whenxis not binary, but integer, can we the number 9, represented using the binary (or base-2) numbersystem and variablesx1,x2,x3,x4, which can only take the values 0 or = 1 20+ 0 21+ 0 22+ 1 23=x1 20+x2 21+x3 22+x4 23where(x1,x2,x3,x4) = (1,0,0,1)In fact, any number from 0 up to 15 can be represented in a similar wayusing the four variablesx1,x2,x3,x4, byx=x1 20+x2 21+x3 22+x4 23,where the variablesx1,x2,x3andx4can only take the values 0 or Roughan (School of Mathematical Sciences, University of Adelaide)

3 OORIIJuly 12, 20175 / 26 Matlabbintprogwas Matlab, R2013, but has since been replacedIwanted to show you integer to binary conversionThese days look upintlinprogIit s very much likeintprogIwill solve ILP directlyIcan specify which variables are integerMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20176 / 26 Section 2 AMPLM atthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20177 / 26 Practical OptimisationMatlab is all very well, but what do real optimisers do?Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20178 / 26 Mathematical Modelling LanguagesThere are computer languages designed specifically for optimisationIthey allow natural expression of LPs, link to multiplebackendsto solve the problemIthey separate themodelfrom thedataIthey link to other tools, ,databases, spreadsheets.

4 Isupport reuseCommon examples:IAMPLIGAMSIAIMMSIMPS (not really a modelling language, but is used for standard input) Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 20179 / 26 AMPL = A Mathematical Programming LanguageWhy AMPL?II like itIit s one of the most commonly used (Neos says 59%)Ilots of backendsIfree student versionHistoryIdesigned 1985 by Robert Fourer, David Gay and Brian KernighanI2003 AMPL Optimization LLCI2012 INFORMS Impact PrizeMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201710 / 26 ResourcesTheAMPL Book, AMPL: A Modelling Language for MathematicalProgramming , , and ~atamturk/ieor264/samples/ ~dano/courses/4600/lectures/6 your own (student) copy of AMPL are other backends (we are using lpsolve, but I notice they don thave a direct link to this anymore).

5 Online solver Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201711 / 26 ExampleExampleLPmaxz= 3x1+2x2subject to2x1+x2 5 x1+4x2 3xi 0 AMPL x{i in } >= 0;maximize z: 3*x[1] + 2*x[2];subject to c1: 2*x[1]+1*x[2]<=5;subject to c2: -x[1]+4*x[2]<=3;Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201712 / 26 ExampleStartampland then typeExample# commands to run in AMPL ampl:reset; # get rid of old ; # choose our modelampl: option solver lpsolve; # set the backendampl:solve;ampl:displayx; # output the resultsYou could just type these commands at the AMPL promptCould also run them from a scriptRemember the Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201713 / 26 Programming StyleMixesImperative:Isequences of commands to executeIfocus onhowto perform the taskDeclarative:Idescribe the problem, not how to solve itIfocus onwhatthe task should achieveInterpreted:Iexecuted in source code formIcan interact with interpreter (like Matlab)Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201714 / 26 ModelsVariablesvar x{i in } >= 0;Ior could have named variables, ,amountofpaintIand we can havesets, and other constructsObjectivemaximize z: 3*x[1] + 2*x[2].

6 Iwe can put a wide range of mathematical expressions hereConstraintssubject to c1: 2*x[1]+1*x[2]<=5;subject to c2: -x[1]+4*x[2]<=3;Iwe can put a wide range of mathematical expressions hereIconstraints have names, ,c1, which could use laterMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201715 / 26 Another ExampleIndex values can be from an arbitrary setCoefficients and variables can be specified as vectors or matricesExample1setpossibilities := { A , B , C };23parama{possibilities};4paramb;5param c{possibilities};67varx{possibilities} integer;89maximizeprofit: sum{i in possibilities} c[i]*x[i];1011subject tolimit1: sum{i in possibilities} a[i]*x[i] <= b;12subject tolimit2{i in possibilities}: 0<= x[i] <= 1;Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201716 / 26 Data and Model SeparationWhy separate data and model?

7 Imodel might actually be very small when you remove repeated bitsFxi 0 for alliImodel might be static, but data ,prices changeIdata might be in another ,spreadsheet or databaseIconceptually easier to understandWhat is separationImodel shows mathematical structureIdata fills in the coefficients, which are calledparametersWe use notation much like standard mathematical notationMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201717 / 26 Example: modelExample (Example model file)1## Introduction to AMPL - A Tutorial, by Kaminsky and Rajan2## Example 23paramn;4paramt;5paramp{i in };6paramr{i in };7paramm{i in };89varpaint{i in } >= 0 integer;1011maximizeprofit: sum{i in } p[i]*paint[i];1213subject totime: sum{i in } (1/r[i])*paint[i] <= t;14subject tocapacity{i in }: 0 <= paint[i] <= m[i];Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201718 / 26 Example: dataExample (Example data file)1## Introduction to AMPL - A Tutorial, by Kaminsky and Rajan2## Example 23paramn:= 2;4paramt:= 40;56paramp:= 1 1072 15;8paramr:= 1 4092 30;10paramm:= 1 1000112 860;Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201719 / 26 ExampleExample (Example commands)# commands to run in AMPL ampl:reset; # get rid of old ; # choose our ; # specify dataampl: option solver lpsolve; # set the backendampl:solve;ampl:displaypaint.

8 # output the resultsNote we input the model before the data, and we reset first, to clear anyold definitions that might Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201720 / 26 Data and Model SeparationNote thatnis set in the dataIwe can change the number of types of paint easilyThe coefficients of the constraints, and the objective are set in thedataIwe can change these as the market changesIwe could choose more meaningful names for everythingThe expression of all the constraints is done very conciselyImakes it easier to get it right (less typos)Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201721 / 26 Data and Model SeparationModelDataAMPL interpreterfilesSolverback endsolutionMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201722 / 26 Advanced AMPLWe can go way beyond thisIall sorts of constraintsIall sorts of objectiveIgeneral sets of objectsI2D arrays of parametersIdata from filesSolvers (backends)IlpsolveICPLEXIMINOSIG urobiEach can handle different size problems, and different types ofconstraints ( ,MINOS can t do Integer problems).

9 Matthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201723 / 26 Where to next?We will use AMPL in some practical questionsIyou ll get some more helpIyou might need to read some of the other available resources to fill ingapsII may have some more examples in lecturesYou can use it to solve some assignment questions or in your projectIbut read questions carefully some expect you to use it, and other asknotIand make sure you understand the resultsThere will be a question in the ExamMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201724 / 26 TakeawaysMatlab has a solver for ILPsIit s useful when we want an integrated environment to create, solve,and visualise our problemAMPL (or another modelling language) is the way most industrialmathematiciansshouldapproach big problemsIit s naturalImultiple backendsIseparation of data and model is very valuableWe re going to spend some time now to understand how these mightworkMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201725 / 26 Further reading IMatthew Roughan (School of Mathematical Sciences, University of Adelaide)OORIIJuly 12, 201726 / 26