SHOT (**S**upporting **H**yperplane **O**ptimization **T**oolkit) is a deterministic solver for mixed-integer nonlinear programming problems (MINLPs).

Originally, SHOT was intended for convex MINLP problems only, but now also has functionality to solve nonconvex MINLP problems as a heuristic method without providing any guarantees of global optimality. SHOT can solve certain nonconvex problem types to global optimality as well.

SHOT has mainly been developed by Andreas Lundell (Åbo Akademi University, Finland) and Jan Kronqvist (Imperial College London, UK). For more details, see [169, 165, 150, 151].

SHOT supports GAMS equations that use the following intrinsic functions: abs, cos, cvPower, div, exp, log, log10, log2, pi, power, rPower, sin, sqr, sqrt, vcPower.

# Algorithm

SHOT is based on iteratively creating a tighter polyhedral approximation of the nonlinear feasible set by generating supporting hyperplanes or cutting planes. These linearized problems are then solved with a mixed-integer linear programming (MIP) solver. GAMS/SHOT uses CPLEX, if a GAMS/CPLEX license is available, and otherwise CBC. Users with a license from Gurobi can also select Gurobi as MIP solver on Linux and Windows. If CPLEX or Gurobi is used, the subproblems can also include quadratic and bilinear nonlinearities directly.

The solution to the outer approximation problem provides a dual bound (i.e., a lower bound when solving a minimization problem) to the optimal value of the original problem if it is convex. If the problem is nonconvex, convergence to the global optimal solution cannot be guaranteed (but might be achieved for certain classes of problems, cf. [165]).

To get a primal bound (i.e., an upper bound when solving a minimization problem) on the optimal value, SHOT utilizes the following heuristics:

- Solving nonlinear programming (NLP) problems where the integer variables have been fixed to valid values. This is done by calling an NLP solver, which is either Ipopt or one of the GAMS NLP solvers.
- By checking solutions from the MIP solver's solution pool for points that fulfill also the nonlinear constraints in the original MINLP problem.
- By performing root searches.

When a termination criterion like a tolerance on the relative or absolute objective gap or a time limit is fulfilled, SHOT terminates and returns the current primal solution to GAMS. If the original problem is convex and SHOT could close the objective gap, then this is a global optimal solution to the problem. If it is nonconvex, then there is normally no guarantee that such a solution can be found. However, SHOT will always, in addition to a primal solution, return a valid dual bound on the solution in model attribute objest, unless Model.Convexity.AssumeConvex has been enabled.

# Usage

The following statement can be used inside your GAMS program to specify using SHOT

Option MINLP = SHOT; { or MIQCP }

The above statement should appear before the Solve statement. If SHOT was specified as the default MINLP or MIQCP solver during GAMS installation, the above statement is not necessary.

## Specification of SHOT Options

GAMS/SHOT supports the GAMS parameters reslim, iterlim, nodlim, optcr, optca, cutoff, and threads.

Options can be specified by a SHOT options file. A SHOT options file consists of one option or comment per line. An asterik (`*`

) at the beginning of a line causes the entire line to be ignored. Otherwise, the line will be interpreted as an option name and value separated by an equal sign (`=`

) and any amount of white space (blanks or tabs).

A small example for a shot.opt file is:

Dual.CutStrategy = 1 Dual.MIP.Solver = 2 Output.Console.DualSolver.Show = true

It causes GAMS/SHOT to use the Extended Cutting Plane (ECP) method instead of the Extended Supporting Hyperplane (EHP) method, changes the MIP solver to CBC, and enables showing the output of the solver that computes dual bounds (typically the MIP solver).

- Attention
- SHOT requires options to be specified using exactly the names as specified in the documentation. That is, also casing matters.

# List of SHOT Options

In the following, we give a detailed list of all SHOT options.

## Dual strategy

Option | Description | Default |
---|---|---|

Dual.CutStrategy | Dual cut strategy`0` : ESH`1` : ECP | `0` |

Dual.ESH.InteriorPoint.CuttingPlane.ConstraintSelectionFactor | The fraction of violated constraints to generate cutting planes for Range: [ `0` , `1` ] | `0.25` |

Dual.ESH.InteriorPoint.CuttingPlane.IterationLimit | Iteration limit for minimax cutting plane solver Range: { `1` , ..., ∞} | `100` |

Dual.ESH.InteriorPoint.CuttingPlane.IterationLimitSubsolver | Iteration limit for minimization subsolver | `100` |

Dual.ESH.InteriorPoint.CuttingPlane.Reuse | Reuse valid cutting planes in main dual model | `0` |

Dual.ESH.InteriorPoint.CuttingPlane.TerminationToleranceAbs | Absolute termination tolerance between LP and linesearch objective | `1` |

Dual.ESH.InteriorPoint.CuttingPlane.TerminationToleranceRel | Relative termination tolerance between LP and linesearch objective | `1` |

Dual.ESH.InteriorPoint.CuttingPlane.TimeLimit | Time limit for minimax solver | `10` |

Dual.ESH.InteriorPoint.MinimaxObjectiveLowerBound | Lower bound for minimax objective variable Range: [-∞, `0` ] | `-1e+12` |

Dual.ESH.InteriorPoint.MinimaxObjectiveUpperBound | Upper bound for minimax objective variable Range: [-∞, ∞] | `0.1` |

Dual.ESH.InteriorPoint.UsePrimalSolution | Utilize primal solution as interior point`0` : No`1` : Add as new`2` : Replace old`3` : Use avarage | `1` |

Dual.ESH.Rootsearch.ConstraintTolerance | Constraint tolerance for when not to add individual hyperplanes | `1e-08` |

Dual.ESH.Rootsearch.UniqueConstraints | Allow only one hyperplane per constraint per iteration | `0` |

Dual.HyperplaneCuts.ConstraintSelectionFactor | The fraction of violated constraints to generate supporting hyperplanes / cutting planes for Range: [ `0` , `1` ] | `0.5` |

Dual.HyperplaneCuts.Delay | Add hyperplane cuts to model only after optimal MIP solution | `1` |

Dual.HyperplaneCuts.MaxConstraintFactor | Rootsearch performed on constraints with values larger than this factor times the maximum value Range: [ `1e-06` , `1` ] | `0.1` |

Dual.HyperplaneCuts.MaxPerIteration | Maximal number of hyperplanes to add per iteration | `200` |

Dual.HyperplaneCuts.ObjectiveRootSearch | When to use the objective root search`0` : Always`1` : IfConvex`2` : Never | `1` |

Dual.HyperplaneCuts.UseIntegerCuts | Add integer cuts for infeasible integer-combinations for binary problems | `0` |

Dual.MIP.CutOff.InitialValue | Initial cutoff value to use Range: [-∞, ∞] | `GAMS cutoff` |

Dual.MIP.CutOff.Tolerance | An extra tolerance for the objective cutoff value (to prevent infeasible subproblems) Range: [-∞, ∞] | `1e-05` |

Dual.MIP.CutOff.UseInitialValue | Use the initial cutoff value | `1, if cutoff is set` |

Dual.MIP.InfeasibilityRepair.IntegerCuts | Allow feasibility repair of integer cuts | `1` |

Dual.MIP.InfeasibilityRepair.IterationLimit | Max number of infeasible problems repaired without primal objective value improvement | `100` |

Dual.MIP.InfeasibilityRepair.TimeLimit | Time limit when reparing infeasible problem | `10` |

Dual.MIP.NodeLimit | Node limit to use for MIP solver in single-tree strategy | `GAMS nodlim` |

Dual.MIP.NumberOfThreads | Number of threads to use in MIP solver: 0: Automatic Range: { `0` , ..., `999` } | `GAMS threads` |

Dual.MIP.OptimalityTolerance | The reduced-cost tolerance for optimality in the MIP solver Range: [ `1e-09` , `0.01` ] | `1e-06` |

Dual.MIP.Presolve.Frequency | When to call the MIP presolve`0` : Never`1` : Once`2` : Always | `1` |

Dual.MIP.Presolve.RemoveRedundantConstraints | Remove redundant constraints (as determined by presolve) | `0` |

Dual.MIP.Presolve.UpdateObtainedBounds | Update bounds (from presolve) to the MIP model | `1` |

Dual.MIP.SolutionLimit.ForceOptimal.Iteration | Iterations without dual bound updates for forcing optimal MIP solution | `10000` |

Dual.MIP.SolutionLimit.ForceOptimal.Time | Time (s) without dual bound updates for forcing optimal MIP solution | `1000` |

Dual.MIP.SolutionLimit.IncreaseIterations | Max number of iterations between MIP solution limit increases | `50` |

Dual.MIP.SolutionLimit.Initial | Initial MIP solution limit Range: { `1` , ..., ∞} | `1` |

Dual.MIP.SolutionLimit.UpdateTolerance | The constraint tolerance for when to update MIP solution limit | `0.001` |

Dual.MIP.SolutionPool.Capacity | The maximum number of solutions in the solution pool | `100` |

Dual.MIP.Solver | Which MIP solver to use`0` : Cplex`1` : Gurobi (not available on Mac OS X)`2` : Cbc | `Cplex, if licensed, otherwise Cbc` |

Dual.MIP.UpdateObjectiveBounds | Update nonlinear objective variable bounds to primal/dual bounds | `0` |

Dual.ReductionCut.MaxIterations | Max number of primal cut reduction without primal improvement | `5` |

Dual.ReductionCut.ReductionFactor | The factor used to reduce the cutoff value Range: [ `0` , `1` ] | `0.001` |

Dual.Relaxation.Frequency | The frequency to solve an LP problem: 0: Disable | `0` |

Dual.Relaxation.IterationLimit | The max number of relaxed LP problems to solve initially | `200` |

Dual.Relaxation.MaxLazyConstraints | Max number of lazy constraints to add in relaxed solutions in single-tree strategy | `0` |

Dual.Relaxation.TerminationTolerance | Time limit (s) when solving LP problems initially Range: [-∞, ∞] | `0.5` |

Dual.Relaxation.TimeLimit | Time limit (s) when solving LP problems initially | `30` |

Dual.Relaxation.Use | Initially solve continuous dual relaxations | `1` |

Dual.TreeStrategy | The main strategy to use`0` : Multi-tree`1` : Single-tree | `1` |

## Optimization model

## Solver output

## Primal heuristics

## Strategy

Option | Description | Default |
---|---|---|

Strategy.UseRecommendedSettings | Modifies some settings to their recommended values based on the strategy | `1` |

## Subsolver functionality

## Termination

Option | Description | Default |
---|---|---|

Termination.ConstraintTolerance | Termination tolerance for nonlinear constraints | `1e-08` |

Termination.DualStagnation.ConstraintTolerance | Min absolute difference between max nonlinear constraint errors in subsequent iterations for termination | `1e-06` |

Termination.DualStagnation.IterationLimit | Max number of iterations without significant dual objective value improvement | `50` |

Termination.IterationLimit | Iteration limit for main strategy Range: { `1` , ..., ∞} | `GAMS iterlim` |

Termination.ObjectiveConstraintTolerance | Termination tolerance for the nonlinear objective constraint | `1e-08` |

Termination.ObjectiveGap.Absolute | Absolute gap termination tolerance for objective function | `GAMS optca` |

Termination.ObjectiveGap.Relative | Relative gap termination tolerance for objective function | `GAMS optcr` |

Termination.PrimalStagnation.IterationLimit | Max number of iterations without significant primal objective value improvement | `50` |

Termination.TimeLimit | Time limit (s) for solver | `GAMS reslim` |