DICOPT
Author
Ignacio E. Grossmann, Jagadisan Viswanathan, Aldo Vecchietti; Engineering Research Design Center, Carnegie Mellon University, Pittsburgh, PA
Ramesh Raman, Erwin Kalvelagen; GAMS Development Corporation, Washington D.C.

Introduction

DICOPT is a program for solving mixed-integer nonlinear programming (MINLP) problems that involve linear binary or integer variables and linear and nonlinear continuous variables. While the modeling and solution of MINLP optimization problems has not yet reached the stage of maturity and reliability achieved by linear, integer, or non-linear programming modeling, these problems still have rich areas of application. For example, they often arise in engineering design, management sciences, and finance. DICOPT (DIscrete and Continuous OPTimizer) was developed by J. Viswanathan and Ignacio E. Grossmann at the Engineering Design Research Center (EDRC) at Carnegie Mellon University. The program is based on the extensions of the outer-approximation algorithm for the equality relaxation strategy. The MINLP algorithm inside DICOPT solves a series of NLP and MIP sub-problems. These sub-problems can be solved using any NLP (Nonlinear Programming) or MIP (Mixed-Integer Programming) solver that runs under GAMS. The performance will heavily depend on the choice of the selected subsolvers.

Although the algorithm has provisions to handle non-convexities, it does not necessarily obtain the global optimum.

The GAMS/DICOPT system has been designed with two main goals in mind:

  • to build on existing modeling concepts, introduce a minimum of extensions to the existing modeling language, and provide upward compatibility to ensure easy transition from existing modeling applications to nonlinear mixed-integer formulations
  • to use existing optimizers to solve the DICOPT sub-problems. This allows one to match the best algorithms to the problem at hand and guarantees that any new development and enhancements in the NLP and MIP solvers become automatically and immediate available to DICOPT.

Requirements

In order to use DICOPT you will need to have access to a licensed GAMS BASE system as well as at least one licensed MIP solver and one licensed NLP solver. For difficult models it is advisable to also have access to multiple solvers.

How to Run a Model with GAMS/DICOPT

DICOPT is only able to solve MINLP and MIQCP models. If you did not specify DICOPT as the default solver you can use the following statement in your GAMS model:

   option minlp = dicopt;

This should appear before the solve statement. DICOPT automatically uses the default MIP and NLP solver to solve its sub-problems. One can override this with GAMS statements like:

   option nlp = conopt;  { or any other nlp solver }
   option mip = gurobi;  { or any other mip solver }

These options can also be specified on the command line:

   > gams mymodel minlp=dicopt nlp=conopt mip=gurobi

In the Integrated Development Environment (IDE) the command line option can be specified in the edit line in the right upper corner of the main window.

Possible NLP solvers include conopt, ipopt, knitro, minos, and snopt. Possible MIP solvers include cplex, gurobi, and xpress.

With an option file it is even possible to use alternate solvers in different cycles. Section DICOPT Options explains this is in detail.

Overview of DICOPT

DICOPT solves models of the form:

\[ \begin{array}{rl} \tag{MINLP} \min\> \text{or}\> \max & f(x,y) \\ \text{subject to} & g(x,y) \sim b \\ & \ell_x \le x \le u_x \\ & y \in \lceil\ell_y\rceil,...,\lfloor u_y \rfloor \end{array} \]

where \(x\) are the continuous variables and \(y\) are the discrete variables. The symbol \(\sim\) is used to denote a vector of relational operators \(\{\le,=,\ge\}\). The constraints can be either linear or non-linear. Bounds \(\ell\) and \(u\) on the variables are handled directly. \(\lceil x \rceil\) indicates the smallest integer, greater than or equal to \(x\). Similarly, \(\lfloor x \rfloor\) indicates the largest integer, less than or equal to \(x\). The discrete variables can be either integer variables or binary variables.

The Algorithm

The algorithm in DICOPT is based on three key ideas:

  • Outer Approximation
  • Equality Relaxation
  • Augmented Penalty

Outer Approximation refers to the fact that the surface described by a convex function lies above the tangent hyper-plane at any interior point of the surface. (In 1-dimension, the analogous geometrical result is that the tangent to a convex function at an interior point lies below the curve). In the algorithm outer-approximations are attained by generating linearizations at each iterations and accumulating them in order to provide successively improved linear approximations of nonlinear convex functions that underestimate the objective function and overestimate the feasible region.

Equality Relaxation is based on the following result from non-linear programming. Suppose the MINLP problem is formulated in the form:

\[ \begin{array}{rl} \text{minimize or maximize}\> & f(x) + c^Ty \\ \text{subject to} \> & G(x) + Hy \sim b \\ & \ell \le x \le u \\ & y \in \{0,1\} \end{array} \]

i.e. the discrete variables are binary variables and they appear linearly in the model.

Let \(y^{(0)}\) be any fixed binary vector and let \(x^{(0)}\) be the solution of the corresponding NLP subproblem:

\[ \begin{array}{rl} \text{minimize}\> & c^Ty^{(0)} + f(x)\\ \text{subject to} \> & Ay^{(0)} + h(x) = 0 \\ & By^{(0)} + g(x) \le 0 \\ & \ell \le x \le u \end{array} \]

Further let

\[ \begin{array}{rl} T^{(0)} &= \mathrm{diag}(t_{i,i}) \\ t_{i,i} &= \mathrm{sign}(\lambda_i) \end{array} \]

where \(\lambda_i\) is the Lagrange multiplier of the \(i\)-th equality constraint.

If \(f\) is pseudo-convex, \(h\) is quasi-convex, and \(g\) is quasi-convex, then \(x^0\) is also the solution of the following NLP:

\[ \begin{array}{rl} \text{minimize}\> & c^Ty^{(0)} + f(x) \\ \text{subject to}\> & T^{(0)}(Ay^{(0)} + h(x)) \le 0 \\ & By^{(0)} + g(x) \le 0 \\ & \ell \le x \le u \end{array} \]

In colloquial terms, under certain assumptions concerning the convexity of the nonlinear functions, an equality constraint can be relaxed to be an inequality constraint. This property is used in the MIP master problem to accumulate linear approximations.

Augmented Penalty refers to the introduction of (non-negative) slack variables on the right hand sides of the just described inequality constraints and the modification of the objective function when assumptions concerning convexity do not hold.

The algorithm underlying DICOPT starts by solving the NLP in which the 0-1 conditions on the binary variables are relaxed. If the solution to this problem yields an integer solution the search stops. Otherwise, it continues with an alternating sequence of nonlinear programs (NLP) called subproblems and mixed-integer linear programs (MIP) called master problems. The NLP subproblems are solved for fixed 0-1 variables that are predicted by the MIP master problem at each (major) iteration. For convex problems the master problem also provides a lower bound on the objective function. This lower bound (in the case of minimization) increases monotonically as iterations proceed due to the accumulation of linear approximations. Note that in the case of maximization this bound is an upper bound which can be used as a stopping criterion through a DICOPT option stop 1 (see section DICOPT Options). Another stopping criterion that tends to work very well for non-convex problems (and even for convex problems) is based on the heuristic: stop as soon as the NLP subproblems start worsening (i.e. the current NLP subproblem has an optimal objective function that is worse than the previous NLP subproblem). This stopping criterion relies on the use of the augmented penalty, and is used in the description of the algorithm below. This is also the default stopping criterion in the implementation of DICOPT. The algorithm can be stated briefly as follows:

  1. Solve the NLP relaxation of the MINLP program. If \(y^{(0)}=y\) is integer, stop(integer optimum found). Else continue with step 2.
  2. Find an integer point \(y^{(1)}\) with an MIP master problem that features an augmented penalty function to find the minimum over the convex hull determined by the half-spaces at the solution \((x^{(0)},y^{(0)})\).
  3. Fix the binary variables \(y=y^{(1)}\) and solve the resulting NLP. Let \((x^{(1)},y^{(1)})\) be the corresponding solution.
  4. Find an integer solution \(y^{(2)}\) with a MIP master problem that corresponds to the minimization over the intersection of the convex hulls described by the half-spaces of the KKT points at \(y^{(0)}\) and \(y^{(1)}\).
  5. Repeat steps 3 and 4 until there is an increase in the value of the NLP objective function. (Repeating step 4 means augmenting the set over which the minimization is performed with additional linearizations - i.e. half-spaces - at the new KKT point).

In the MIP problems integer cuts are added to the model to exclude previously determined integer vectors \(y^{(1)},y^{(2)},...,y^{(K)}\).

For a detailed description of the theory and references to earlier work, see [243, 142, 75] .

The algorithm has been extended to handle general integer variables and integer variables appearing nonlinearly in the model.

Modeling

Relaxed Model

Before solving a model with DICOPT, the user is strongly advised to experiment with the relaxed model where the integer restrictions are ignored. This is the RMINLP model. As the DICOPT will start solving the relaxed problem and can use an existing relaxed optimal solution, it is a good idea to solve the RMINLP always before attempting to solve the MINLP model, i.e., the following fragment is not detrimental with respect to performance:

  model m /all/;
  option nlp=conopt;
  option mip=cplex;
  option rminlp=conopt;
  option minlp=dicopt;
*
* solve relaxed model
*
  solve m using rminlp minimizing z;
  abort$(m.modelstat > 2.5) "Relaxed model could not be solved";

*
* solve minlp model
*
  solve m using minlp minimizing z;

The second SOLVE statement will only be executed if the first SOLVE was successful, i.e., if the model status was one (optimal) or two (locally optimal).

In general it is not a good idea to try to solve an MINLP model if the relaxed model cannot be solved reliably. As the RMINLP model is a normal NLP model, some obvious points of attention are:

  • Scaling. If a model is poorly scaled an NLP solver may not be able find the optimal or even a feasible solution. Some NLP solvers have automatic scaling algorithms, but often it is better to attack this problem on the modeling level. The GAMS scaling facility can help in this respect.
  • Starting point. If a poor starting point is used, the NLP solver may not be able to find a feasible or optimal solution. A starting point can be set by setting level values, e.g. X.L = 1;. The GAMS default levels are zero, with is often not a good choice.
  • Adding bounds. Add bounds so that all functions can be properly evaluated. If you have a function \(\sqrt{x}\) or \(\log(x)\) in the model, you may want to add a bound X.LO=0.001;. If a function like \(\log(f(x))\) is used, you may want to introduce an auxiliary variable and equation \(y=f(x)\) with an appropriate bound Y.LO=0.001;.

In some cases the relaxed problem is the most difficult model. If more than one NLP solver is available you may want to try them in a sequence:

  model m /all/;
  option nlp=conopt;
  option mip=cplex;
  option rminlp=conopt;
  option minlp=dicopt;
*
* solve relaxed model
*
  solve m using rminlp minimizing z;
  if (m.modelstat > 2.5,
     option rminlp=minos;
     solve m using rminlp minimizing z;
  );
  if (m.modelstat > 2.5,
     option rminlp=snopt;
     solve m using rminlp minimizing z;
  );

*
* solve minlp model
*
  solve m using minlp minimizing z;

In this fragment we first try to solve the relaxed model using CONOPT. If that fails we try MINOS, and if that solve also fails we try SNOPT.

It is worthwhile to spend some time getting the relaxed model to solve reliably and speedily. In most cases, modeling improvements in the relaxed model, such as scaling, will also benefit the subsequent NLP sub-problems. In general these modeling improvements turn out to be rather solver independent: changes that improve the performance with CONOPT will also help solving the model with MINOS.

OPTCR and OPTCA

The DICOPT algorithm assumes that the integer sub-problems are solved to optimality. The GAMS options for OPTCR and OPTCA are therefore ignored: subproblems are solved with both tolerances set to zero. If you want to solve a MIP sub-problem with an optimality tolerance you can use the DICOPT option file to set OPTCR or OPTCA. For more information see section DICOPT Options.

For models with many discrete variables, it may be necessary to introduce an OPTCR or OPTCA option in order to solve the model in acceptable time. For models with a limited number of integer variables the default to solve MIP sub-models to optimality may be acceptable.

Integer Formulations

A number of MIP formulations are not very obvious and pose a demand on the modeler's knowledge and experience. A good overview of integer programming modeling is given in [254] .

Many integer formulations use a so-called big- \(M\) construct. It is important to choose small values for those big- \(M\) numbers. As an example consider the fixed charge problem where \(y_i \in \{0,1\}\) indicate if facility \(i\) is open or closed, and where \(x_i\) is the production at facility \(i\). Then the cost function can be modeled as:

\[ \begin{array}{rl} C_i &= f_i y_i + v_i x_i \\ x_i & \le M_i y_i \\ & y_i \in \{0,1\} \\ & 0 \le x_i \le cap_i \end{array} \]

where \(f_i\) is the fixed cost and \(v_i\) the variables cost of operating a facility \(i\). In this case the chosen \(M_i\) should be large enough that \(x_i\) is not restricted if \(y_i=1\). On the other hand, it should be as small as possible. This leads to a choice to have \(M_i\) equal to the (tight) upperbound of variable \(x_i\) (i.e. the capacity \(cap_i\) of facility \(i\)).

Non-smooth Functions

GAMS alerts NLP modelers against the use of non-smooth functions such as min(), max(), smin(), smax() and abs(). In order to use these functions, a non-linear program needs to be declared as a DNLP model instead of a regular NLP model:

option dnlp=conopt;
model m /all/;
solve m minimizing z using dnlp;

This construct will warn the user that problems may arise due to the use of non-smooth functions.

A possible solution is to use a smooth approximation. For instance, the function \(f(x) = |x|\) can be approximated by \(g(x) = \sqrt{x^2 + \varepsilon}\) for some \(\varepsilon > 0\). This approximation does not contain the point \((0,0)\). An alternative approximation can be devised that has this property:

\[ f(x) \approx \frac{2x}{1+e^{-x/h}} - x \]

MINLP models do not have such protection against non-smooth functions, but the use of such functions is just as problematic here. It is possible to use discrete variables with MINLP models in order to model if-then-else situations. For instance, in the case of the absolute value we can replace \(x\) by \(x^+ - x^-\) and \(|x|\) by \(x^+ + x^-\) by using:

\[ \begin{array}{rl} x &= x^+ - x^- \\ |x| &= x^+ + x^- \\ x^+ &\le \delta M \\ x^- &\le (1-\delta) M \\ x^+,x^- &\ge 0 \\ \delta &\in \{0,1\} \end{array} \]

where \(\delta\) is a binary variable.

GAMS Options

GAMS options are specified in the GAMS model source, using either the option statement or a model suffix.

The OPTION Statement

An option statement sets a global parameter. An option statement should appear before the solve statement, as in:

   model m /all/;
   option iterlim=100;
   solve m using minlp minimizing z;

Option statements that affect the behavior of DICOPT are listed below:

  • option domlim = n;
    This option sets a limit on the total accumulated number of non-linear function evaluation errors that are allowed while solving the NLP subproblems or inside DICOPT itself. An example of a function evaluation error or domain error is taking the square root of a negative number. This situations can be prevented by adding proper bounds. The default is zero, i.e. no function evaluation errors are allowed.

    In case a domain error occurs, the listing file will contain an appropriate message, including the equation that is causing the problem. For instance:
      **** ERRORS(S) IN EQUATION loss(cc,sw)
           2 instance(s) of - UNDEFINED REAL POWER (RETURNED  0.0E+00)

    If such errors appear you can increase the DOMLIM limit, but often it is better to prevent the errors from occurring in the first place. In many cases this can be accomplished by adding appropriate bounds. Sometimes extra variables and equations need to be added to accomplish this. For instance, with an expression like \(\log(x-y)\), you may want to introduce a variable \(z > \varepsilon\) and an equation \(z = x -y\), so that the expression can be rewritten as \(\log(z)\).
  • option iterlim = n;
    This option sets a limit on the total accumulated (minor) iterations performed in the MIP and NLP subproblems.
  • option minlp = dicopt;
    This option selects DICOPT to solve MINLP problems.
  • option mip = s;
    This option sets the MIP solver to be used for the MIP master problems. Note that changing from one MIP solver to another can lead to different results, and may cause DICOPT to follow a different path.
  • option nlp = s;
    This option sets the NLP solver to be used for the NLP sub-problems. Note that changing from one NLP solver to another can lead to different results, and may cause DICOPT to follow a different path.
  • option optca = x;
    This option is ignored. MIP master problems are solved to optimality unless specified differently in the DICOPT option file.
  • option optcr = x;
    This option is ignored. MIP master problems are solved to optimality unless specified differently in the DICOPT option file.
  • option reslim = x;
    This option sets a limit on the total accumulated time (in seconds) spent inside DICOPT and the subsolvers.
  • option sysout = on;
    This option will print extra information to the listing file.

In the list above (and in the following) \(n\) indicates an integer number. GAMS will also accept fractional values, which will be rounded. Options marked with an $x$ parameter expect a real number. Options with an \(s\) parameter expect a string argument.

The Model Suffix

Some options are set by assigning a value to a model suffix, as in:

   model m /all/;
   m.optfile=1;
   solve m using minlp minimizing z;

Model suffixes that affect the behavior of DICOPT are listed below:

  • m.dictfile = 1;
    This option tells GAMS to write a dictionary file containing information about GAMS identifiers (equation and variables names). Such information is needed when the DICOPT option nlptracelevel is used, otherwise the option can be ignored.
  • m.iterlim = n;
    Sets the total accumulated (minor) iteration limit. This option overrides the global iteration limit set by an option statement, e.g.,
        model m /all/;
        m.iterlim = 100;
        option iterlim = 1000;
        solve m using minlp minimizing z;
    will cause DICOPT to use an iteration limit of 100.
  • m.optfile = 1;
    This option instructs DICOPT to read an option file dicopt.opt. This file should be located in the current directory (or the project directory when using the GAMS IDE). The contents of the option file will be echoed to the listing file and to the screen (the log file):
      --- DICOPT: Reading option file D:\MODELS\SUPPORT\DICOPT.OPT
      > maxcycles 10
      --- DICOPT: Starting major iteration 1
    If the option file does not exist, the algorithm will proceed using its default settings. An appropriate message will be displayed in the listing file and in the log file:
      --- DICOPT: Reading option file D:\MODELS\SUPPORT\DICOPT.OPT
      --- DICOPT: File does not exist, using defaults...
      --- DICOPT: Starting major iteration 1
  • m.optfile = n;
    If \(n>1\) then the option file that is read is called dicopt.op \(n\) (for \(n=2,...,9\)) or dicopt.o \(n\) (for \(n=10,...,99\)). E.g. m.optfile=2; will cause DICOPT to read dicop.op2.
  • m.prioropt = 1;
    This option turns on the use of priorities on the discrete variables. Priorities influence the branching order chosen by the MIP solver during solution of the MIP master problems. The use of priorities can greatly impact MIP solver performance. The priorities themselves have to be specified using the .prior variables suffix, e.g. x.prior(i,j) = ord(i);. Contrary to intuition, variables with a lower value for their priority are branched on before variables with a higher priority, i.e., the most important variables should get lower priority values.
  • m.reslim = x;
    Sets the total accumulated time limit. This option overrides the global time limit set by an option statement.

DICOPT Options

This sections describes the options that can be specified in the DICOPT option file. This file is usually called dicopt.opt. The optfile model suffix must be set to tell DICOPT to read this file:

   model m /all/;
   m.optfile=1;
   solve m using minlp minimizing z;

The option file is searched for in the current directory, or in the project directory when the IDE is used.

The option file is a standard text file, with a single option on each line. All options are case-insensitive. A line is a comment line if it starts with an asterisk, * in column one. A valid option file can look like:

   * stop only on infeasible MIP or hitting a limit
   stop 0
   * use minos to solve first NLP sub problem
   * and conopt for all subsequent ones
   nlpsolver minos conopt

A convenient way to write the option file from within a GAMS model is to use the following construct:

   $onecho > dicopt.opt
   stop 0
   nlpsolver minos conopt
   $offecho

This will make the model self-contained. Notice, however, that this overwrites an existing file dicopt.opt.

Available DICOPT options are listed below:

Algorithmic options

Option Description Default
continue How to proceed in case of NLP errors 2
convex If enabled, the defaults for a number of other options are set to values appropriate to convex MINLPs 0
infbnd Bound to use for unbounded integer variables in integer cuts 10000
infeasder Use derivatives of infeasible nonlinear subproblems 0
maxcycles Maximum number of cycles 20
relaxed How to start DICOPT 1
solvelink Solvelink for NLP and MIP subsolver 5
stop Stopping criterion 2
usexinit Use the user initial point as starting point for all NLP solves 0
weight Penalty parameter 1000

Tolerances

Option Description Default
epsmip Tolerance on test on monotonic improvement of MIP master problem 1.0e-6
epsx Tolerance for integer values when loading relaxed solution 1.0e-3

MIP masterproblem options

Option Description Default
mipiterlim List of iteration limits
mipoptfile List of option files for MIP solver
mipreslim List of resource limits
mipsolver List of MIP solvers
optca List of OPTCA values
optcr List of OPTCR values

NLP subproblem options

Option Description Default
domlim List of allowed number of domain errors
nlpiterlim List of iteration limits
nlpoptfile List of option files for NLP solver
nlpreslim List of resource limits
nlpsolver List of NLP solvers
nlptracefile Base name of trace files nlptrace
nlptracelevel Trace level 0

Feasibility Pump

Option Description Default
feaspump Whether to run the Feasibility Pump 0
fp_acttol Tolerance on when to consider an equation as active 1E-6
fp_cutoffdecr Additional relative decrement of cutoff value for the original objective function 0.1
fp_dumpsubprob Whether to dump subproblems (NLPs and MIPs) into GAMS files 0
fp_iterlimit Major Iteration limit maxint
fp_projzerotol Tolerance on when to consider optimal value of projection problem as zero, which may trigger the solution of a Sub-NLP 1E-6
fp_sollimit Stop when a number of (improving) solutions has been bound maxint
fp_stalllimit Stop when no improving solution has been bound for a number of FP iterations, -1 to disable 5
fp_subsolverlog Whether to show the log of subsolvers 0
fp_timelimit Time limit maxdouble
fp_transfercuts Whether to transfer cuts from the Feasibility Pump MIP to the DICOPT MIP (all except from the round in which the FP MIP became infeasible) 1

Detailed Options Description

continue (integer): How to proceed in case of NLP errors

This option can be used to let DICOPT continue in cases of NLP solver failure. The preferred approach is to fix the model so that NLP subproblems solve without problems. In some cases, however, (partial) failures of an NLP solver in solving the NLP subproblems can be ignored, as DICOPT may recover later on. Adding the option continue 0 during model debugging enables DICOPT to function in a more specific way.

Default: 2

valuemeaning
0 Stop on solver failure
Stop on solver failure. DICOPT will terminate when an NLP subproblem can not be solved to optimality. Some NLP solvers terminate with a status other than optimal if not all of the termination criteria are met. For instance, the change in the objective function is negligible (indicating convergence) but the reduced gradients are not within the required tolerance. Such a solution may or may not be close to the (local) optimum. Using continue 0 will prevent DICOPT from accepting such a solution.
1 Accept non-optimal feasible solutions
NLP subproblem failures resulting in a non-optimal but feasible solutions are accepted. Sometimes an NLP solver cannot make further progress towards meeting all optimality conditions, although the current solution is feasible. Such a solution can be accepted by this option.
2 Ignore infeasible solutions
NLP subproblem failures resulting in a non-optimal but feasible solution are accepted (as in option continue 1). NLP subproblem failures resulting in an infeasible solution are ignored. The corresponding configuration of discrete variables is forbidden to be used again. An integer cut to accomplish this is added to subsequent MIP master problems. Note that the relaxed NLP solution should be feasible. This setting is the default.

convex (boolean): If enabled, the defaults for a number of other options are set to values appropriate to convex MINLPs

If this option is enable, the default option values will be changed such that DICOPT will stop on crossover (stop set to 1), linearizations from infeasible NLP subproblems will be added to the MIP master problem (infeasder set to 1), and the feasibility pump is run if there are no semicontinuous or semiinteger variables and no special ordered sets (feaspump set to 1).

Default: 0

domlim (string): List of allowed number of domain errors

domlim \(i_1\) \(i_2\) \(\dots\) \(i_n\). Sets a limit of the number of function and derivative evaluation errors for a particular cycle. A number of \(-1\) means that the global GAMS option domlim is used. The last number \(i_n\) sets a domain error limit for all cycles \(n, n+1, \dots\).

Example: domlim 0 100 0
The NLP solver in the second cycle is allowed to make up to 100 evaluation errors, while all other cycles must be solved without evaluation errors.

The default is to use the global GAMS domlim option.

epsmip (real): Tolerance on test on monotonic improvement of MIP master problem

This option can be used to relax the test on MIP objective functions. The objective function values of the MIP master problems should form a monotonic worsening curve. This is not the case if the MIP master problems are not solved to optimality. If the options OPTCR or OPTCA are set to a nonzero value, this test is bypassed. If the test fails, DICOPT will fail with a message:

The MIP solution became better after adding integer cuts. Something is wrong. Please check if your model is properly scaled. Also check your big M formulations – the value of M should be relatively small. This error can also occur if you used a MIP solver option file with a nonzero OPTCR or OPTCA setting. In that case you may want to increase the EPSMIP setting using a DICOPT option file.

The value of

\[ \frac{\text{PreviousObj} - \text{CurrentObj}}{1 + |\text{PreviousObj}|} \]

is compared against epsmip. In case the test fails but you want DICOPT to continue anyway, you may want to increase the value of epsmip. The current values used in the test (previous and current MIP objective, epsmip) are printed along with the above message to provide information about how much you should increase epsmip to pass the test. Normally, you should not have to change this value.

Default: 1.0e-6

epsx (real): Tolerance for integer values when loading relaxed solution

This tolerance is used to distinguish integer variables that are set to an integer value by the user, or integer variables that are fractional. See the option relaxed.

Default: 1.0e-3

feaspump (integer): Whether to run the Feasibility Pump

Default: 0

valuemeaning
0 Do not run the Feasibility Pump
1 Run the Feasibility Pump if there are no semicontinuous or semiinteger variables and no special ordered sets
2 Always run the Feasibility Pump

fp_acttol (real): Tolerance on when to consider an equation as active

Default: 1E-6

fp_cutoffdecr (real): Additional relative decrement of cutoff value for the original objective function

Default: 0.1

fp_dumpsubprob (boolean): Whether to dump subproblems (NLPs and MIPs) into GAMS files

Default: 0

fp_iterlimit (integer): Major Iteration limit

Default: maxint

fp_projzerotol (real): Tolerance on when to consider optimal value of projection problem as zero, which may trigger the solution of a Sub-NLP

Default: 1E-6

fp_sollimit (integer): Stop when a number of (improving) solutions has been bound

Default: maxint

fp_stalllimit (integer): Stop when no improving solution has been bound for a number of FP iterations, -1 to disable

Range: [-1, ∞]

Default: 5

fp_subsolverlog (boolean): Whether to show the log of subsolvers

Default: 0

fp_timelimit (real): Time limit

Default: maxdouble

fp_transfercuts (boolean): Whether to transfer cuts from the Feasibility Pump MIP to the DICOPT MIP (all except from the round in which the FP MIP became infeasible)

Default: 1

infbnd (real): Bound to use for unbounded integer variables in integer cuts

Value to use for missing bounds on discrete variables when constructing integer cuts.

Default: 10000

infeasder (integer): Use derivatives of infeasible nonlinear subproblems

This option is to determine whether linearizations of infeasible NLP subproblems are added or not added to the MIP master problem.

Default: 0

valuemeaning
0 No linearizations of infeasible NLP subproblems
This is the default option in which no linearizations are added in the infeasible NLP subproblems. In this case a simple integer cut is added to remove from consideration the 0-1 vector that gave rise to the infeasible NLP. Since this may slow the convergence, it is recommended to reformulate the MINLP with "elastic" constraints (i.e., adding slacks to infeasible constraints and adding a penalty for them in the objective) to ensure that the NLP subproblems are mathematically feasible.
1 Add linearization for infeasible NLP subproblems
This will add linearizations derived from the infeasible NLP subproblem to the master problem. This option is recommended to speed up convergence when the MINLP is known to be convex (i.e. its continuous relaxation is convex). The possibility of cutting-off the global optimum is increased if it is used for a nonconvex MINLP.

maxcycles (integer): Maximum number of cycles

The maximum number of cycles or major iterations performed by DICOPT.

Default: 20

mipiterlim (string): List of iteration limits

mipiterlim \(i_1\) \(i_2\) \(\dots\) \(i_n\) sets an iteration limit on individual MIP master problems. The last number \(i_n\) is valid for all subsequent cycles \(n, n+1, \dots\). A number of \(-1\) indicates that there is no (individual) limit on the corresponding MIP master problem. A global iteration limit is maintained through the GAMS option iterlim.

Example: mipiterlim 10000 -1
The first MIP master problem cannot use more than 10000 iterations, while subsequent MIP master problems are not individually restricted.

Example: mipiterlim 10000
Sets an iteration limit of 10000 on all MIP master problems.

When this option is used it is advised to have the option continue set to its default of 2. The default for this option is not to restrict iteration counts on individual solves of MIP master problems. The default for this option is not to restrict iteration counts on individual solves of MIP master problems.

mipoptfile (string): List of option files for MIP solver

mipoptfile \(s_1\) \(s_2\) \(\dots\) \(s_n\) specifies the option file to be used for the MIP master problems. Several option files can be specified, separated by a blank. If a digit 1 is entered the default option file for the MIP solver in question is being used. The digit 0 indicates that no option file is to be used. The last option file is also used for subsequent MIP master problems.

Example: mipoptfile mip.opt mip2.opt 0
This option will cause the first MIP master problem solver to read the option file mip.opt and the second one to read the option file mip2.opt; subsequent MIP master problem solvers will not use any option file.

Example: mipoptfile 1
This will cause the MIP solver for all MIP subproblems to read a default option file (e.g. cplex.opt, xpress.opt, gurobi.opt etc.).

Option files are located in the current directory (or the project directory when using the IDE). The default is not to use an option file.

mipreslim (string): List of resource limits

mipreslim \(x_1\) \(x_2\) \(\dots\) \(x_n\) sets a resource (time) limit on individual MIP master problems. The last number \(x_n\) is valid for all subsequent cycles \(n, n+1, \dots\). A number \(-1.0\) means that the corresponding MIP master problem is not individually time restricted. A global time limit is maintained through the GAMS option reslim.

Example: mipreslim -1 10000 -1
The MIP master problem in cycle 2 cannot use more than 100 seconds, while subsequent MIP master problems are not individually restricted.

Example: mipreslim 1000
Sets a time limit on all MIP master problems of 1000 seconds.

When this option is used it is advised to have the option continue set to its default of 2. The default for this option is not to restrict individually the time a solver can spent on the MIP master problem.

mipsolver (string): List of MIP solvers

This option specifies with MIP solver to use for the MIP master problems.

Example: mipsolver cplex xpress
This instructs DICOPT to use Cplex for the first MIP and XPRESS for the second and subsequent MIP problems. The last entry may be used for more than one problem.

The names to be used for the solvers are the same as one uses in the GAMS statement OPTION MIP=....;. The default is to use the default MIP solver.
Note that changing from one MIP solver to another can lead to different results, and may cause DICOPT to follow a different path.

nlpiterlim (string): List of iteration limits

nlpiterlim \(i_1\) \(i_2\) \(\dots\) \(i_n\) sets an iteration limit on individual NLP subproblems. The last number \(i_n\) is valid for all subsequent cycles \(n, n+1, \dots\). A number of \(-1\) indicates that there is no (individual) limit on the corresponding NLP subproblem. A global iteration limit is maintained through the GAMS option reslim.

Example: nlpiterlim 1000 -1
The first (relaxed) NLP subproblem cannot use more than 1000 iterations, while subsequent NLP subproblems are not individually restricted.

Example: nlpiterlim 1000
Sets an iteration limit of 1000 on all NLP subproblems.

When this option is used it is advised to have the option continue set to its default of 2. This default does not restrict the amount of iterations an NLP solver can spend on an NLP subproblem, other than the global iteration limit.

nlpoptfile (string): List of option files for NLP solver

nlpoptfile \(s_1\) \(s_2\) \(\dots\) \(s_n\) specifies the option file to be used for the NLP subproblems. Several option files can be specified, separated by a blank. If a digit 1 is entered, the default option file for the NLP solver in question is being used. The digit 0 indicates that no option file is to be used. The last option file is also used for subsequent NLP subproblems.

Example: nlpoptfile nlp.opt nlp2.opt 0
This option will cause the first NLP subproblem solver to read the option file nlp.opt and the second one to read the option file nlp2.opt; subsequent NLP subproblem solvers will not use any option file.

Example: nlpoptfile 1
This will cause the NLP solver for all NLP subproblems to read a default option file (e.g. conopt.opt, minos.opt, snopt.opt etc.).

Option files are located in the current directory (or the project directory when using the IDE). The default is not to use an option file.

nlpreslim (string): List of resource limits

nlpreslim \(x_1\) \(x_2\) \(\dots\) \(x_n\) sets a resource (time) limit on individual NLP subproblems. The last number \(x_n\) is valid for all subsequent cycles \(n, n+1, \dots\). A number \(-1.0\) means that the corresponding NLP subproblem is not individually time restricted. A global time limit is maintained through the GAMS option reslim.

Example: nlpreslim 100 -1
The first (relaxed) NLP subproblem can not use more than 100 seconds, while subsequent NLP subproblems are not individually restricted.

Example: nlpreslim 1000
Sets a time limit of 1000 seconds on all NLP subproblems.

When this option is used it is advised to have the option continue set to its default of 2. This default does not restrict the time an NLP solver can spend on an NLP subproblem (other than the global resource limit).

nlpsolver (string): List of NLP solvers

nlpsolver \(s_1\) \(s_2\) \(\dots\) \(s_n\). This option specifies which NLP solver to use for the NLP subproblems.

Example: nlpsolver conopt minos snopt
tells DICOPT to use CONOPT for the relaxed NLP, MINOS for the second NLP subproblem, and SNOPT for the third and subsequent ones. The last entry is used for more than one subproblem: for all subsequent ones DICOPT will use the last specified solver.

The names to be used for the solvers are the same as those used in the GAMS statementOPTION NLP=....;. The default is to use the default NLP solver. Note that changing from one NLP solver to another can lead to different results, and may cause DICOPT to follow a different path.

nlptracefile (string): Base name of trace files

Name of the files written if the option nlptracelevel is set. Only the stem is needed: if the name is specified as nlptracefile nlptrace, then files of the form nlptrace.001, nlptrace.002, etc. are written. These files contain the settings of the integer variables so that NLP subproblems can be investigated independently of DICOPT.

Default: nlptrace

nlptracelevel (integer): Trace level

This sets the level for NLP tracing, which writes a file for each NLP sub-problem, so that NLP sub-problems can be investigated outside the DICOPT environment. See also the option DICOPTnlptracefile "nlptracefile".
By including a trace file in your original problem and changing it into an MINLP problem, the subproblem will be solved directly by an NLP solver. This option only works if the names in the model (names of variables and equations) are exported by GAMS. This can be accomplished by using the m.dictfile model suffix, as in m.dictfile=1;. In general it is more convenient to use the CONVERT solver to generate isolated NLP models (see section Model Debugging).

Default: 0

valuemeaning
0 No trace info is written
No trace files are written. This is the default.
1 GAMS file with fixed integer variables
A GAMS file for each NLP subproblem is written which fixes the discrete variables.
2 Include levels of continuous variables
As nlptracelevel 1, but in addition level values of the continuous variables are written.
3 Include all levels and marginals
As nlptracelevel 2, but in addition marginal values for the equations and variables are written.

optca (string): List of OPTCA values

optca \(x_1\) \(x_2\) \(\dots\) \(x_n\). The absolute optimality criterion for the MIP master problems. The GAMS option optca is ignored, as, by default, DICOPT wants to solve MIP master problems to optimality. It is possible to stop the MIP solver earlier to allow it to solve a large problem, by specifying a value for optca or optcr in a DICOPT option file. With setting a value for optca, the MIP solver is instructed to stop as soon as the gap between the best possible integer solution and the best found integer solution is less than \(x\), i.e. stop as soon as

\[ | \text{BestFound} - \text{BestPossible} | \le x \]


It is possible to specify a different optca value for each cycle. The last number \(x_n\) is valid for all subsequent cycles \(n, n+1, \dots\).

Example: optca 10
Stop the search in all MIP problems as soon as the absolute gap is less than 10.

Example: optca 0 10 0
Sets a nonzero optca value of 10 for cycle 2, while all other MIP master problems are solved to optimality.

The default is zero.

optcr (string): List of OPTCR values

optcr \(x_1\) \(x_2\) \(\dots\) \(x_n\). The relative optimality criterion for the MIP master problems. The GAMS option optcr is ignored, as by default DICOPT wants to solve MIP master problems to optimality. To allow it to solve a large problem it is possible to stop the MIP solver earlier by specifying a value for optca or optcr in a DICOPT option file. With setting a value for optcr, the MIP solver is instructed to stop as soon as the relative gap between the best possible integer solution and the best found integer solution is less than \(x\), i.e., stop as soon as

\[ \frac{ | \text{BestFound} - \text{BestPossible} | }{| \text{BestPossible} | }\le x \]


Note that the relative gap cannot be evaluated if the best possible integer solution is zero. In these cases the absolute optimality criterion optca can be used. It is possible to specify a different optcr value for each cycle. The last number \(x_n\) is valid for all subsequent cycles \(n, n+1, \dots\).

Example: optcr 0.1
Stop the search in all the MIP problems as soon as the relative gap is smaller than 10%.

Example: optcr 0 0.01 0
Sets a nonzero optcr value of 1% for cycle 2, while all other MIP master problems are solved to optimality.

The default is zero.

relaxed (integer): How to start DICOPT

In some cases it may be possible to use a known configuration of the discrete variables. Some users have very difficult problems, where the relaxed problem cannot be solved but where NLP sub-problems with the integer variables fixed are much easier. If a reasonable integer configuration is known in advance in theses cases we can bypass the relaxed NLP and tell DICOPT to directly start with this integer configuration. The integer variables need to be specified by the user before the solve statement by assigning values to the levels, as in Y.L(I) = INITVAL(I);.

Default: 1

valuemeaning
0 Start with all integers fixed to the starting value
The first NLP sub-problem will be executed with all integer variables fixed to the values specified by the user. If you don't assign a value to an integer variable,it will retain it's current value, which is zero by default
1 Start with relaxed NLP
The first NLP problem is the relaxed NLP problem: all integer variables are relaxed between their bounds. This is the default.
2 Start with mixture of fixed and relaxed integers
The first NLP subproblem will be executed with some variables fixed and some relaxed. The program distinguishes the fixed from the relaxed variables by comparing the initial values against the bounds and the tolerance allowed EPSX. EPSX has a default value of 1.e-3. This can be changed through the option file.

solvelink (integer): Solvelink for NLP and MIP subsolver

This option defines the solvelink used for the NLP and MIP subsolver.

Default: 5

valuemeaning
1 Call NLP and MIP solver via script
2 Call NLP and MIP solver via module
5 Call NLP and MIP solver in memory

stop (integer): Stopping criterion

This option defines the stopping criterion to be used. The search is always stopped when the (minor) iteration limit (the iterlim option), the resource limit (the reslim option), or the major iteration limit (see maxcycles) is hit or when the MIP master problem becomes infeasible.
Note: In general a higher number stops earlier, although in some cases stopping rule 2 may terminate the search earlier than rule 1. Section Modeling shows some experiments with these stopping criteria.

Default: 2

valuemeaning
0 Stop on maxcycles
Do not stop unless an iteration limit, resource limit, or major iteration limit is hit or an infeasible MIP master problem becomes infeasible. This option can be used to verify that DICOPT does not stop too early when using one of the other stopping rules. In general it should not be used on production runs, as in general DICOPT will often find the optimal solution using one of the more optimistic stopping rules. Do not stop unless an iteration limit, resource limit, or major iteration limit is hit or an infeasible MIP master problem becomes infeasible. This option can be used to verify that DICOPT does not stop too early when using one of the other stopping rules. In general it should not be used on production runs, as in general DICOPT will find often the optimal solution using one of the more optimistic stopping rules.
1 Stop on crossover
Stop as soon as the bound defined by the objective of the last MIP master problem is worse than the best NLP solution found (a 'crossover' occurred). For convex problems this gives a global solution, provided the weights are large enough. This stopping criterion should only be used if it is known or it is very likely that the nonlinear functions are convex. In the case of non-convex problems the bounds of the MIP master problem are not rigorous. Therefore, the global optimum can be cut off with the setting stop 1.
2 Stop on worsening
Stop as soon as the NLP subproblems stop improving. This 'worsening' criterion is a heuristic. For non-convex problems in which valid bounds can not be obtained the heuristic often works very well. Even on convex problems, in many cases it terminates the search very early while providing an optimal or a very good integer solution. The criterion is not checked before major iteration three.
3 Stop on crossover or worsening
Stop as soon as a crossover occurs or when the NLP subproblems start to worsen. (This is a combination of 1 and 2).

usexinit (boolean): Use the user initial point as starting point for all NLP solves

Default: 0

weight (real): Penalty parameter

The value of the penalty coefficients.

Default: 1000

DICOPT Output

DICOPT generates lots of output on the screen. DICOPT itself and also the NLP and MIP solvers that handle the sub-problems write messages to the screen. The most important part is the last part of the screen output.

In this section we will discuss the output DICOPT writes to the screen and the listing file using the model procsel.gms (this model is part of the GAMS model library). A DICOPT log is written and the reason why DICOPT terminated is explanied.

--- DICOPT: Checking convergence
--- DICOPT: Search stopped on worsening of NLP subproblems
--- DICOPT: Log File:
 Major Major     Objective    CPU time  Itera- Evaluation Solver
 Step  Iter       Function     (Sec)    tions   Errors
  NLP    1         5.35021      0.05        8      0      conopt
  MIP    1         2.48869      0.28        7      0      cplex
  NLP    2         1.72097<     0.00        3      0      conopt
  MIP    2         2.17864      0.22       10      0      cplex
  NLP    3         1.92310<     0.00        3      0      conopt
  MIP    3         1.42129      0.22       12      0      cplex
  NLP    4         1.41100      0.00        8      0      conopt
--- DICOPT: Terminating...
--- DICOPT: Stopped on NLP worsening

      The search was stopped because the objective function
      of the NLP subproblems started to deteriorate.

--- DICOPT: Best integer solution found: 1.923099
--- Restarting execution
--- PROCSEL.GMS(98) 0 Mb
--- Reading solution for model process
*** Status: Normal completion

Notice that the integer solutions are provided by the NLP's except for major iteration one (the first NLP is the relaxed NLP). For all NLP's except the relaxed one the binary variables are fixed, according to a pattern determined by the previous MIP which operates on a linearized model. The integer solutions marked with a ' \(<\)' are an improvement. We see that the NLP in cycle 4 starts to deteriorate, and DICOPT stops based on its default stopping rule.

Note that if the criterion stop 1 had been used the search would have been terminated at iteration 3. The reason is that the upper bound to the profit predicted by the MIP (1.42129) exceeds the best current NLP solution (1.9231). Since it can be shown that the MINLP involves convex nonlinear functions, 1.9231 is the global optimum and the criterion stop 1 is rigorous.

A similar output can be found in the listing file:

               S O L V E      S U M M A R Y

     MODEL   process             OBJECTIVE  pr
     TYPE    MINLP               DIRECTION  MAXIMIZE
     SOLVER  DICOPT              FROM LINE  98

**** SOLVER STATUS     1 NORMAL COMPLETION
**** MODEL STATUS      8 INTEGER SOLUTION
**** OBJECTIVE VALUE                1.9231

 RESOURCE USAGE, LIMIT          0.771      1000.000
 ITERATION COUNT, LIMIT        51         10000
 EVALUATION ERRORS              0             0

--- DICOPT: Stopped on NLP worsening

      The search was stopped because the objective function
      of the NLP subproblems started to deteriorate.

 ------------------------------------------------------------------
 Dicopt2x-C    Jul  4, 2001 WIN.DI.DI 20.1 026.020.039.WAT
 ------------------------------------------------------------------

     Aldo Vecchietti and Ignacio E. Grossmann
     Engineering Design Research Center
     Carnegie Mellon University
     Pittsburgh, Pennsylvania 15213

     Erwin Kalvelagen
     GAMS Development Corp.
     1217 Potomac Street, N.W.
     Washington DC 20007
 ------------------------------------------------------------------
 DICOPT Log File
 ------------------------------------------------------------------
 Major Major     Objective    CPU time  Itera- Evaluation Solver
 Step  Iter       Function     (Sec)    tions   Errors
  NLP    1         5.35021      0.05        8      0      conopt
  MIP    1         2.48869      0.28        7      0      cplex
  NLP    2         1.72097<     0.00        3      0      conopt
  MIP    2         2.17864      0.22       10      0      cplex
  NLP    3         1.92310<     0.00        3      0      conopt
  MIP    3         1.42129      0.22       12      0      cplex
  NLP    4         1.41100      0.00        8      0      conopt
 ------------------------------------------------------------------
   Total solver times :  NLP =     0.05   MIP =     0.72
   Perc. of total     :  NLP =     6.59   MIP =    93.41
 ------------------------------------------------------------------

In case the DICOPT run was not successful, or if one of the subproblems could not be solved, the listing file will contain all the status information provided by the solvers of the subproblems. For each iteration the configuration of the binary variables will also be printed. This extra information can also be requested via the GAMS option:

    option sysout = on ;

Special Notes

This section covers some special topics of interest to users of DICOPT.

Stopping Rule

Although the default stopping rule behaves quite well in practice there some cases where it terminates too early. In this section we discuss the use of the stopping criteria.

When we run the example procsel.gms with stopping criterion 0, we see the following DICOPT log:

--- DICOPT: Starting major iteration 10
--- DICOPT: Search terminated: infeasible MIP master problem
--- DICOPT: Log File:
 Major Major     Objective    CPU time  Itera- Evaluation Solver
 Step  Iter       Function     (Sec)    tions   Errors
  NLP    1         5.35021      0.06        8      0      conopt
  MIP    1         2.48869      0.16        7      0      cplex
  NLP    2         1.72097<     0.00        3      0      conopt
  MIP    2         2.17864      0.10       10      0      cplex
  NLP    3         1.92310<     0.00        3      0      conopt
  MIP    3         1.42129      0.11       12      0      cplex
  NLP    4         1.41100      0.00        8      0      conopt
  MIP    4         0.00000      0.22       23      0      cplex
  NLP    5         0.00000      0.00        3      0      conopt
  MIP    5        -0.27778      0.16       22      0      cplex
  NLP    6        -0.27778      0.00        3      0      conopt
  MIP    6        -1.00000      0.16       21      0      cplex
  NLP    7        -1.00000      0.00        3      0      conopt
  MIP    7        -1.50000      0.22       16      0      cplex
  NLP    8        -1.50000      0.00        3      0      conopt
  MIP    8        -2.50000      0.11       16      0      cplex
  NLP    9        -2.50000      0.00        3      0      conopt
  MIP    9        *Infeas*      0.11        0      0      cplex
--- DICOPT: Terminating...
--- DICOPT: Stopped on infeasible MIP

      The search was stopped because the last MIP problem
      was infeasible. DICOPT will not be able to find
      a better integer solution.

--- DICOPT: Best integer solution found: 1.923099
--- Restarting execution
--- PROCSEL.GMS(98) 0 Mb
--- Reading solution for model process
*** Status: Normal completion

This example shows some behavioral features that are not uncommon for other MINLP models. First, DICOPT often finds the best integer solution in the first few major iterations. Second, in many cases as soon as the NLP's start to give worse integer solution no better integer solution will be found. This observation is the motivation to make stopping option 2, where DICOPT stops as soon as the NLP's start to deteriorate, the default stopping rule. In this example DICOPT would have stopped in major iteration 4 (you can verify this in the previous section). In many cases this will give the best integer solution. For this problem, DICOPT has indeed found the global optimum.

Based on experience with other models, we find that the default stopping rule (stop when the NLP becomes worse) performs well in practice. In many cases it finds the global optimum solution for both convex and non-convex problems. In some cases, however, it may provide a sub-optimal solution. In those cases where you want more reassurance that no good integer solutions are missed you can use one of the other stopping rules.

Changing the MIP or NLP solver can change the path that DICOPT follows, since the sub-problems may have non-unique solutions. The optimum stopping rule for a particular problem depends on the MIP and NLP solvers used.

The bounds of the MIP master problem are not rigorous in the case of non-convex problems. Therefore, the global optimum can be cut-off with stop 1. However, this option is the best stopping criterion for convex problems.

Solving the NLP Problems

Using a combination of NLP solvers has been found effective in cases where the relaxed NLP and/or the other NLP sub-problems are very difficult. For example, MINOS has many more difficulties to establish if a model is infeasible, so one would like to use CONOPT for NLP subproblems that are either infeasible or barely feasible. The nlpsolver option can be used to specify the NLP solver to be used for each iteration.

Infeasible NLP sub-problems can be problematic for DICOPT Those subproblems cannot be used to form a new linearization. Effectively only the current integer configuration is excluded from further consideration by adding appropriate integer cuts, but otherwise an infeasible NLP sub-problem provides no useful information to be used by the DICOPT algorithm. If your model shows many infeasible NLP sub-problems you can try to use the infeasder option. Otherwise a strategy that can help is to introduce explicit slack variables and add them with a penalty to the objective function.

Assume your model is of the form:

\[ \begin{array}{rl} \min\> & f(x,y) \\ & g(x,y) \sim b \\ & \ell \le x \le u \\ & y \in \{0,1\} \end{array} \]

where \(\sim\) is a vector of relational operators \(\{\le,=,\ge\}\). \(x\) are continuous variables and \(y\) are the binary variables. If many of the NLP subproblems are infeasible, we can try the following elastic formulation:

\[ \begin{array}{rl} \min\> & f(x,y) + M \sum_i (s_i^+ + s_i^-) \\ & y = y^B + s^+ - s^- \\ & g(x,y) \sim b \\ & \ell \le x \le u \\ & 0 \le y \le 1 \\ & 0 \le s^+,s^- \le 1 \\ & y^B \in \{0,1\} \end{array} \]

I.e., the variables \(y\) are relaxed to be continuous with bounds \([0,1]\), and binary variables \(y^B\) are introduced that are related to the variables \(y\) through a set of the slack variables \(s^+, s^-\). The slack variables are added to the objective with a penalty parameter \(M\). The choice of a value for \(M\) depends on the size of \(f(x,y)\), on the behavior of the model, etc. Typical values are 100 or 1000.

Solving the MIP Master Problems

MIP master problems may become expensive to solve when there are many discrete variables. One of the first things to try is to see if a different MIP solver can solve your particular problems more efficiently.

Different formulations can have dramatic impact on the performance of MIP solvers. Therefore it is advised to try out several alternative formulations. The use of priorities can have a big impact on some models. It is possible to specify a nonzero value for OPTCA and OPTCR in order to prevent the MIP solver from spending an unacceptable long time proving optimality of MIP master problems.

If the MIP master problem is infeasible the DICOPT solver will terminate. In this case you may want to try the same reformulation discussed in the previous paragraph.

Feasibility Pump

The feasibility pump is similar to the Outer-approximation, but its objective is to completely focus on finding good feasible solutions rather than optimal ones. The main idea of this algorithm is to decompose the original mathematical programming problem in two parts: integer feasibility and constraint feasibility. By solving an MIP subproblem its solution is an integer feasible solution, which may violate the constraints; and by solving a continuous relaxation of the original MINLP (NLP subproblem) the solution is constraint feasible but might not be integral. By minimizing in successive iterations the distance between these two types of solutions it is expected to achieve a solution that is both constraint and integral feasible.

The feasibility pump can be used as a standalone solver for convex MINLP problems. This is achieved by iteratively applying the method, while including a bound to the objective function. This bound is obtained by the best known solution and an epsilon improvement. This will result in the global optimum of a convex MINLP [47]. The drawback of this algorithm is that it may require many iterations, since each time the objective function is restricted to improve only by epsilon.

In DICOPT, the feasibility pump can be applied before the Outer-approximation method by setting option feaspump. In the feasibility pump, large improvements in the objective function are enforced at each iteration (option fp_cutoffdecr). After the method finishes, all the cuts and the best known solution are passed to the Outer-approximation method to prove optimality. More details on the implementation of the feasibility pump in DICOPT can be found in [36].

Model Debugging

In this paragraph we discuss a few techniques that can be helpful in debugging your MINLP model.

  • Start with solving the model as an RMINLP model. Make sure this model solves reliably before solving it as a proper MINLP model. If you have access to different NLP solvers, make sure the RMINLP model solves smoothly with all NLP solvers. CONOPT, especially, can generate useful diagnostics such as Jacobian elements (i.e. matrix elements) that become too large.
  • Try different NLP and MIP solvers on the subproblems. Example: use the GAMS statement OPTION NLP=KNITRO; to solve all NLP subproblem using the solver KNITRO.
  • The GAMS option statement OPTION SYSOUT = ON; can generate extra solver information that can be helpful for diagnosing problems.
  • If many of the NLP subproblems are infeasible, add slacks as described in section Solving the NLP Problems.
  • Run DICOPT in pedantic mode by using the DICOPT option: CONTINUE 0. Make sure all NLP subproblems solve to optimality.
  • Don't allow any nonlinear function evaluation errors, i.e. keep the DOMLIM limit at zero. See the discussion on DOMLIM in section The OPTION Statement.
  • If you have access to another MINLP solver such as AlphaECP, Bonmin, or SBB or even global solvers like Antigone or BARON, try to use a different solver on your model. To select another solver (here SBB) use the following GAMS option statement: OPTION MINLP=SBB;.
  • Individual NLP or MIP subproblems can be extracted from the MINLP by using the CONVERT solver, which will write a model in scalar GAMS notation that can then be solved using any GAMS NLP or MIP solver. E.g., to generate the second NLP subproblem, you can use the following DICOPT option: NLPSOLVER CONOPT CONVERT. The model will be written to the file GAMS.GMS. A disadvantage of this technique is that some precision is lost due to the fact that files are being written in plain ASCII. The advantage is that you can visually inspect these files and look for possible problems such as poor scaling.