SHOT

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 [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

Option Description Default
Model.BoundTightening.FeasibilityBased.MaxIterations Maximal number of bound tightening iterations 5
Model.BoundTightening.FeasibilityBased.TimeLimit Time limit for bound tightening 5
Model.BoundTightening.FeasibilityBased.Use Peform feasibility-based bound tightening 1
Model.BoundTightening.FeasibilityBased.UseNonlinear Peform feasibility-based bound tightening on nonlinear expressions 1
Model.Convexity.AssumeConvex Assume that the problem is convex. 0
Model.Convexity.Quadratics.EigenValueTolerance Convexity tolerance for the eigenvalues of the Hessian matrix for quadratic terms 1e-05
Model.Reformulation.Bilinear.AddConvexEnvelope Add convex envelopes (subject to original bounds) to bilinear terms 0
Model.Reformulation.Bilinear.IntegerFormulation How to reformulate integer bilinear terms
0: None
1: 1D
2: 2D
1
Model.Reformulation.Bilinear.IntegerFormulation.MaxDomain Do not reformulate integer variables in bilinear terms which can assume more than this number of discrete values
Range: {2, ..., ∞}
100
Model.Reformulation.Constraint.PartitionNonlinearTerms When to partition nonlinear sums in objective function
0: Always
1: If convex
2: Never
1
Model.Reformulation.Constraint.PartitionQuadraticTerms When to partition quadratic sums in objective function
0: Always
1: If convex
2: Never
1
Model.Reformulation.Monomials.Extract Extract monomial terms from nonlinear expressions 1
Model.Reformulation.Monomials.Formulation How to reformulate binary monomials
0: None
1: Simple
2: Costa and Liberti
1
Model.Reformulation.ObjectiveFunction.Epigraph.Use Reformulates a nonlinear objective as an auxiliary constraint 0
Model.Reformulation.ObjectiveFunction.PartitionNonlinearTerms When to partition nonlinear sums in objective function
0: Always
1: If convex
2: Never
1
Model.Reformulation.ObjectiveFunction.PartitionQuadraticTerms When to partition quadratic sums in objective function
0: Always
1: If convex
2: Never
1
Model.Reformulation.Quadratics.ExtractStrategy How to extract quadratic terms from nonlinear expressions
0: Do not extract
1: Extract to same objective or constraint
2: Extract to quadratic equality constraint if nonconvex
3: Extract to quadratic equality constraint even if convex
1
Model.Reformulation.Quadratics.Strategy How to treat quadratic functions
0: All nonlinear
1: Use quadratic objective
2: Use convex quadratic objective and constraints
3: Use nonconvex quadratic objective and constraints
2
Model.Reformulation.Signomials.Extract Extract signomial terms from nonlinear expressions 1
Model.Variables.Continuous.MaximumUpperBound Maximum upper bound for continuous variables
Range: [-∞, ∞]
1e+50
Model.Variables.Continuous.MinimumLowerBound Minimum lower bound for continuous variables
Range: [-∞, ∞]
-1e+50
Model.Variables.Integer.MaximumUpperBound Maximum upper bound for integer variables
Range: [-∞, ∞]
2e+09
Model.Variables.Integer.MinimumLowerBound Minimum lower bound for integer variables
Range: [-∞, ∞]
-2e+09
Model.Variables.NonlinearObjectiveVariable.Bound Max absolute bound for the auxiliary nonlinear objective variable
Range: [-∞, ∞]
1e+12

Solver output

Option Description Default
Output.Console.DualSolver.Show Show output from dual solver on console 0
Output.Console.Iteration.Detail When should the fixed strategy be used
0: Full
1: On objective gap update
2: On objective gap update and all primal NLP calls
1
Output.Console.LogLevel Log level for console output
0: Trace
1: Debug
2: Info
3: Warning
4: Error
5: Critical
6: Off
2
Output.Console.PrimalSolver.Show Show output from primal solver on console 0
Output.Debug.Enable Use debug functionality 0
Output.Debug.Path The folder where to save the debug information

Primal heuristics

Option Description Default
Primal.FixedInteger.CallStrategy When should the fixed strategy be used
0: Use each iteration
1: Based on iteration or time
2: Based on iteration or time, and for all feasible MIP solutions
2
Primal.FixedInteger.CreateInfeasibilityCut Create a cut from an infeasible solution point 0
Primal.FixedInteger.DualPointGap.Relative If the objective gap between the MIP point and dual solution is less than this the fixed strategy is activated 0.001
Primal.FixedInteger.Frequency.Dynamic Dynamically update the call frequency based on success 1
Primal.FixedInteger.Frequency.Iteration Max number of iterations between calls 10
Primal.FixedInteger.Frequency.Time Max duration (s) between calls 5
Primal.FixedInteger.IterationLimit Max number of iterations per call 10000000
Primal.FixedInteger.OnlyUniqueIntegerCombinations Whether to resolve with the same integer combination, e.g. for nonconvex problems with different continuous variable starting points 1
Primal.FixedInteger.Solver NLP solver to use
0: Ipopt
1: GAMS
1
Primal.FixedInteger.Source Source of fixed MIP solution point
0: All
1: First
2: All feasible
3: First and all feasible
4: With smallest constraint deviation
3
Primal.FixedInteger.SourceProblem Which problem formulation to use for NLP problem
0: Original problem
1: Reformulated problem
2: Both
0
Primal.FixedInteger.TimeLimit Time limit (s) per NLP problem 10
Primal.FixedInteger.Use Use the fixed integer primal strategy 1
Primal.FixedInteger.Warmstart Warm start the NLP solver 1
Primal.Rootsearch.Use Use a rootsearch to find primal solutions 1
Primal.Tolerance.Integer Integer tolerance for accepting primal solutions
Range: [-∞, ∞]
1e-05
Primal.Tolerance.LinearConstraint Linear constraint tolerance for accepting primal solutions
Range: [-∞, ∞]
1e-06
Primal.Tolerance.NonlinearConstraint Nonlinear constraint tolerance for accepting primal solutions
Range: [-∞, ∞]
1e-05
Primal.Tolerance.TrustLinearConstraintValues Trust that subsolvers (NLP, MIP) give primal solutions that respect linear constraints 1

Strategy

Option Description Default
Strategy.UseRecommendedSettings Modifies some settings to their recommended values based on the strategy 1

Subsolver functionality

Option Description Default
Subsolver.Cbc.AutoScale Whether to scale objective, rhs and bounds of problem if they look odd (experimental) 0
Subsolver.Cbc.DeterministicParallelMode Run Cbc with multiple threads in deterministic mode 0
Subsolver.Cbc.NodeStrategy Node strategy
0: depth
1: downdepth
2: downfewest
3: fewest
4: hybrid
5: updepth
6: upfewest
4
Subsolver.Cbc.Scaling Whether to scale problem
0: automatic
1: dynamic
2: equilibrium
3: geometric
4: off
5: rowsonly
0
Subsolver.Cbc.Strategy This turns on newer features
0: easy problems
1: default
2: aggressive
1
Subsolver.Cplex.AddRelaxedLazyConstraintsAsLocal Whether to add lazy constraints generated in relaxed points as local or global 0
Subsolver.Cplex.FeasOptMode Strategy to use for the feasibility repair
0: Minimize the sum of all required relaxations in first phase only
1: Minimize the sum of all required relaxations in first phase and execute second phase to find optimum among minimal relaxations
2: Minimize the number of constraints and bounds requiring relaxation in first phase only
3: Minimize the sum of squares of required relaxations in first phase only
4: Minimize the sum of squares of required relaxations in first phase and execute second phase to find optimum among minimal relaxations
0
Subsolver.Cplex.MemoryEmphasis Try to conserve memory when possible
Range: {0, ..., 1}
0
Subsolver.Cplex.MIPEmphasis Sets the MIP emphasis
0: Balanced
1: Feasibility
2: Optimality
3: Best bound
4: Hidden feasible
1
Subsolver.Cplex.NodeFile Where to store the node file
0: No file
1: Compressed in memory
2: On disk
3: Compressed on disk
1
Subsolver.Cplex.NumericalEmphasis Emphasis on numerical stability
Range: {0, ..., 1}
0
Subsolver.Cplex.OptimalityTarget Specifies how CPLEX treats nonconvex quadratics
0: Automatic
1: Searches for a globally optimal solution to a convex model
2: Searches for a solution that satisfies first-order optimality conditions, but is not necessarily globally optimal
3: Searches for a globally optimal solution to a nonconvex model
0
Subsolver.Cplex.ParallelMode Controls how much time and memory should be used when filling the solution pool
0: Automatic
1: Deterministic
-1: Opportunistic
0
Subsolver.Cplex.Probe Sets the MIP probing level
0: Automatic
1: Moderate
2: Aggressive
3: Very aggressive
-1: No probing
0
Subsolver.Cplex.SolutionPoolGap Sets the relative gap filter on objective values in the solution pool
Range: [0, 1e+75]
1e+75
Subsolver.Cplex.SolutionPoolIntensity Controls how much time and memory should be used when filling the solution pool
0: Automatic
1: Mild
2: Moderate
3: Aggressive
4: Very aggressive
0
Subsolver.Cplex.SolutionPoolReplace How to replace solutions in the solution pool when full
0: Replace oldest
1: Replace worst
2: Find diverse
0
Subsolver.Cplex.UseGenericCallback Use the new generic callback in the single-tree strategy 0
Subsolver.Cplex.WorkDirectory Directory for swap file
Subsolver.Cplex.WorkMemory Memory limit for when to start swapping to disk
Range: [0, 1e+75]
0
Subsolver.GAMS.NLP.OptionsFilename Options file for the NLP solver in GAMS
Subsolver.GAMS.NLP.Solver NLP solver to use in GAMS (auto: SHOT chooses) auto
Subsolver.Gurobi.Heuristics The relative amount of time spent in MIP heuristics.
Range: [0, 1]
0.05
Subsolver.Gurobi.MIPFocus MIP focus
0: Automatic
1: Feasibility
2: Optimality
3: Best bound
0
Subsolver.Gurobi.NumericFocus MIP focus
0: Automatic
1: Mild
2: Moderate
3: Aggressive
2
Subsolver.Gurobi.PoolSearchMode Finds extra solutions
0: No extra effort
1: Try to find solutions
2: Find n best solutions
0
Subsolver.Gurobi.PoolSolutions Determines how many MIP solutions are stored
Range: {1, ..., 2000000000}
1
Subsolver.Gurobi.ScaleFlag Controls model scaling
0: Off
1: Mild
2: Moderate
3: Aggressive
-1: Automatic
-1
Subsolver.Ipopt.ConstraintViolationTolerance Constraint violation tolerance in Ipopt
Range: [-∞, ∞]
1e-08
Subsolver.Ipopt.LinearSolver Ipopt linear subsolver
0: Default
1: MA27
2: MA57
3: MA86
4: MA97
5: MUMPS
5
Subsolver.Ipopt.MaxIterations Maximum number of iterations 1000
Subsolver.Ipopt.RelativeConvergenceTolerance Relative convergence tolerance
Range: [-∞, ∞]
1e-08
Subsolver.Rootsearch.ActiveConstraintTolerance Epsilon constraint tolerance for root search 0
Subsolver.Rootsearch.MaxIterations Maximal root search iterations 100
Subsolver.Rootsearch.Method Root search method to use
0: TOMS748
1: Bisection
0
Subsolver.Rootsearch.TerminationTolerance Epsilon lambda tolerance for root search 1e-16

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