BARON user manual v. 15.6.5
Contents
1. N V Sahinidis Global optimization and constraint satisfaction The branch and reduce approach In AC Bliek C Jermann and A Neumaier eds Global Optimization and Constraint Satisfaction Lecture Notes in Computer Science Vol 2861 Springer Berlin pages 1 16 2003 S Ahmed M Tawarmalani and N V Sahinidis A finite branch and bound algorithm for two stage stochastic integer programs Mathematical Programming 100 355 377 2004 M Tawarmalani and N V Sahinidis Global optimization of mixed integer nonlinear programs A theoretical and computational study Mathematical Programming 99 563 591 2004 N V Sahinidis and M Tawarmalani Accelerating branch and bound through a modeling language construct for relaxation specific constraints Journal of Global Optimization 32 259 280 2005 M Tawarmalani and N V Sahinidis A polyhedral branch and cut approach to global optimization Mathematical Programming 103 225 249 2005 N V Sahinidis BARON A general purpose global optimization software package Journal of Global Optimization 8 201 205 1996 Y Chang and N V Sahinidis Global optimization in stabilizing controller design Journal of Global Optimization 38 509 526 2007 X Bao N V Sahinidis and M Tawarmalani Multiterm polyhedral relaxations for non convex quadratically constrained quadratic programs Optimization Methods and Soft ware 24 485 504 2009 L M Rios and N V Sahinidis Portfol2. IsolTol can take any positive value greater than or equal to le 12 7 2 Relaxation options Option NOutert NOutPerVar N0utlter DutGrid Description Number of outer approximators of convex univariate func tions NOuter1 must be a nonnegative integer Number of outer approximators per variable for convex multivariate functions NOutPerVar must be a nonnega tive integer Number of rounds of cutting plane generation at node re laxation NOutIter must be a nonnegative integer Number of grid points per variable for convex multivariate approximators of BARON s CONVEX_EQUATIONS OutGrid must be a nonnegative integer 7 3 Range reduction options Option TDo MDo LBTTDo OBTTDo PDo Description Nonlinear feasibility based range reduction option poor man s NLPs O no bounds tightening is performed 1 bounds tightening is performed Marginals based reduction option 0 no range reduction based on marginals 1 range reduction done based on marginals Linear feasibility based range reduction option poor man s LPs O no range reduction based on feasibility 1 range reduction done based on feasibility Optimality based tightening option O no range reduction based on optimality 1 range reduction done based on optimality Number of probing problems allowed aoe automatically decided by BARON 0 no range reduction by probing i probing on all variables n probing on n variables le 4 Defaul
3. unknown If model status is 4 or 5 this entry denotes the number of missing bounds from vari ables expressions that make BARON unable to guarantee global optimality e The number of branch and bound iterations taken The node where the best solution was found nodeopt e The maximum number of nodes stored in memory The total CPU time in seconds If nodeopt 3 there will be no solution in the results file Otherwise the solution can be found in the results file by starting from the end of the file searching backward for and then reading the solution forward one variable at a time The variables are ordered in the way they were defined in the VARIABLES section of the BARON file If available the dual solution is also provided there In addition the best primal solution is provided using variable names If the solution process is interrupted for instance by Ctrl C the primal solution will be present in the results file but not necessarily the corresponding dual If BARON declares the problem as unbounded it will report its best solution found possibly followed by a vertex and direction of an unbounded ray at the end of the results file In the case of numsol gt 1 BARON returns the best numsol solutions found These solutions follow right after the mentioned above and they are sorted in improving order the last solution is the best Duals may not be returned for all these solutions For those solutions for
4. Boston MA pages 205 230 2001 H S Ryoo and N V Sahinidis Analysis of bounds for multilinear functions Journal of Global Optimization 19 403 424 2001 M Tawarmalani and N V Sahinidis Semidefinite relaxations of fractional programs via novel techniques for constructing convex envelopes of nonlinear functions Journal of Global Optimization 20 137 158 2001 M Tawarmalani and N V Sahinidis Convex extensions and convex envelopes of l s c functions Mathematical Programming 93 247 263 2002 M Tawarmalani and N V Sahinidis Convezification and Global Optimization in Con tinuous and Mixed Integer Nonlinear Programming Theory Algorithms Software and Applications Kluwer Academic Publishers Dordrecht 2002 M Tawarmalani S Ahmed and N V Sahinidis Global optimization of 0 1 hyperbolic programs Journal of Global Optimization 24 385 417 2002 M Tawarmalani S Ahmed and N V Sahinidis Product disaggregation and relaxations of mixed integer rational programs Optimization and Engineering 3 281 303 2002 BARON user manual v 15 6 5 29 19 20 Zi 22 23 24 25 26 27 28 29 30 31 32 33 N V Sahinidis M Tawarmalani and M Yu Design of alternative refrigerants via global optimization AIChE Journal 49 1761 1775 2003 H S Ryoo and N V Sahinidis Global optimization of multiplicative programs Journal of Global Optimization 26 387 418 2003
5. Y8T1T3 Y9L283 YioL1 Y11L2 Y12 4 V13 0 Y1aLoXg YisL1 Vise 0 1721 Y18L2 Vig 0 r ee 1 0 r 2 1 0 2 2 xg 25 1 0 r a22 1 0 mL tS Ll 0 where y 0 004731 ye 1 Yu 0 07745 Vie 0 004731 Yq 0 3578 v7 0 3571 12 0 6734 17 0 7623 y3 0 1238 Ya 0 2238 13 0 6022 Vig 0 2238 y4 001637 Yo 0 7638 ia 1 Vig 0 3461 y5 0 9338 10 0 2638 15 0 3578 The first four equations of this problem are bilinear while the last four are generalized cylinders BARON s scheme for finding all feasible solutions works well in continuous spaces as long as the 16 BARON user manual v 15 6 5 solutions are isolated separated by a certain distance The BARON option isoltol default value of 10 allows the user to specify the isolation tolerance to be used to discriminate among different solutions In order for two feasible solution vectors to be considered different at least one of their coordinates must differ by isoltol The BARON file for the robot problem is as follows Filename robot bar Purpose Find all solutions of the PUMA robot problem L W Tsai and A P Morgan Solving the kinematics of the most general six and five degree of freedom manipulators by continuation methods ASME J Mech Transm Automa Des 107 189 200 1985 OPTIONS numsol 20 VARIABLES x1 x2 x3 x4 x5 x6 x7 x8 LOWER_BOUNDS i 1 x22
6. and driven shafts The objective of the gear train design is to find the number of teeth of the four gears and to obtain a required gear ratio of 1 6 931 The problem originated from Deb K and Goyal M Optimizing Engineering Designs Using a Combined Genetic Search In Back T Ed Proceedings of the Seventh International Conference on Genetic Algorithms 1997 pp 521 528 INTEGER_VARIABLES i1 12 13 14 number of teeth in each of the gears LOWER_BOUNDS it 12 i2 12 13 12 i4 12 UPPER_BOUNDS il 60 i2 60 i3 60 i4 60 EQUATIONS e2 e3 symmetry constraints e2 i3 i4 gt 0 e3 il i2 gt 0 BARON user manual v 15 6 5 9 the objective aimms to make the reciprocal of the gear ratio as close to 6 931 as possible an ideal design will have an objective equal to 1 OBJ minimize 6 931 i1 i2 i3 i4 2 1 STARTING_POINT il 24 i2 24 i3 24 i4 24 Additional examples can be found at http www minlp com download 4 7 Other ways to access BARON For information on how to access BARON under MATLAB see the BARON MATLAB interface manual at http www minlp com downloads matbar matbar zip For information on how to access BARON under AIMMS AMPL GAMS or YALMIP consult the corresponding web sites of these modeling systems 5 BARON output 5 1 BARON screen output The screen output below is obtained for the MINLP model gear b
7. core reformulations of the optimization problem e The number of variables in one of BARON s core reformulations of the optimization prob lem e BARON s lower bound for the global optimum of the problem e BARON s upper bound for the global optimum of the problem e BARON s solver status which can take one of the following values 1 Zi PU ON OU Te eo go 10 11 12 If normal completion occurred i e the problem was solved within tolerances If there is insufficient memory to store the number of nodes required for this search tree increase physical memory or change algorithmic options If the maximum allowed number of iterations was exceeded increase maxiter If the maximum allowed time was exceeded increase maxtime If the problem is numerically sensitive If the run was interrupted by user Ctrl C If there was insufficient memory to setup BARON s data structures increase physical memory This return code is reserved for development purposes If the run was terminated by BARON If the run was terminated by BARON s parser because of a syntax error in the BARON input file If the run was terminated because of a licensing error If the heuristic termination rule was invoked by the user e BARON s model status which can take one of the following values i optimal within tolerances 14 BARON user manual v 15 6 5 2 infeasible 3 unbounded 4 intermediate feasible 5
8. course of the algorithm Parts of the BARON software were created at the University of Illinois at Urbana Champaign and Carnegie Mellon University 1 1 Licensing and software requirements The demo version of BARON is freely available from The Optimization Firm and can be down loaded from http ww minlp com download This code can handle problems with up to 10 variables 10 constraints and 50 nonlinear operations In order to use BARON for larger prob lems users will need to have a valid BARON license The Optimization Firm provides licenses that permit users to use BARON directly on any Windows or Linux platform as well as under MATLAB and YALMIP In addition BARON distributors AIMMS AMPL and GAMS provide licenses for using BARON under their modeling systems BARON user manual v 15 6 5 3 The software includes the Coin solvers CLP CBC FilterSD and IPOPT for solving BARON s linear integer programming LP MIP and nonlinear programming NLP subproblems In ad dition BARON can utilize IBM s ILOG CPLEX for solving LP MIP subproblems if CPLEX is installed on the user s computer as a dynamic library Additional licensed LP MIP and NLP solvers are available under the AIMMS AMPL and GAMS versions of BARON and may expe dite convergence Current valid LP MIP subsolvers for BARON are CLP CBC CPLEX and XPRESS Current valid NLP subsolvers are CONOPT FilterSD IPOPT MINOS and SNOPT 2 Model requirements BARON addresses the prob
9. in ascending order of degree 3 arrange constraints in descending order of degree gt 4 random order using IISorder as seed Specifies the number of cores that BARON is allowed to use for solution of its MIP subproblems By de fault this option has the value of 1 meaning that a single core will be utilized The value of this option is passed to CBC CPLEX and XPRESS through the op tions CPX_PARAM_THREADS XPRS_THREADS and threads respectively 8 Bibliography 27 The following is a partial list of BARON related publications that describe the algorithms im plemented in the software the theory behind them and some related applications 1 H S Ryoo and N V Sahinidis Global optimization of nonconvex NLPs and MINLPs with applications in process design Computers amp Chemical Engineering 19 551 566 1995 2 M C Dorneich and N V Sahinidis Global optimization algorithms for chip layout and compaction Engineering Optimization 25 131 154 1995 3 H S Ryoo and N V Sahinidis Journal of Global Optimization 8 107 139 1996 A branch and reduce approach to global optimization 4 N V Sahinidis BARON A general purpose global optimization software package Journal of Global Optimization 8 201 205 1996 28 10 11 12 13 14 15 16 17 18 BARON user manual v 15 6 5 R A Gutierrez and N V Sahinidis A branch and bound approach for machine selection in just in time m
10. must be read from three output files e The results file provides the results Each solution found by BARON is reported in this file as soon as it is found Variable values and dual values for variables and constraints are printed in the order in which variables and constraints are defined in the BARON file At the end of this file a termination message such as Normal Completion is printed followed by the best solution point in two different formats the last of which makes use of the variable names used in the BARON file e The summary file contains the information that goes to the screen In addition it provides information on missing bounds if any BARON user manual v 15 6 5 13 e The time file contains a single line with concise information on the solution including a breakdown of iterations and times the same information is available at the bottom of the summary file as well As detailed in Section 7 the user has full control on whether any of these files will be written or not In addition the user can specify the names and or paths of these output files The time file should be read first after BARON s termination in order to obtain information regarding termination status This file contains a single line with the following information e ProName e The number of constraints of the optimization problem e The number of variables of the optimization problem e The number of constraints in one of BARON s
11. point This point is found to be feasi ble with an objective function value of 36 176761 BARON subsequently performs a randomized local search procedure which in this case does not improve the incumbent Execution then proceeds with branch and bound with information printed every 1 000 000 branch and bound iterations and every 30 seconds Additionally information is printed at the end of the root node whenever the value of the incumbent is improved by at least 1075 and at the end of the search During branch and bound search a star in the first position of a line indicates that a better feasible solution was found that improves the value of previous best known solution by at least 1075 The log fields include the iteration number number of open branch and bound nodes the time taken thus far the lower bound and the upper bound for the problem The log output fields are summarized below BARON user manual v 15 6 5 11 Field Description Iteration The number of the current iteration A plus following the iteration num ber denotes reporting while solving a probing as opposed to a relaxation subproblem of the corresponding node Open Nodes Number of open nodes in branch and reduce tree Time Current computational time in seconds CPU time is reported for single threaded jobs and wall clock time is reported for multi threaded jobs Lower Bound Current lower bound on the model Upper Bound Current upper bound on the model On
12. the MIP subproblems For this purpose the option threads may be used to specify the number of cores that BARON s MIP subsolver is allowed to use By default this option has the value of 1 meaning that a single core will be utilized 7 The BARON options The BARON options allow the user to control termination tolerances branching and relaxation strategies heuristic local search options and output options as detailed in this section Contrary to variable names the BARON parser is not case sensitive to option names 7 1 Termination options 20 Option EpsA ea EpsR e DeltaTerm DeltaT 0 DeltaA 0 DeltaR 6 CutOff AbsConFeasTol BARON user manual v 15 6 5 Description Absolute termination tolerance BARON terminates if U El lt ca where U and L are the values of the in cumbent and best estimate respectively for the optimiza tion problem at the current iteration EpsA must be a real greater than or equal to 1e 12 Relative termination tolerance BARON terminates if U L lt e L where U and L are the values of the incumbent and best estimate respectively for the opti mization problem at the current iteration EpsR must be a nonnegative real Users have the option to request BARON to terminate if insufficient progress is made over 6 consecutive seconds Progress is measured using the absolute and relative im provement thresholds 6 and 6 defined below Termi nation will occ
13. time The BARON option is MaxTime e Problem is numerically sensitive BARON is designed to automatically handle problems with numerical difficulties However for certain problems the global optimum is numerically sensitive This occurs for instance when the objective function value varies significantly over small neighborhoods of points that are strictly outside the feasible region but are nonetheless feasible within numerical tolerances When BARON returns this message the Best possible reported on the objective is likely correct e Search interrupted by user The run was interrupted by the user Ctrl C e x x Insufficient Memory for Data structures More memory is needed to set up the problem data structures The user will need to increase the physical memory available on the computer in order to accommodate problems of this size e x A potentially catastrophic access violation just took place In the unlikely event of an access violation BARON will terminate the search and return the best known solution Please report problems that lead to this termination condition to Nick Sahinidis niksah minlp com 5 3 BARON solution output When BARON is used under AIMMS AMPL GAMS MATLAB or YALMIP the corresponding BARON interface brings BARON results into these modeling environments these users can skip this section For those users who choose to use BARON outside of these modeling systems BARON s solution
14. which a corresponding dual was found the dual is also printed right after the primal There will typically be a dual solution for the best solution found and all local minima However there will be no dual for non KKT points something that is highly likely to happen in most applications When numsol 1 find all feasible solutions the solutions are reported in the results file as soon as they are found These solutions are reported before the and can be read from this file by searching for occurrences of found reading the solution reported immediately thereafter and repeating this process until all occurrences of found are identified Again many of these solutions will be reported without corresponding duals At the end of the file i e following Succ the best solution can be read along with a corresponding dual 6 Some BARON features The features described in this section rely on options that are further detailed in the next section For details of the algorithmic implementations the user may wish to consult publications cited at the end of this document BARON user manual v 15 6 5 15 6 1 No starting point is required In contrast to many NLP algorithms that require a feasible starting point a starting point is not required for BARON A user may optionally provide a starting point for all or even some of the problem variables BARON will judiciously initialize any variables that are not ini
15. BARON s NumLoc option which determines the number of local searches to be done by BARON s preprocessor BARON can be forced to terminate after preprocessing by setting the number of iterations to 0 through the MaxIter op tion In addition to local search BARON s preprocessor performs extensive reduction of variable 18 BARON user manual v 15 6 5 ranges To sample the search space for local minima without range reduction one would have to set to 0 the range reduction options TDo MDo LBTTDo and OBTTDo On the other hand leaving these options to their default values increases the likelihood of finding high quality local optima during preprocessing If NumLoc is set to 1 local searches in preprocessing will be done from randomly generated starting points until global optimality is proved or MaxTime seconds have elapsed 6 4 Systematic treatment of unbounded problems If BARON declares a problem as unbounded it will search for and may report a vertex and direction of an unbounded ray In addition BARON will report the best solution found This will be a feasible point that is as far as possible along an unbounded ray while avoiding numerical errors due to floating point arithmetic 6 5 Systematic treatment of infeasible problems If BARON declares a problem as infeasible it has the capability to identify a subset of the constraints that are infeasible and become feasible once any one of them is eliminated This so called irreduci
16. BARON user manual v 15 6 5 June 5 2015 Nick Sahinidis The Optimization Firm LLC niksah minlp com http www minlp com Contents 1 Tatroduection o sacs a tecen e A ew Sas 2 Li Licensing and software requirements e 2 2 Model requirements 3 2 1 Allowable nonlinear functions e 3 oS Variable and expression bounds o o e e 3 3 Installation 2 5 06 S22 oa a a A BARON apt soc cum rrd sd o a e a 4 4 1 e ES AN 4 4 2 a AA ee EOD RES 4 4 3 Theyptions SECON e A eena ok a A ATE a ap do 5 4 4 The problem data ooos cres eee a a a 6 4 5 Error messages 8 4 6 Sample LBS ada a ras a a we a 8 Ay Other ways to access BARON 9 5 BARON output scc sst sg a ee a A aS RS 9 5 1 BARON screen output o aoe os oea a aci a m ee 9 5 2 Termination messages model and solver statuses 11 5 8 BARON solution output c secas eresse ce rergp detr iaa 12 6 Some BARON features 2 0 0 2 eee eee 14 6 1 No starting point is required 0 0 eee ee ee es 15 6 2 Finding a few of the best or all feasible solutions 15 6 3 Using BARON as a multi start heuristic solver 17 6 4 Systematic treatment of unbounded problems 18 6 5 Systematic treatment of infeasible problems 18 6 6 Handling of complementarity constraints 0 19 6 7 Par
17. RON s DeltaTerm option e xxx User did not provide appropriate variable bounds x The user will need to read the BARON summary file for pointers to variables and expressions with missing bounds The model should be modified in order to provide bounds for variables and intermediate expressions that make it possible for BARON to construct reliable relaxations Even though relaxation bounds are printed on the screen to give the user a feeling for convergence these bounds may not be valid for the problem at hand This message is followed by one of the following two messages 12 BARON user manual v 15 6 5 e x Infeasibility is therefore not guaranteed This indicates that be cause of missing bounds no feasible solution was found but model infeasibility was not proven e xxx Globality is therefore not guaranteed This indicates that because of missing bounds a feasible solution was found but global optimality was not proven e Max allowable nodes in memory reached The user will need to increase the physical memory of the computer or change algorithmic options such as branching and node selection rules to reduce the size of the search tree and memory required for storage e xxx Max allowable BaR iterations reached The user will need to increase the maximum number of allowable iterations The BARON option is MaxIter e xxx Max allowable time exceeded The user will need to increase the maximum of allowable
18. allel capabilities 2 50242 sasaa ee Re ee ee Re ee 19 2 BARON user manual v 15 6 5 7 The BARON options lt lt s saca a 4 22604 Hee ew bee ds es 19 Tel Termination options ace soor Re ee ee ee a 19 pee Beliociigam ORO eus osae d ea A oh we ee we a a 22 7 3 Range reduction options oa se lt lt eos essa aiai 22 7 4 Tree management options e 23 T5 Local gear PLE o o se mied a A Ra ee ee a a i 23 7 6 Output oplions so e eae aa a eis Ge a o a ee ee 23 7 7 Subs lyer OPTIONS air a w ecean he ee ee 24 7 8 DCE WRI a occ 3 Aly E AE OO ee ee Pe 26 7 9 Other GPhone caco A A a 26 8 Bibliograbhy 2 22 Seed eee ee ia ee 27 1 Introduction The Branch And Reduce Optimization Navigator BARON is a computational system for the global solution of algebraic nonlinear programs NLPs and mixed integer nonlinear programs MINLPs While traditional NLP and MINLP algorithms are guaranteed to provide global optima only under certain convexity assumptions BARON implements deterministic global optimization al gorithms of the branch and bound type that are guaranteed to provide global optima under fairly general assumptions These assumptions include the existence of finite lower and upper bounds on nonlinear expressions in the NLP or MINLP to be solved BARON implements algorithms of the branch and bound type enhanced with a variety of con straint propagation and duality techniques for reducing ranges of variables in the
19. anufacturing systems International Journal of Production Research 34 797 818 1996 M L Liu N V Sahinidis and J P Shectman Planning of chemical process networks via global concave minimization In I E Grossmann ed Global Optimization in Engineering Design Kluwer Academic Publishers Boston MA pages 195 230 1996 V Ghildyal Design and Development of a Global Optimization System Master s thesis Department of Mechanical amp Industrial Engineering University of Illinois Urbana IL 1997 J G VanAntwerp R D Braatz and N V Sahinidis Globally optimal robust control for systems with nonlinear time varying perturbations Computers amp Chemical Engineering 21 5125 S130 1997 J P Shectman and N V Sahinidis A finite algorithm for global minimization of separable concave programs Journal of Global Optimization 12 1 36 1998 J G VanAntwerp R D Braatz and N V Sahinidis Globally optimal robust control J Process Control 9 375 383 1999 N V Sahinidis and M Tawarmalani Applications of global optimization to process and molecular design Computers amp Chemical Engineering 24 2157 2169 2000 V Ghildyal and N V Sahinidis Solving global optimization problems with BARON In A Migdalas P Pardalos and P Varbrand eds From Local to Global Optimization A Workshop on the Occasion of the 70th Birthday of Professor Hoang Tuy Link ping Sweden Aug 24 29 1997 Kluwer Academic Publishers
20. ar BARON version 15 6 5 Built LNX 64 Fri Jun 5 09 12 41 EDT 2015 If you use this software please cite Tawarmalani M and N V Sahinidis A polyhedral branch and cut approach to global optimization Mathematical Programming 103 2 225 249 2005 BARON is a product of The Optimization Firm LLC http www minlp com Parts of the BARON software were created at the University of Illinois at Urbana Champaign No BARON license file found in user PATH Continuing in demo mode Model size is allowable within BARON demo size This BARON run may utilize the following subsolver s For LP MIP ILOG CPLEX 10 BARON user manual v 15 6 5 For NLP COIN IPOPT with MUMPS and METIS FILTERSD Starting solution is feasible with a value of 36 1767610000 Doing local search Solving bounding LP Starting multi start local search Done with local search Iteration Open nodes Time s Lower bound Upper bound 1 1 0 02 1 00000 36 1768 1 1 0 02 1 00000 35 1952 1 1 0 02 1 00000 4 72876 1 1 0 02 1 00000 3 29321 1 1 0 02 1 00000 3 29321 2 0 02 1 00000 1 06987 3 1 0 02 1 00000 1 02321 6 3 0 03 1 00000 1 01273 17 0 0 04 1 00000 1 00006 17 0 0 04 1 00000 1 00006 Cleaning up Normal completion Wall clock time 0 04 Total CPU time used 0 04 Total no of BaR iterations 17 Best solution found at node 17 Max no of nodes in memory 11 All done The solver first tests feasibility of the user supplied starting
21. as soon as NumSol feasible solutions are found Maximum number of branch and reduce iterations al lowed 1 implies unlimited Setting MaxIter to 0 will force BARON to terminate after root node preprocessing Setting MaxIter to 1 will result in termination after the solution of the root node MaxIter must be an integer greater than or equal to 1 Maximum time allowed sec For single threaded jobs i e when threads equals 1 this limit is enforced on CPU time consumed by the job For multi threaded jobs the MaxTime limit is enforced on wall clock time Setting MaxTime to 1 will make BARON ignore the time limit MaxTime must be a real equal to 1 or greater than 0 Number of feasible solutions to be found Solutions found will be listed in the results file As long as NumSol 4 1 these solutions will be sorted from best to worse If NumSol is set to 1 BARON will search for all feasible solutions to the given model and print them in the order in which they are found in the results file NumSol must be an integer greater than or equal to 1 le 5 le 8 1000 21 22 IsolTol BARON user manual v 15 6 5 Separation distance between solutions This option is used in conjunction with NumSol For combinatorial optimiza tion problems feasible solutions are isolated For contin uous problems feasible solution points within an l dis tance that does not exceed IsolTol gt 0 will be treated as identical by BARON
22. bly inconsistent system IIS can be obtained by BARON for all types of prob lems handled by BARON including linear and nonlinear continuous and integer convex and nonconvex and problems with complementarity constraints BARON s CompIIS option can be used to identify an IIS As an example consider the problem of minimizing the nonconvex function x2 x73 over the fol lowing nonconvex constrained set el 85 0 006225 0 000622 0 00273x15 lt 92 e2 0 82225 0 003222 0 00223 110 e3 9 0 0052r3x75 0 0012x1273 0 002 37 4 lt 25 78 lt x lt 102 33 lt 12 lt 45 ESO T da When this problem is solved with CompIIS equal to 1 BARON provides the following result IIS contains 1 row and 3 columns as follows e2 Upper xi Lower x2 Lower x5 Lower The IIS consists of the lower bounds of variables x1 12 and z5 along with the lt part of the equality constraint e2 This suggests that constraint e2 and the entire model can be made feasible by lowering the lower bound of any of the three variables that are part of the IIS whereas modifying the bounds of 23 would not make the model feasible BARON user manual v 15 6 5 19 If a problem is known to be infeasible and the user desires to identify an IIS it may be beneficial to set BARON s NumLoc option to zero Doing so will deactivate BARON s initial upper bounding search which involves multiple local searches On the other hand DoLocal should be nonzero in ord
23. ce the branch and reduce tree is searched the best solution is isolated and a corresponding dual solution is calculated Then the total number of branch and reduce iterations number of search tree nodes is reported followed by the node where the best solution was identified a 1 indicates preprocessing as explained in the next section on termination messages 5 2 Termination messages model and solver statuses Upon normal termination BARON will report the node where the optimal solution was found We refer to this node as nodeopt The log message is of the form Best solution found at node nodeopt where nodeopt can take the following values 3 no feasible solution found 2 the best solution found was the user supplied 1 the best solution was found during preprocessing i the best solution was found in the ith node of the tree nodeopt In addition to reporting nodeopt upon termination BARON will issue one of the following statements e xxx Normal completion This is the most desirable termination status The problem has been solved within tolerances in this case If BARON returns a code of 3 then no feasible solution exists e xxx Heuristic termination While global optimality is not guaranteed in this case BARON will terminate with this message when a a feasible solution has been found and b the progress of lower upper bounds satisfies the heuristic termination criterion set by the user through BA
24. cy in number of seconds 23 Default 0 Default 1 Default 1000000 30 24 PrLevel LocRes ProName results ResName summary SumName times TimName BARON user manual v 15 6 5 Option to control log output 0 all log output is suppressed 1 print log output Option to control output to log from local search O no local search output d detailed results from local search will be printed to the results file Problem name This option must be provided in double quotes and be no longer than 10 characters Indicator if a results file is to be created 0 do not create file 1 create file named according to the ResName op tion Name of results file to be written This option must be provided in double quotes in the bar file Indicator if a summary file is to be created O do not create file 1 create file named according to the SumName op tion Name of summary file to be written This option must be provided in double quotes in the bar file Indicator if a times file is to be created O do not create file 1 create file named according to the TimName op tion Name of times file to be written This option must be provided in double quotes in the bar file 7 7 Subsolver options Option LPSol Description Specifies the LP MIP solver to be used 3 CPLEX 8 CLP CBC problem 1 res lst sum lst tim lst Default BARON user manual v 15 6 5 CplexLibName LPAl
25. e be baron Then issuing the command baron test or baron test bar results in BARON parsing the file and solving the problem 4 2 Input grammar The following rules should be adhered to while preparing a BARON input file e All statements should be terminated by a semicolon e Reserved words must appear in uppercase letters BARON user manual v 15 6 5 5 Variable names can be in lower or upper case The parser is case sensitive i e X1 and x1 are two different variables Variable names should be no longer than 15 characters Variable names must start with a letter With the exception of underscores _ non alphanumeric characters such as hyphens are not permitted in variable names Any text between and the end of a line is ignored i e it is treated as a comment The signs and have their usual meaning of arithmetic operations 66499 is the power exponentiation operator where if the base is a negative constant the exponent must be an integer Note that the order of operations may be different in different computing environments y z xy zin GAMS MATLAB and Excel ay 2 x y z in Fortran AMPL BARON Mathematica The exponential function is denoted as exp The natural logarithm is available as log as well as In To enter log in the model use the transformation log x logyp e x log x 0 4342944819032518 x log x BARON does not allow
26. er to permit local search during the solution of certain subproblems that BARON solves while searching for an IIS 6 6 Handling of complementarity constraints Complementarity relationships of the type f x g x 0 are automatically recognized and ex ploited algorithmically by BARON The functions f and g may be univariate or multivariate linear or nonlinear convex or nonconvex in terms of continuous and or integer variables and may be subject to additional constraints in the model These complementarity relationships can be inferred by BARON even when implied by problem constraints and variable bounds As a result BARON can solve general mathematical programs with equilibrium constraints MPECs This class of problems includes the classical linear complementarity problem LCP Find z gt 0 and q such that Mz q gt 0 and 2 Mz q 0 as well as the more general mixed complementarity problem MCP Given a function f R gt R and bounds l u R with R RU 00 00 find z R and w v R such that Ha w wl lt z lt u z lw 0 u z v 0 Both problems are automatically recognized and exploited by BARON without the user having to mark complementarities in any special way 6 7 Parallel capabilities For difficult problems with integer variables most of BARON s time is spent on solving MIP relaxations Hence considerable speedups may be obtained via parallel solution of
27. g NLPSol AllowFilterSD If utilized this option must be supplied in double quotes and provide the entire path to the location of the CPLEX callable libraries on the user s computer If left unspecified and LPSol is 3 BARON will utilize standard library loca tion facilities to locate CPLEX and use it for the solution of LP NLP subproblems In the latter case the CPLEX libraries should be in the user s LIBRARY PATH When searching for the libraries on Windows systems BARON will look for cplex dll whereas on Linux systems it will look for libcplex so on MAC OSX it will look for libc plex dylib If a CPLEX library named CplexLibName is not found BARON will search for a library containing the version number currently cplex1261 dll libcplex1261 so or libcplex1261 dylib depending on the platform If CPLEX is still not found BARON will resort to using CLP CBC instead The CplexLibName option is not ap plicable to BARON under AIMMS AMPL or GAMS As an alternative to the CplexLibName option users may copy the CPLEX libraries or use symbolic links to place the default library name on their user LIBRARY PATH Specifies the LP algorithm to be used 0 automatic selection of LP algorithm 1 primal simplex 2 dual simplex 3 barrier Specifies the NLP solver to be used By default BARON will select the NLP solver and may switch between dif ferent NLP solvers during the search based on problem characteristics and solver perfo
28. io optimization for wealth dependent risk prefer ences Annals of Operations Research 177 63 90 2010 X Bao N V Sahinidis and M Tawarmalani Semidefinite relaxations for quadratically constrained quadratic programming A review and comparisons Mathematical Program ming 129 129 157 2011 A Khajavirad and N V Sahinidis Convex envelopes of products of convex and component wise concave functions Journal of Global Optimization 52 391 409 2012 A Khajavirad and N V Sahinidis Convex envelopes generated from finitely many com pact convex sets Mathematical Programming 137 371 408 2013 K Zorn and N V Sahinidis Global optimization of general nonconvex problems with intermediate bilinear substructures Optimization Methods and Software 29 442 462 2013 30 34 35 36 37 BARON user manual v 15 6 5 K Zorn and N V Sahinidis Computational experience with applications of bilinear cutting planes Industrial amp Engineering Chemistry Research 52 7514 7525 2013 A Khajavirad J J Michalek and N V Sahinidis Relaxations of factorable functions with convex transformable intermediates Mathematical Programming 144 107 140 2014 K Zorn and N V Sahinidis Global optimization of general nonconvex problems with inter mediate polynomial substructures Journal of Global Optimization DOI 10 1007 s10898 014 0190 2 2014 X Bao A Khajavirad N V Sahinidis and M Tawarmalani Global optim
29. ization of non convex problems with multilinear intermediates Mathematical Programming Computation DOI 10 1007 s12532 014 0073 z 2015
30. lem of finding global solutions to general nonlinear and mixed integer nonlinear programs min f z st qa lt 0 TEX where f X gt R g X gt R and X CIR The set X may include integer restrictions and the constraints may include complementarity relationships The types of functions f and g currently handled by BARON are discussed below 2 1 Allowable nonlinear functions In addition to multiplication and division BARON can handle nonlinear functions that in volve exp x ln x x for real a and 8 for real 8 AIMMS BARON AMPL BARON and GAMS BARON automatically handle x and x where x and y are variables otherwise suitable transformations discussed below can be used Currently there is no support for other functions including the trigonometric functions sin x cos x etc 2 2 Variable and expression bounds Nonlinear expressions in the mathematical program to be solved must be bounded below and or above It is important that finite lower and upper bounds be provided by the user on as many problem variables as possible However providing finite bounds on variables alone may not suffice to guarantee finite bounds on nonlinear expressions arising in the model For example consider the term 1 x for x 0 1 which has finite variable bounds but is unbounded It is important to provide bounds for problem variables that guarantee that the problem functions are finitely valued in the domain of interest If the use
31. ng this option equal to 1 works very well for most problems O f 2 do not search for an IIS the search for an IIS is based on a fast heuristic an IIS is obtained using a deletion filtering algo rithm an IIS is obtained using an addition filtering al gorithm an IIS is obtained using an addition deletion fil tering algorithm an IIS is obtained using a depth first search al gorithm Default baronlice txt Default 0 BARON user manual v 15 6 5 IISint IISorder threads When search for an IIS is requested through CompIIS BARON assumes that the model is unlikely to include an error in terms of binaries i e the binary definitions are assumed correct and the IIS output should be interpreted with respect to binary definitions General integer bounds may be assumed as correct or can be questioned using the option IISint which can take the values of 0 default where integer bounds are assumed correct and the IIS should be interpreted with respect to integer bounds or 1 signalling that general integer bounds should be ques tioned Integrality is enforced in both cases 0 do not consider general integers as part of an IIS i consider general integers but not binaries as part of an IIS Defines the order in which problem constraints are consid ered in the search for an IIS lu auto set to aim for a small IIS depending on the value of CompIIS be arrange constraints in problem order 2 arrange constraints
32. r model does not include variable bounds that guarantee that all nonlinear expressions are finitely valued BARON will attempt to infer appropriate bounds from problem constraints If this step fails global optimality of the solutions provided may not be guaranteed 4 BARON user manual v 15 6 5 3 Installation If you intend to use BARON under GAMS AIMMS AMPL or YALMIP the BARON software already comes installed with your modeling system If you intend to access the stand alone version of BARON entirely on its own or via MATLAB place the BARON executable and license in your PATH Simply placing them under your MATLAB PATH may not suffice In order to use BARON under MATLAB follow the additional installation instructions that come with the MATLAB BARON interface 4 BARON input There are various ways for passing an optimization problem to BARON e Directly using the BARON modeling language e Indirectly using one of the available BARON interfaces under AIMMS AMPL GAMS MATLAB or YALMIP In this section we describe the BARON modeling language in detail 4 1 Usage BARON provides a high level modeling language capable of reading a mixed integer nonlinear optimization model in a relatively simple format Input is provided in the form of a text file Even though not required it is strongly recommended that all BARON input files have the extension bar Let the input file be called test bar and let the name of the BARON executabl
33. rmance Any combination of licensed NLP solvers may be used in that case A single specific NLP solver can be specified by setting this option to a value other than the default If the specified solver is not licensed BARON will default to automatic solver selection 1 automatic solver selection 0 Local search based on function evaluations alone with no calls to local solvers 9 IPOPT 10 FilterSD In case of automatic NLP solver selection this option can be used to selectively permit or disallow the use of Fil terSD as an NLP subsolver O do not use FilterSD for local search alk consider FilterSD for local search 25 libcplex so cplex dll libcplex dylib 26 AllowIpopt BARON user manual v 15 6 5 In case of automatic NLP solver selection this option can be used to selectively permit or disallow the use of IPOPT as an NLP subsolver O 1 do not use IPOPT for local search consider IPOPT for local search 7 8 Licensing options Option LicName 7 9 Other options Option CompIIS Description License file name If utilized this option must be supplied in double quotes and provide the entire path to the loca tion of the BARON license file If left unspecified BARON will search for the BARON license file baronlice txt in the user PATH This option is not applicable to BARON under AIMMS AMPL or GAMS Description In case of an infeasible problem this option can be used to search for an IIS Setti
34. t 4 4 20 Default BARON user manual v 15 6 5 7 4 Tree management options Option BrVarStra BrPtStra NodeSel Description Branching variable selection strategy O BARON s dynamic strategy 1 largest violation Jz longest edge Branching point selection strategy O BARON s dynamic strategy 1 w branching 2 bisection branching 3 convex combination of w and bisection Specifies the node selection rule to be used for exploring the search tree O BARON s strategy 1 best bound 2 LIFO 3 minimum infeasibilities 7 5 Local search options Option DoLocal NumLoc Description Local search option for upper bounding O no local search is done during upper bounding LE BARON automatically decides when to apply lo cal search based on analyzing the results of pre vious local searches Number of local searches done in preprocessing The first one begins with the user specified starting point Sub sequent local searches are done from judiciously chosen starting points If NumLoc is set to 1 local searches in preprocessing will be done until proof of globality or MaxTime is reached If NumLoc is set to 2 BARON de cides the number of local searches in preprocessing based on problem and NLP solver characteristics NumLoc must be an integer greater than or equal to 2 7 6 Output options Option PrFreq PrTimeFreq Description Log output frequency in number of nodes Log output frequen
35. ter than or equal to le 12 Default 1e 6 le 4 100 le 5 BARON user manual v 15 6 5 RelConFeasTol AbsIntFeasTol RelIntFeasTol BoxTol FirstFeas MaxIter MaxTime NumSol Relative constraint feasibility tolerance This tolerance is used for general constraints and variable bounds A point is considered feasible for a constrain bound if the abso lute or relative constraint feasibility tolerance is satisfied RelConFeasTol must be a real between 0 and 0 1 Absolute integer feasibility tolerance All integer variable values must satisfy this tolerance A point is considered integer feasible for a variable if integrality is satisfied us ing the absolute or relative integer feasibility tolerance AbsIntFeasTol must be a real greater than or equal to le 12 Relative integer feasibility tolerance All integer variable values must satisfy this tolerance A point is considered integer feasible for a variable if integrality is satisfied us ing the absolute or relative integer feasibility tolerance RelIntFeasTol must be a real between 0 and 0 1 Boxes will be eliminated if smaller than this tolerance BoxTol must be a real greater than or equal to 1e 12 If set to 1 BARON will terminate once it finds NumSol feasible solutions irrespective of solution quality By de fault FirstFeas is 0 meaning that BARON will search for the best NumSol feasible solutions O do not enforce this termination condition 1 terminate
36. tialized by the user Even when the problem functions cannot be evaluated at a user provided starting point BARON is still capable of carrying out its global search 6 2 Finding a few of the best or all feasible solutions BARON offers a facility through its NumSol option to find the best few or even all feasible solu tions to a model The development of this facility was motivated by combinatorial optimization problems but the facility is applicable to continuous problems as well Even for combinatorial problems BARON does not rely on integer cuts to find multiple solutions Instead it uti lizes a single search tree thus providing a computationally efficient method for finding multiple solutions Furthermore because BARON s approach applies to integer as well as continuous programs it can be used to find all feasible solutions to a system of nonlinear equality and inequality constraints Once a model is solved by BARON with the NumSol option the solutions found can be read from BARON results file To illustrate this feature we consider a problem in kinematic analysis of robot manipulators the so called indirect position or inverse kinematics problem in which the desired position and orientation of a robot hand is given and the relative robot joint displacements are to be found The specific example that we consider involves the following set of equations for the PUMA robot Y1T1 3 Y2L2L3 Y3gL1 Yale Y5La VeL7 Y7 O
37. uation definition is shown below el 5 x3 y2 3 x573 gt 1 e2 yl 2xx4 2 x7 25 7 e3 20 lt x4 2 y1 x3 x6 lt 50 Any variables must appear only on one side of the relational operator That is the left hand side and the right hand side should be pure numbers or expressions involving constants but no variables e Objective function BARON optimizes a given objective function This can be declared using the OBJ and the minimize or maximize keywords A sample objective definition is shown below OBJ minimize 7 x3 2 x6 e Starting point optional A starting point can be optionally specified using the keyword STARTING_POINT as follows STARTING_POINT x1 50 x4 100 x7 300 8 BARON user manual v 15 6 5 4 5 Error messages Any errors in the input file are reported in the form of warnings and errors BARON tries to continue execution despite warnings In case the warnings and or errors are severe the program execution is stopped and the line where the fatal error occurred is displayed The input file should be checked even if the warnings are not severe as the problem might have been parsed in a way other than it was intended to be 4 6 Sample input file A sample input file for BARON is shown below This is a gear train design problem taken from the GAMS test library A compound gear train is to be designed to achieve a specific gear ratio between the driver
38. ur if over a period of 6 consecutive sec onds the value of the best solution found by BARON is not improved by at least an absolute amount a or an amount equal to 6 times the value of the incumbent at time t This termination condition is enforced after processing the root node and only after a feasible solu tion has been obtained Because it relies on CPU time measurements which may depend on machine load this option may result in nondeterministic behavior O do not enforce this termination condition 1 terminate if progress is insufficient If DeltaTerm is set to 1 BARON will terminate if insuffi cient progress is made over 6 consecutive seconds If is set to a non positive quantity BARON will automatically set equal to 0 times the CPU time taken till the end of root node processing DeltaT can take any real value Absolute improvement termination threshold DeltaA must be a real greater than or equal to 1e 12 Relative improvement termination threshold DeltaR must be a real greater than or equal to 1e 12 BARON may ignore parts of the search space that contain solutions that are no better than this value CutOff can take any real value Absolute constraint feasibility tolerance This tolerance is used for general constraints and variable bounds A point is considered feasible for a constrain bound if the abso lute or relative constraint feasibility tolerance is satisfied AbsConFeasTol must be a real grea
39. wing parts Note that the words EQUATIONS ROWS and CONSTRAINTS are used interchangeably e Variable declaration All variables used in the problem have to be declared before they are used in equations Variables can be declared as binary integer positive or free using the keywords BINARY_VARIABLES INTEGER_VARIABLES POSITIVE_VARIABLES and VARIABLES respectively In these keywords VARIABLE or VAR may be used instead of VARIABLES and the underscore may be replaced by a space All discrete binary and integer variables should be declared before any continuous variables A sample declaration is as follows BINARY_VARIABLES y1 y2 0 1 variables INTEGER_VARIABLES x3 x7 discrete variables POSITIVE_VARIABLES x1 x4 x6 nonnegative variables VARIABLE x5 this is a free variable e Variable bounds optional Lower and upper bounds on previously declared variables can be declared using the keywords LOWER BOUNDS and UPPER BOUNDS respectively The word BOUND can be used instead of BOUNDS A sample bounds declaration follows LOWER_BOUNDS x7 10 x5 300 UPPER_BOUND x4 100 e Branching priorities optional Branching priorities can be provided using the keyword BRANCHING_PRIORITIES The default values of these parameters are set to 1 Variable vio lations are multiplied by the user provided priorities before a branching variable is selected A sample branching priorities section follows BRANCHING_PRIORITIEFS
40. x3 10 x5 0 The effect of this input is that variable x3 will be given higher priority than all others while variable x5 will never be branched upon BARON user manual v 15 6 5 7 e Equation declaration An identifier name corresponding to each equation constraint has to be declared first The keywords EQUATION and EQUATIONS can be used for this purpose A sample equation declaration is shown below EQUATIONS el e2 e3 The naming rules for equations are the same as those for variables i e all equation names are case sensitive and should begin with a letter e RELAXATION_ONLY_EQUATIONS lt list equation names gt This equation declaration can be used to specify constraints to be used for relaxation construction only This is optional and must follow after the EQUATIONS declaration and before the equation definitions e CONVEX_EQUATIONS lt list equation names gt This equation declaration can be used to specify constraints that are convex This is op tional and must follow after the EQUATIONS declaration and before the equation definitions e Equation definition Each equation or inequality declared above is written in this section of the input file The equation is preceded by its corresponding identifier The bounds on the equations can be specified using the symbols equal to lt less than or equal to and gt greater than or equal to Both lt and gt can be used in the same equation A sample eq
41. xa 1 x4 1 xo 1 x6 1 xi 15 xo 15 UPPER_BOUNDS xt d x2 1 xa 1 x4 1 x52 de x6 1 xl x8 1 EQUATIONS e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 e13 e14 e15 e16 e2 0 004731 x1 x3 0 1238 x1 0 3578 x2 x3 0 001637 x2 0 9338 x4 x7 BARON user manual v 15 6 5 17 lt 0 3571 e3 0 1238 x1 0 004731 x1 x3 0 3578 x2 x3 0 001637 x2 0 9338 x4 x7 lt 0 3571 e4 0 2238 x1 x3 0 2638 x1 0 7623 x2 x3 0 07745 x2 0 6734 x4 x7 lt 0 6022 e5 0 2238 x1 x3 0 2638 x1 0 7623 x2 x3 0 07745 x2 0 6734 x4 x7 lt 0 6022 e6 x6 x8 0 3578 x1 0 004731 x2 lt 0 e7 x6 x8 0 3578 x1 0 004731 x2 lt 0 e8 0 7623 x1 0 2238 x2 0 3461 e9 x172 x2 2 lt 1 e10 x172 x2 2 lt 1 e11 x372 x4 2 lt 1 e12 x3 2 x4 2 lt 1 e13 x5 2 x6 2 lt 1 e14 x5 2 x6 2 lt 1 e15 x7 2 x8 2 lt 1 e16 x7 2 x8 2 lt 1 OBJ minimize 0 The above problem has 14 different solutions Looking at the BARON results file all these solutions can be found after the Normal Completion message 6 3 Using BARON as a multi start heuristic solver To gain insight into the difficulty of a nonlinear program especially with regard to existence of multiple local solutions modelers often make use of multiple local searches from randomly gen erated starting points This can be easily done with
42. xz where x and y are both variables It is permissible to have either x or y as a variable in this case but not both The following reformulation can be used around this x exp y log 1 This reformulation is done automatically when BARON is used under AIMMS AMPL GAMS or MATLAB BARON does not allow the use of absolute values in the model file However this func tion can be modeled equivalently as x 12 This reformulation is done automatically when BARON is used under AIMMS AMPL GAMS or MATLAB Parentheses and can be used in any meaningful combination with operations in mathematical expressions The input file is divided into two sections the options and the problem data sections 4 3 The options section This section is optional If used it should be placed before any other programmatic statements Any of BARON s algorithmic options can be specified here This section has the following form OPTIONS lt optnamei gt lt optvaluel gt lt optname2 gt lt optvalue2 gt lt optname3 gt lt optvalue3 gt 6 BARON user manual v 15 6 5 The names and corresponding values of the BARON options are described in detail in Section 7 Options not specified here take their default values Instead of OPTIONS the word OPTION can also be used 4 4 The problem data This section contains the data relating to the particular problem to be solved The section can be divided into the follo
Download Pdf Manuals
Related Search