Solving MINLP Problems with AIMMS Software Developer Marcel Hunting
"Learn how AIMMS software developer Marcel Hunting solves MINLP problems using AIMMS, an integrated modeling system with advanced deployment options and extensive development tools. Explore the AIMMS Modeling Structure, Generated Math Program, and more features for efficient problem-solving."
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Solving MINLP problems with AIMMS Pittsburgh June 4, 2014 Marcel Hunting AIMMS Software Developer www.aimms.com
Overview Introducing AIMMS Generated Math Program (GMP) Outer Approximation AIMMS Presolver Implement Branch-and-Bound www.aimms.com
AIMMS Modeling Structure AIMMS, integrated & interactive modeling system Modeling language, integrated GUI, direct access to solvers, advanced deployment options, and extensive development tools www.aimms.com
AIMMS Modeling Structure AIMMS, integrated & interactive modeling system Modeling language, integrated GUI, direct access to solvers, advanced deployment options, and extensive development tools www.aimms.com
Model generation Columns: c0 c48 c49 c118 c119 Variables: JobSchedule(j,s) StartTime(s,m) TimeSpan Solve Rows: r0 r6 r7 r13 r14 r76 r77 r136 Constraints: OneJobPerSchedule(s) OneSchedulePerJob(j) MachineStartTime(s,m) ScheduleStartTime(s,m) www.aimms.com
Generated Math Program (GMP) Symbolic MP Generated MP Matrix symbolic variables generated columns generated rows generated matrix coefficients symbolic constraints mappings from/to variables and constraints Solution Repository 1 solution status level values [basis information] 2 solution status level values [basis information] . . . Pool of Solver Sessions 2 solver option settings 1 solver option settings . . . www.aimms.com
Basic GMP Normally: solve MathProgram; GMP: myGMP := GMP::Instance::Generate(MathProgram); GMP::Instance::Solve(myGMP); Modify: GMP::Column::SetUpperBound(myGMP,StartTime(s1,m1),5); www.aimms.com
Selection of GMP functions GMP::Instance:: Generate, Solve, Copy, FixColumns, CreateFeasibilityProblem, CreatePresolved GMP::Column:: Add, Delete, Freeze, SetLowerBound GMP::Row:: Add, Delete, SetRightHandSide GMP::Coefficient:: Set, Get, SetQuadratic, GetQuadratic GMP::Solution:: Copy, SendToModel, GetColumnValue GMP::Linearization:: Add, Delete GMP::SolverSession:: Execute, AsynchronousExecute www.aimms.com
Outer Approximation module Module: GMPOuterApproximation Call: myGMP := GMP::Instance::Generate( myMathProgram ) ; GMPOuterApprox::DoOuterApproximation( myGMP ); Uses AIMMS presolver by default Can be combined with Multi-start module Quesada & Grossmann (1992) version for convex MINLP Uses lazy constraints callback Uses nested solve www.aimms.com
Results AOA - COA Problem AOA COA Problem AOA COA BatchS151208M 17 6 o7 4494 629 BatchS201210M 41 6 o7_ar4_1 2923 643 CLay0205H 17 5 RSyn0840M04H 7 8 CLay0305H 31 8 RSyn0840M04M 33 15 FLay04H 33 2 SLay08H 63 5 FLay05H > 3hr 172 SLay09M 48 5 fo7_2 54 11 SLay10H > 3hr 505 fo9 1161 5183 Syn40M04H 2 2 netmod_dol2 388 63 trimloss4 356 17 netmod_kar1 142 5 Water0303 13 5 no7_ar3_1 142 265 Water0303R 22 12 www.aimms.com
Results COA: 1 versus 4 Threads Problem 1 thr 4 thr Problem 1 thr 4 thr CLay0305H 8 3 o7_ar4_1 643 432 FLay05H 172 62 RSyn0840M04H 8 8 fo7_2 11 5 RSyn0840M04M 15 7 fo9 5183 937 SLay09H 17 24 netmod_dol2 63 22 SLay10H 505 191 no7_ar3_1 265 33 trimloss4 17 13 o7 629 323 Water0303R 12 13 www.aimms.com
AIMMS Presolver Delete redundant constraints & fixed variables Bound Tightening - Feasibility based Variable x: range [0,inf) - range [10,55] Linear & nonlinear constraints Improve coefficients (possibly using probing) Linearize quadratic constraints www.aimms.com
Linearize quadratic constraints Constraint (? binary, ? and ? continuous or integer) ????= ? ? ???? with ? ???? ? ? ? Linearization: ???? ?? , ???? ????+ ? ? 1 ? ? ? ???? ?? , ???? ????+ ? ? 1 ? ? ? www.aimms.com
Branch-and-Bound MINLP problem with binary variables x(i) and y(i,j). Implement branching; choose most fractional column. gmpBB: Generated Math Program for a node in B&B tree www.aimms.com
Branching for (i) do xLev(i) := GMP::Column::GetColumnValue( gmpBB, 1, x(i) ); xHalfGap(i) := abs( xLev(i) - 0.5 ); endfor; xMostFractionalColumn := ArgMin( i, xHalfGap(i) ); for (i,j) do yLev(i,j) := GMP::Column::GetColumnValue( gmpBB, 1, y(i,j) ); yHalfGap(i,j) := abs( yLev(i,j) - 0.5 ); endfor; yMostFractionalColumn := ArgMin( (i,j), yHalfGap(i,j) ); MostFractionalColumn := www.aimms.com
Branching - Improved Vars := { x , y }; ColNrs := GMP::Instance::GetColumnNumbers( gmpBB, Vars ); For example: ColNrs = {3,4, ,10,20,21, ,43} index: c for (c) do Lev(c) := GMP::Column::GetColumnValue( gmpBB, 1, c ); HalfGap(c) := abs( Lev(c) - 0.5 ); endfor; MostFractionalColumn := ArgMin( c, HalfGap(c) ); www.aimms.com
Branching - Improved Vars := AllIntegerVariables; ColNrs := GMP::Instance::GetColumnNumbers( gmpBB, Vars ); For example: ColNrs = {3,4, ,10,20,21, ,43} index: c for (c) do Lev(c) := GMP::Column::GetColumnValue( gmpBB, 1, c ); HalfGap(c) := abs( Lev(c) - 0.5 ); endfor; MostFractionalColumn := ArgMin( c, HalfGap(c) ); www.aimms.com
