SHOT (Supporting Hyperplane Optimization Toolkit) 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 [167, 163, 148, 149].
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. 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. [163]).
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
These settings control the various functionality of the dual strategy in SHOT, i.e., the polyhedral outer approximation utilizing the ESH or ECP algorithms.
Option | Description | Default |
---|---|---|
Dual.CutStrategy | Dual cut strategy 0: ESH 1: ECP | 0 |
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 Range: {0, ..., ∞} | 100 |
Dual.ESH.InteriorPoint.UsePrimalSolution | Utilize primal solution as interior point 0: No 1: Add as new 2: Replace old 3: Use avarage | 1 |
Dual.HyperplaneCuts.MaxPerIteration | Maximal number of hyperplanes to add per iteration Range: {0, ..., ∞} | 200 |
Dual.HyperplaneCuts.ObjectiveRootSearch | When to use the objective root search 0: Always 1: IfConvex 2: Never | 1 |
Dual.MIP.InfeasibilityRepair.IterationLimit | Max number of infeasible problems repaired without primal objective value improvement Range: {0, ..., ∞} | 100 |
Dual.MIP.NumberOfThreads | Number of threads to use in MIP solver: 0: Automatic Range: {0, ..., 999} | GAMS threads |
Dual.MIP.Presolve.Frequency | When to call the MIP presolve 0: Never 1: Once 2: Always | 1 |
Dual.MIP.SolutionLimit.ForceOptimal.Iteration | Iterations without dual bound updates for forcing optimal MIP solution Range: {0, ..., ∞} | 10000 |
Dual.MIP.SolutionLimit.IncreaseIterations | Max number of iterations between MIP solution limit increases Range: {0, ..., ∞} | 50 |
Dual.MIP.SolutionLimit.Initial | Initial MIP solution limit Range: {1, ..., ∞} | 1 |
Dual.MIP.SolutionPool.Capacity | The maximum number of solutions in the solution pool Range: {0, ..., ∞} | 100 |
Dual.MIP.Solver | Which MIP solver to use 0: Cplex 1: Gurobi 2: Cbc | Cplex, if licensed, otherwise Cbc |
Dual.ReductionCut.MaxIterations | Max number of primal cut reduction without primal improvement Range: {0, ..., ∞} | 5 |
Dual.Relaxation.Frequency | The frequency to solve an LP problem: 0: Disable Range: {0, ..., ∞} | 0 |
Dual.Relaxation.IterationLimit | The max number of relaxed LP problems to solve initially Range: {0, ..., ∞} | 200 |
Dual.Relaxation.MaxLazyConstraints | Max number of lazy constraints to add in relaxed solutions in single-tree strategy Range: {0, ..., ∞} | 0 |
Dual.TreeStrategy | The main strategy to use 0: Multi-tree 1: Single-tree | 1 |
Dual.ESH.InteriorPoint.CuttingPlane.ConstraintSelectionFactor | The fraction of violated constraints to generate cutting planes for Range: [0, 1] | 0.25 |
Dual.ESH.InteriorPoint.CuttingPlane.TerminationToleranceAbs | Absolute termination tolerance between LP and linesearch objective Range: [0, ∞] | 1 |
Dual.ESH.InteriorPoint.CuttingPlane.TerminationToleranceRel | Relative termination tolerance between LP and linesearch objective Range: [0, ∞] | 1 |
Dual.ESH.InteriorPoint.CuttingPlane.TimeLimit | Time limit for minimax solver Range: [0, ∞] | 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: real | 0.1 |
Dual.ESH.Rootsearch.ConstraintTolerance | Constraint tolerance for when not to add individual hyperplanes Range: [0, ∞] | 1e-08 |
Dual.HyperplaneCuts.ConstraintSelectionFactor | The fraction of violated constraints to generate supporting hyperplanes / cutting planes for Range: [0, 1] | 0.5 |
Dual.HyperplaneCuts.MaxConstraintFactor | Rootsearch performed on constraints with values larger than this factor times the maximum value Range: [1e-06, 1] | 0.1 |
Dual.MIP.CutOff.InitialValue | Initial cutoff value to use Range: real | GAMS cutoff |
Dual.MIP.CutOff.Tolerance | An extra tolerance for the objective cutoff value (to prevent infeasible subproblems) Range: real | 1e-05 |
Dual.MIP.InfeasibilityRepair.TimeLimit | Time limit when reparing infeasible problem Range: [0, ∞] | 10 |
Dual.MIP.NodeLimit | Node limit to use for MIP solver in single-tree strategy Range: [0, ∞] | GAMS nodlim |
Dual.MIP.OptimalityTolerance | The reduced-cost tolerance for optimality in the MIP solver Range: [1e-09, 0.01] | 1e-06 |
Dual.MIP.SolutionLimit.ForceOptimal.Time | Time (s) without dual bound updates for forcing optimal MIP solution Range: [0, ∞] | 1000 |
Dual.MIP.SolutionLimit.UpdateTolerance | The constraint tolerance for when to update MIP solution limit Range: [0, ∞] | 0.001 |
Dual.ReductionCut.ReductionFactor | The factor used to reduce the cutoff value Range: [0, 1] | 0.001 |
Dual.Relaxation.TerminationTolerance | Time limit (s) when solving LP problems initially Range: real | 0.5 |
Dual.Relaxation.TimeLimit | Time limit (s) when solving LP problems initially Range: [0, ∞] | 30 |
Dual.ESH.InteriorPoint.CuttingPlane.Reuse | Reuse valid cutting planes in main dual model Range: boolean | 0 |
Dual.ESH.Rootsearch.UniqueConstraints | Allow only one hyperplane per constraint per iteration Range: boolean | 0 |
Dual.HyperplaneCuts.Delay | Add hyperplane cuts to model only after optimal MIP solution Range: boolean | 1 |
Dual.HyperplaneCuts.UseIntegerCuts | Add integer cuts for infeasible integer-combinations for binary problems Range: boolean | 0 |
Dual.MIP.CutOff.UseInitialValue | Use the initial cutoff value Range: boolean | 1, if cutoff is set |
Dual.MIP.InfeasibilityRepair.IntegerCuts | Allow feasibility repair of integer cuts Range: boolean | 1 |
Dual.MIP.Presolve.RemoveRedundantConstraints | Remove redundant constraints (as determined by presolve) Range: boolean | 0 |
Dual.MIP.Presolve.UpdateObtainedBounds | Update bounds (from presolve) to the MIP model Range: boolean | 1 |
Dual.MIP.UpdateObjectiveBounds | Update nonlinear objective variable bounds to primal/dual bounds Range: boolean | 0 |
Dual.Relaxation.Use | Initially solve continuous dual relaxations Range: boolean | 1 |
Optimization model
These settings control various aspects of SHOT's representation for and handling of the provided optimization model.
Solver output
These settings control how much and what output is shown to the user from the solver.
Primal heuristics
These settings control the primal heuristics used in SHOT.
Strategy
Overall strategy parameters used in SHOT.
Option | Description | Default |
---|---|---|
Strategy.UseRecommendedSettings | Modifies some settings to their recommended values based on the strategy Range: boolean | 1 |
Subsolver functionality
These settings allow for more direct control of the different subsolvers utilized in SHOT.
Termination
These settings control when SHOT will terminate the solution process.
Option | Description | Default |
---|---|---|
Termination.DualStagnation.IterationLimit | Max number of iterations without significant dual objective value improvement Range: {0, ..., ∞} | 50 |
Termination.IterationLimit | Iteration limit for main strategy Range: {1, ..., ∞} | GAMS iterlim |
Termination.PrimalStagnation.IterationLimit | Max number of iterations without significant primal objective value improvement Range: {0, ..., ∞} | 50 |
Termination.ConstraintTolerance | Termination tolerance for nonlinear constraints Range: [0, ∞] | 1e-08 |
Termination.DualStagnation.ConstraintTolerance | Min absolute difference between max nonlinear constraint errors in subsequent iterations for termination Range: [0, ∞] | 1e-06 |
Termination.ObjectiveConstraintTolerance | Termination tolerance for the nonlinear objective constraint Range: [0, ∞] | 1e-08 |
Termination.ObjectiveGap.Absolute | Absolute gap termination tolerance for objective function Range: [0, ∞] | GAMS optca |
Termination.ObjectiveGap.Relative | Relative gap termination tolerance for objective function Range: [0, ∞] | GAMS optcr |
Termination.TimeLimit | Time limit (s) for solver Range: [0, ∞] | GAMS reslim |