panmip.m

由matlab开发的hybrid系统的描述语言

%                      (default: 10 digits)
%          reordername:Name of auxilary file denoting the reordering of 
%                      variables
%                      (default: 'reordered')  
%          problemname:Name of auxilary file denoting the name of the problem
%                      for Baron
%                      (default: 'problem')
%          deleteflag: If set > 0, a file possibly present in the current
%                      directory with the same name as the problem file
%                      generated is deleted, otherwise an error is produced
%                      (default: delete file)
%          infinity:   In the box bounds there might be variables that are not
%                      bounded and the to the values +/- inf. panmip replaces
%                      these bounds with numbers of large magnitude given by
%                      this option
%                      (default: 1e8)
%
%          Options.sunbaronLP: 
%          the same options as Options.sunbaronQP, in addition:
%
%          suppresserr: does not terminate with an error, when the Hessian H is
%                       nonzero, but it sets the H to 0 solving an MILP
%                       (default: 0)
%
%          Options.fletcher (old-sparse):
%          priority
%          iprint
%
%          Options.mps
%          outname:     the file name of the problem definition is mps format 
%                       (default = 'mpsfile.mps')          
%          infinity:    a large positive number denoting infinity in bounds
%                       (default = 1e8)
%          extractbox:  1: extract box bounds from Cx <= d
%                       0: leave constraints as they are 
%                       (default: 0)
%          format:      the mps file produced is either in syntax required by
%                       Dash-Opt for MIQP/MILP ==> 'xpress'
%                       or in syntax required by cplex for MILP only
%                       ==> 'cplex'
%                       (default: 'cplex')
%          verbose:     1: high verbosity
%                       0: quiet
%                       (default: 0)
%          QPflag:      These flags advise the mps converter to interpret the
%          MILPflag:    problem to be converted as QP, MILP, or LP respectively
%          LPflag:      This is mainly used for the call within 'cplex_file'
%                       (default: all 0, this means MIQP)
%          suppresserr: see the same option in cplex_file. Advices the generator
%                       of the mps file to check, whether there are optimization
%                       variables appearing with coefficient zero in the cost
%                       function. If this is the case, these variables are
%                       reported with coefficient zero in the COLUMNS section
%                       (default: 0, i.e. do not report zero coefficients)
%
%          Options.cplex
%          verbose:     1: verbose,  0: silent
%                       (default: 0) 
%          savecplex:   1: save a copy of mps file,   0: don't save
%                       (default: 0)
%
%          Options.cplex_file
%          deletefile:  1: deletes the files generated for / by CPLEX
%                       0: leaves them in the working directory
%                       (default: 1)
%          infinity:    large positive number for bounds
%                       (default: 1e8)
%          mpsfile:     filename for the mps problem passed to CPLEX
%                       (default: 'ravioli_cplex_prob_298.mps')
%          runfile:     filename for calling CPLEX
%                       (default: 'basilicoVerde_run_file_563')
%          solutionfile:filename for the solution of CPLEX
%                       (default: 'solution_stracciatella_6329')
%          initialsolutionfile: filename for the initial solution provided to 
%                       CPLEX. The file format is described in the CPLEX
%                       reference manual (ver.7.0) on page 544
%                       (default: 'initial_solution_malaga_1245')
%          extractbox:  1: extract box bounds from Cx <= d
%                       0: leave constraints as they are
%                       (default: 0)
%          itolerance:  small positive number defining the integrality tolerance
%                       This options has been kept for downward compatibility.
%                       See below for CPLEX related options, we recommend to use
%                       the option integrality instead. 
%                       (default: 1e-5) this default value is suggested by CPLEX
%          nodeselect:  string defining strategy for mixed integer optimization
%                       concerning the node selection strategy
%                       'depth'      : depth-first strategy
%                       'best-bound' : best-bound search
%                       'best-est'   : best-estimate search
%                       'a-best-est' : alternate best-estimate search
%                       (default: 'best-bound') 
%          suppresserr: does not terminate with an error, when the Hessian H is
%                       nonzero, but it sets the H to 0 solving an MILP
%                       Setting this option to 1 allows to use CPLEX to check
%                       whether an MIQP is feasible. Since the solution is then
%                       found only minimizing the linear term of the quadratic
%                       cost function, the optimimum so obtained is an upper
%                       bound to the optimum of the MIQP
%                       (default: 0)
%          presolve:    turns off the presolve option of CPLEX
%                       (default: 1, i.e. presolve is used)
%          
%                       The following options allow to set the MIP parameter
%                       tolerances provided by CPLEX, see page 169 in the ILOG
%                       CPLEX 7.0 User's Manual for details. The option names
%                       are the same as given in CPLEX. All default values 
%                       correspond to the CPLEX default values.
%          
%          absmipgap:   set absolute mixed integer optimality gap tolerance
%                       The solution is guaranteed to lie within this distance
%                       to the optimal value. Increasing this value speeds up
%                       computations, but reduces the chance to get the true
%                       optimum
%                       (default: 1e-6)
%          integrality: set integrality tolerance
%                       the same as itolerance above. The usage of 'integrality'
%                       is preferred and is chosen, if both parameter should be
%                       erroneously defined
%                       (default: 1e-5)
%          lowercutoff  ... coming soon
%          mipgap:      set mixed integer optimality gap tolerance
%                       (default: 1e-4)
%          objdifference... coming soon
%          relobjdifference... coming soon
%          uppercutoff  ... coming soon
%          timelimit:   maximum time spent by CPLEX optimizing, 
%                       recall that extra time is required for I/O
%                       (default: CPLEX default, see CPLEX manual)
%          mip_limits_solutions: maximum number of mixed integer feasible
%                       solution found 
%                       (default: CPLEX default, see CPLEX manual)
%          load_tree_file: load a previously computed b&b tree file, see CPLEX 
%                       manual
%                       (default: 0)
%          write_tree_file: write the present b&b tree file, see CPLEX manual
%                       (default: 0)
%          treefile:    file name used for the tree file
%                       (default: tree_file_prosciutto_e_funghi_54386)
%                       This file gets renamed to 'treefile'_old during the
%                       execution of the routine.
%          quality:     displays solution quality of cplex's solution, if set to
%                       one
%                       (default: 0)
%          
%                       The default names are such, that most likely they do not
%                       exist yet in the working directory
%
%          Options.xpress
%          verbose:     2: high verbosity, 1: medium verbosity, 0: silent
%                       (default: 0) 
%
%          Options.xpress_file
%          outname:     name of the mps file storing the problem to be passed
%                       to xpress
%                       (default: 'per_il_prog_degliamichetti_43.mps')
%          runfile:     filename for calling xpress
%                       (default: 'run_file_8927_salsadisoia')
%          infinity:    large positive number for bounds
%                       (default: 1e8)
%          deletefile:  1: deletes the files generated for / by CPLEX
%                       0: leaves them in the working directory
%                       (default: 1)
%          extractbox:  1: extract box bounds from Cx <= d
%                       0: leave constraints as they are
%                       (default: 0)
%          eliminatebox:1: translates box bound to inequalities
%                       0: leaves box bounds as they are
%                       (default: 0)
%
%                       The default names are such, that most likely they do not
%                       exist yet in the working directory
%
%
% Outputs: xopt:    minimizer of the problem
%          fopt:    optimal cost of the problem
%          flag:    characterization of solution according to the following list
%                   1 : integer feasible, optimum found
%                   2 : flag returned when calling panmip with the solver 'mps'
%                   5 : feasible, but not integer feasible
%                   7 : infeasible, i.e. relaxed problem is infeasible
%                  11 : integer feasible, the limit maxqp of QPs has been
%                       reached, i.e. the solution might be suboptimal
%                  15 : feasible, but not integer feasible, the limit maxqp of
%                       QPs has been reached, i.e. did not search long enough
%                  -1 : the solution is unbounded
%                   0 : other problems for the solver, check the solver
%                       please immediately report to the authors any occcurence
%                       of this value for the flag 
%
%          If the solution could not be found (flag= 7|0|-1|2), the values for 
%          xopt and fopt returned are:    xopt = [inf, ... , inf]    fopt = inf
%
%          Extendedflag: Variable in matlab's structure format, which contains
%                        other informations about the MIQP or MILP. The
%                        following fields may be accessed in Extendedflag. If 
%                        the information is not provided by the corresponding
%                        solver, the field is not defined. 
%                        
%                        Some fields are listed next. Otherwise use the matlab
%                        function fieldnames() to get the information about the
%                        fields returned in Extendedflag.
%
%          Extendedflag.QPiter: Number of relaxed QPs or LPs solved in the
%                               branch and bound tree
%          Extendedflag.time  : Time elapsed for running panmip.m
%          Extendedflag.optQP : Number of relaxed QP at which the optimal
%                               has been found
%
%          Very few people in the world will ever read this file down to this 
%          point, because they will think it is boring and useless. Obviously 
%          you are one of those few. Therefore we would like to thank you for 
%          your patience and for your interest, and wish you a lot of success 
%          while solving your MIQPs and MILPs!
%
% Matlab:  This file has been designed for matlab 5.3 (Release 11)
%
% Versions:Older versions of panmip.m are available from the authors upon
%          request
%
% References:
%          - ILOG CPLEX 7.0, User's Manual, 2000, http://www.ilog.com
%          - ILOG CPLEX 7.0, Reference Manual, 2000, http://www.ilog.com 
%          - miqp.m: A Matlab function for solving Mixed Integer Quadratic
%            Programs, Bemporad A. and Mignone D., Technical Report AUT00-22,
%            Automatic Control Laboratory, ETH Zuerich, Switzerland,
%            http://www.aut.ee.ethz.ch/~hybrid/miqp/ 
%
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% Legal note:
%
%          This library is free software; you can redistribute it and/or
%          modify it under the terms of the GNU Lesser General Public
%          License as published by the Free Software Foundation; either
%          version 2.1 of the License, or (at your option) any later version.
%
%          This library is distributed in the hope that it will be useful,
%          but WITHOUT ANY WARRANTY; without even the implied warranty of
%          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
%          Lesser General Public License for more details.
% 
%          You should have received a copy of the GNU Lesser General Public
%          License along with this library; if not, write to the 
%          Free Software Foundation, Inc., 59 Temple Place, Suite 330, 
%          Boston, MA 02111-1307 USA
%
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% Contact: Domenico Mignone
%          Automatic Control Laboratory
%          ETH Zentrum
%          Zurich, Switzerland
%          [e-mail]
%
%          Fabio Danilo Torrisi
%          Automatic Control Laboratory
%          ETH Zentrum
%          Zurich, Switzerland
%          [e-mail]
%
%          Comments and bug reports are highly appreciated
%
% (C) 2000,2001  Domenico Mignone, Fabio Danilo Torrisi
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% Acknowledgements:
%          The authors would like to thank the following people for the useful 
%          comments and the testing of the code:
%
%          Alberto Bemporad
%          Giancarlo Ferrari-Trecate
%          Eduardo Gallestey
%          Researchers of ABB Corporate Research Center, Daettwil, Switzerland
%          Paolo Letizia
%          Matteo Spedicato
%          Tobias Geyer 
%          Francesco Borrelli
%          Tal Pasternak
%          Bostjan Potocnik
%
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% TO DO:   - check error codes of cplex and xpress and give them meaningful
%            interpretations
%
%          - complete status messages from xpress to be returned as flag
%
%          - match exactly length of the strings when reading solution files
%            row by row
%
% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%
% Expertise:  This list collects some non-obvious features that have caused
%             problems in the past and that may be worth knowing, when using
%             or updating panmip.m
%
%          23.03.2000
%          ----------
%          consider the LP 
%              
%              min(x)
%              s.t.    -x <= 0 
%                   -400x <= 0.4
% 
%          The solution is obviously x = 0. 
%          The different available solvers in matlab however report different
%          solutions. The routines "linprog" and "quadprog" report the output
%          parameter "exitflag". If exitflag<0 the problem is declared to be
%          either unbounded or infeasible. Solving the problem above with both
%          "linprog" and "quadprog" gives the value -1 for "exitflag", even
%          though the problem is neither infeasible nor unbounded. The old
%          routine "lp" gives the correct result. The same problem can be
%          rewritten as