AMPL in the Cloud Using Online Services to Develop and Deploy Optimization Applications through Algebraic Modeling Robert Fourer AMPL Optimization Inc. [email protected] INFORMS Conference on Business Analytics and Operations Research Las Vegas, April 2-4, 2017 Technology Tutorials — Monday, 2:10-3:00 pm Robert Fourer, AMPL in the Cloud 1 INFORMS Analytics, 2-4 April 2017 The Optimization Modeling Cycle Steps  Communicate with problem owner  Build model  Prepare data  Generate optimization problem  Submit problem to solver  Gurobi, Knitro, CPLEX, Xpress, CONOPT, MINOS, . . .  Report & analyze results  Repeat until you get it right! Goals for optimization software  Do this quickly and reliably  Get results before client loses interest  Deploy for application Robert Fourer, AMPL in the Cloud 4 INFORMS Analytics, 2-4 April 2017 Optimization Modeling Languages Two forms of an optimization problem  Modeler’s form  Mathematical description, easy for people to work with  Solver’s form  Explicit data structure, easy for solvers to compute with Idea of a modeling language  A computer-readable modeler’s form  You write optimization problems in a modeling language  Computers translate to algorithm’s form for solution Advantages of a modeling language  Faster modeling cycles  More reliable modeling  More maintainable applications Robert Fourer, AMPL in the Cloud 5 INFORMS Analytics, 2-4 April 2017 Algebraic Modeling Languages Formulation concept  Define data in terms of sets & parameters  Analogous to database keys & records  Define decision variables  Minimize or maximize a function of decision variables  Subject to equations or inequalities that constrain the values of the variables Advantages  Familiar  Powerful  Proven Robert Fourer, AMPL in the Cloud 6 INFORMS Analytics, 2-4 April 2017 Features  Algebraic modeling language  Built specially for optimization  Designed to support many solvers Design goals  Powerful, general expressions  Natural, easy-to-learn modeling principles  Efficient processing that scales well with problem size 3 ways to use . . . Robert Fourer, AMPL in the Cloud 8 INFORMS Analytics, 2-4 April 2017 3 Ways to Use AMPL Command language  Browse results & debug model interactively  Make changes and re-run Scripting language  Bring the programmer to the modeling language Programming interface (API)  Bring the modeling language to the programmer Robert Fourer, AMPL in the Cloud 9 INFORMS Analytics, 2-4 April 2017 Example: Roll Cutting Motivation  Fill orders for rolls of various widths  by cutting raw rolls of one (large) fixed width  using a variety of cutting patterns Optimization model  Decision variables  number of raw rolls to cut according to each pattern  Objective  minimize number of raw rolls used  Constraints  meet demands for each ordered width Robert Fourer, AMPL in the Cloud 10 INFORMS Analytics, 2-4 April 2017 Roll cutting Mathematical Formulation Given (cid:1849) set of ordered widths (cid:1866) number of patterns considered and (cid:1853) occurrences of width (cid:1861) in pattern (cid:1862), (cid:3036)(cid:3037) for each (cid:1861) ∈ (cid:1849) and (cid:1862) (cid:3404) 1, . . . , (cid:1866) (cid:1854) orders for width (cid:1861), for each (cid:1861) ∈ (cid:1849) (cid:3036) Robert Fourer, AMPL in the Cloud 11 INFORMS Analytics, 2-4 April 2017 Roll cutting Mathematical Formulation (cont’d) Determine (cid:1850) number of rolls to cut using pattern (cid:1862), (cid:1862) for each (cid:1862) (cid:3404) 1, . . . , (cid:1866) to minimize (cid:3041) ∑ (cid:1850) (cid:3037)(cid:2880)(cid:2869) (cid:3037) total number of rolls cut subject to (cid:3041) ∑ (cid:1853) (cid:1850) (cid:3410) (cid:1854) , for all (cid:1861) ∈ (cid:1849) (cid:3037)(cid:2880)(cid:2869) (cid:3036)(cid:3037) (cid:3037) (cid:3036) number of rolls of width (cid:1861) cut must be at least the number ordered Robert Fourer, AMPL in the Cloud 12 INFORMS Analytics, 2-4 April 2017 Roll Cutting AMPL Formulation Symbolic model set WIDTHS; param orders {WIDTHS} > 0; param nPAT integer >= 0; param nbr {WIDTHS,1..nPAT} integer >= 0; var Cut {1..nPAT} integer >= 0; minimize Number: sum {j in 1..nPAT} Cut[j]; subj to Fulfill {i in WIDTHS}: sum {j in 1..nPAT} nbr[i,j] * Cut[j] >= orders[i]; (cid:3041) ∑ (cid:1853) (cid:1850) (cid:3410) (cid:1854) (cid:3037)(cid:2880)(cid:2869) (cid:3036)(cid:3037) (cid:3037) (cid:3036) Robert Fourer, AMPL in the Cloud 13 INFORMS Analytics, 2-4 April 2017