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 [113, 109, 100, 101, 108].
SHOT supports GAMS equations that use the following intrinsic functions: abs, arcsin, arccos, arctan(2), cos, cosh, cvPower, div, (c)entropy, edist, errf, exp, log, log10, log2, min, max, pi, poly, power, rPower, sigmoid, signpower, sin, sinh, sqr, sqrt, tan, tanh, 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 GUROBI, if a GAMS/GUROBI license is available, CPLEX, if a GAMS/CPLEX license is available, and otherwise HiGHS. 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. [109]).
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, one of the GAMS NLP solvers, or SHOT itself.
- 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 asterisk (*) 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.
Solver output
These settings control how much and what output is shown to the user from the solver.
| Option | Description | Default |
| Output.Debug.Path | The folder where to save the debug information
Range: string | |
| Output.GAMS.AlternateSolutionsFile | Name of GAMS GDX file to write alternative solutions to
Range: string | |
| Output.Console.Iteration.Detail | Which iterations are shown on the console: all, or only those that update the objective gap (and those with a primal NLP call). Some iterations are shown regardless after 100 hidden ones or 2 s
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.DualSolver.Show | Show output from dual solver on console
Range: boolean | 0 |
| Output.Console.PrimalSolver.Show | Show output from primal solver on console
Range: boolean | 0 |
| Output.Debug.Enable | Use debug functionality
Range: boolean | 0 |
Subsolver functionality
These settings allow for more direct control of the different subsolvers utilized in SHOT.
| Option | Description | Default |
| Subsolver.Cplex.WorkDirectory | Directory for swap file
Range: string | |
| Subsolver.GAMS.NLP.OptionsFilename | Options file for the NLP solver in GAMS
Range: string | |
| Subsolver.GAMS.NLP.Solver | NLP solver to use in GAMS (auto: SHOT chooses)
Range: string | auto |
| Subsolver.Ipopt.OptionsFile | An Ipopt options file with any Ipopt options, read instead of ipopt.opt in the working directory. Its options override those set by SHOT, e.g. the linear solver, except the time limit (max_wall_time) of each solve
Range: string | |
| 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.Conopt.DerivativeCheck | CONOPT compares the first and second derivatives with numerical ones (Lkdebg, Lkdeb2): 0 = never, -1 = at the initial point, n = every n-th iteration
Range: {-1, ..., ∞} | 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 number of constraints and bounds requiring relaxation in first phase and execute second phase to find optimum among minimal relaxations
4: Minimize the sum of squares of required relaxations in first phase only
5: Minimize the sum of squares of required relaxations in first phase and execute second phase to find optimum among minimal relaxations | 0 |
| Subsolver.Cplex.MIPEmphasis | Sets the MIP emphasis
0: Balanced
1: Feasibility
2: Optimality
3: Best bound
4: Hidden feasible | 0 |
| Subsolver.Cplex.MemoryEmphasis | Try to conserve memory when possible
Range: {0, ..., 1} | 0 |
| 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 | Parallel mode in CPLEX, i.e., whether it runs deterministically when using several threads
-1: Opportunistic
0: Automatic
1: Deterministic | 0 |
| Subsolver.Cplex.Probe | Sets the MIP probing level
-1: No probing
0: Automatic
1: Moderate
2: Aggressive
3: Very aggressive | 0 |
| 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.Gurobi.MIPFocus | MIP focus
0: Automatic
1: Feasibility
2: Optimality
3: Best bound | 0 |
| Subsolver.Gurobi.NumericFocus | How much effort Gurobi spends on detecting and managing numerical issues
0: Automatic
1: Mild
2: Moderate
3: Aggressive | 0 |
| Subsolver.Gurobi.PoolSearchMode | Finds extra solutions
0: No extra effort
1: Try to find solutions
2: Find n best solutions | 0 |
| Subsolver.Gurobi.ScaleFlag | Controls model scaling
-1: Automatic
0: Off
1: Mild
2: Moderate
3: Aggressive | -1 |
| Subsolver.Highs.DebugLevel | Debug level for HiGHS internal assertions
0: off
1: low
2: medium
3: high | 0 |
| Subsolver.Highs.MIPIPMSolver | Interior point solver that HiGHS uses in the MIP solver, e.g., for the analytic center
0: choose
1: ipx
2: hipo (only if HiGHS has been built with HiPO) | 0 |
| Subsolver.Highs.Parallel | Use parallelization
0: off
1: choose
2: on | 1 |
| Subsolver.Highs.Presolve | Use presolve
0: off
1: choose
2: on | 1 |
| Subsolver.Highs.RunCrossover | Run crossover
0: off
1: choose
2: on | 0 |
| Subsolver.Ipopt.HessianApproximation | The Hessian of the Lagrangian used by Ipopt. Automatic uses a limited-memory approximation if the exact Hessian of a nonlinear expression with at least 64 variables is nearly dense, since it is then expensive
0: Exact
1: Limited memory
2: Automatic | 2 |
| Subsolver.Ipopt.LinearSolver | Ipopt linear subsolver
0: Default
1: MA27
2: MA57
3: MA86
4: MA97
5: MUMPS | 5 |
| Subsolver.Rootsearch.MaxIterations | Maximal root search iterations
Range: {0, ..., ∞} | 100 |
| Subsolver.Rootsearch.Method | Root search method to use
0: TOMS748
1: Bisection | 0 |
| Subsolver.Conopt.FeasibilityTolerance | CONOPT feasibility tolerance (Rtnwma)
Range: [1e-12, 0.01] | 1e-09 |
| Subsolver.Conopt.OptimalityTolerance | CONOPT reduced-gradient tolerance (Rtredg)
Range: [1e-12, 0.01] | 1e-09 |
| Subsolver.Cplex.SolutionPoolGap | Sets the relative gap filter on objective values in the solution pool
Range: [0, 1e+75] | 1e+75 |
| Subsolver.Cplex.WorkMemory | Memory limit for when to start swapping to disk
Range: [0, 1e+75] | 0 |
| Subsolver.Gurobi.Heuristics | The relative amount of time spent in MIP heuristics.
Range: [0, 1] | 0.05 |
| Subsolver.Highs.MIPHeuristicEffort | Effort spent for MIP heuristics
Range: [0, 1] | 0.05 |
| Subsolver.Ipopt.ConstraintViolationTolerance | Constraint violation tolerance in Ipopt
Range: [0, ∞] | 1e-08 |
| Subsolver.Ipopt.RelativeConvergenceTolerance | Relative convergence tolerance in Ipopt (tol)
Range: [0, ∞] | 1e-08 |
| Subsolver.Rootsearch.TerminationTolerance | Termination tolerance for the length of the root search interval for lambda in [0, 1], which also stops when the interval cannot be divided further
Range: [0, ∞] | 1e-16 |
| Subsolver.SHOT.ReuseHyperplanes.Fraction | The fraction of generated hyperplanes to reuse.
Range: [0, 1] | 0.1 |
| Subsolver.Cbc.AutoScale | Whether to scale objective, rhs and bounds of problem if they look odd (experimental)
Range: boolean | 0 |
| Subsolver.Cbc.Cuts | Use the cut generators of Cbc, which can give a wrong optimal value for a MILP problem
Range: boolean | 0 |
| Subsolver.Cbc.DeterministicParallelMode | Run Cbc with multiple threads in deterministic mode
Range: boolean | 0 |
| Subsolver.Cplex.AddRelaxedLazyConstraintsAsLocal | Whether to add lazy constraints generated in relaxed points as local or global
Range: boolean | 0 |
| Subsolver.Highs.MIPAllowRestart | Whether MIP restart is permitted
Range: boolean | 1 |
| Subsolver.Highs.MIPDetectSymmetry | Whether MIP symmetry should be detected
Range: boolean | 1 |
| Subsolver.Highs.MIPHeuristicRunShifting | Run Shifting heuristic
Range: boolean | 0 |
| Subsolver.Highs.MIPHeuristicRunZiRound | Run Zi Round heuristic
Range: boolean | 0 |
| Subsolver.SHOT.ReuseHyperplanes.Use | Reuse valid generated hyperplanes in main dual model.
Range: boolean | 1 |
| Subsolver.SHOT.UseFBBT | Do FBBT on NLP problem.
Range: boolean | 1 |
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.ConvexBounding.IdleIterations | How many iterations with new hyperplanes the convex bounding strategy is skipped before it is performed again: 0 = Every iteration with new hyperplanes, 1 = Every second such iteration, etc.
Range: {0, ..., ∞} | 10 |
| Dual.CutStrategy | Dual cut strategy
0: ESH
1: ECP
2: Only external (through callback) | 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.Strategy | Strategy for finding ESH interior points
0: Use internal strategy
1: Only external (through callback) | 0 |
| Dual.ESH.InteriorPoint.UsePrimalSolution | Utilize primal solution as interior point
0: Only if there is no interior point
1: Add as new
2: Replace old
3: Use average | 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.CutResetLimit | Max number of times the cuts of nonconvex constraints are removed without primal objective value improvement when the infeasibility repair loops
Range: {0, ..., ∞} | 3 |
| Dual.MIP.InfeasibilityRepair.IterationLimit | Max number of infeasible problems repaired without primal objective value improvement
Range: {0, ..., ∞} | 100 |
| Dual.MIP.NodeLimit | Node limit for each solve of the MIP solver: 0: No limit
Range: {0, ..., ∞} | 0 |
| Dual.MIP.NumberOfThreads | Number of threads to use in MIP solver: 0: Automatic
Range: {0, ..., 999} | GAMS threads |
| Dual.MIP.RandomSeed | Random seed for the pseudorandom choices in the MIP solver: 0: The default of the solver used
Range: {0, ..., ∞} | 0 |
| Dual.MIP.SolutionLimit.ForceOptimal.Iteration | Iterations without dual bound updates for forcing optimal MIP solution (multi-tree)
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 of the MIP solver
Range: {1, ..., ∞} | 100 |
| Dual.MIP.Solver | Which MIP solver to use. Default: the first available of Gurobi, Cplex, Highs and Cbc
0: Cplex
1: Gurobi
2: Cbc
3: Highs | depends on GAMS license |
| Dual.ReductionCut.MaxIterations | Maximum number of reduction cuts without primal improvement before terminating
Range: {0, ..., ∞} | 20 |
| Dual.ReductionCut.Strategy | The reduction cut strategy to use
0: Fraction
1: GoldenRatio | 0 |
| Dual.Relaxation.Frequency | The frequency to solve an LP problem, if Dual.Relaxation.Use is true (by default not for nonconvex problems): 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 | Max number of violated nonlinear constraints, the most violated first, to generate cutting planes for in the interior point search, as a fraction of the number of nonlinear constraints
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 | Max number of violated nonlinear constraints, the most violated first, to generate hyperplanes for in each solution point, as a fraction of the number of nonlinear constraints
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.HyperplaneCuts.NonfinitePointRetreatFactor | The smallest fraction of the distance to a point where the constraint is finite that the point a hyperplane is generated in is moved, when the constraint is not finite in it
Range: [1e-12, 0.5] | 0.001 |
| 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: [0, ∞] | 1e-05 |
| Dual.MIP.InfeasibilityRepair.TimeLimit | Time limit when repairing infeasible problem
Range: [0, ∞] | 10 |
| 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 (multi-tree)
Range: [0, ∞] | 1000 |
| Dual.MIP.SolutionLimit.IncreaseFactor | Factor the MIP solution limit is multiplied by when increased: 1: Increase by one
Range: [1, ∞] | 2 |
| Dual.MIP.SolutionLimit.UpdateTolerance | The constraint tolerance for when to update MIP solution limit
Range: [0, ∞] | 0.001 |
| Dual.ReductionCut.ReductionFactor | Reduction of the cutoff per reduction cut, relative to max(1, |cutoff|), in the Fraction strategy when the relative gap is at most 0.1 or above 1
Range: [0, 1] | 0.001 |
| Dual.Relaxation.TerminationTolerance | Stop solving relaxed problems when the maximum constraint deviation is at most this value
Range: [0, ∞] | 0.5 |
| Dual.Relaxation.TimeLimit | Time limit (s) when solving LP problems initially
Range: [0, ∞] | 30 |
| Dual.ConvexBounding.Use | Enable the convex bounding strategy for nonconvex problems
Range: boolean | 1 |
| Dual.ESH.InteriorPoint.CuttingPlane.Reuse | Reuse valid cutting planes in main dual model
Range: boolean | 0 |
| Dual.ESH.Rootsearch.UseMaxFunction | Perform rootsearch on max function, otherwise on individual constraints
Range: boolean | 0 |
| Dual.HyperplaneCuts.Delay | Add hyperplane cuts to model only after optimal MIP solution
Range: boolean | 1 |
| Dual.HyperplaneCuts.UniqueConstraints | Allow only one hyperplane per constraint per iteration
Range: boolean | 0 |
| 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 | 0 |
| Dual.MIP.InfeasibilityRepair.RelaxCutsViolatedByPrimal | Relax the cuts of nonconvex constraints that cut off a known primal solution
Range: boolean | 1 |
| Dual.MIP.InfeasibilityRepair.Use | Enable the infeasibility repair strategy for nonconvex problems
Range: boolean | 1 |
| Dual.MIP.UpdateObjectiveBounds | Update nonlinear objective variable bounds to primal/dual bounds
Range: boolean | 0 |
| Dual.MIP.UseDualSolutionStart | Give the discrete values of the previous MIP solution as a partial MIP start in the multi-tree strategy; Cplex and Gurobi get it in addition to the primal solution, HiGHS and Cbc instead of it
Range: boolean | 1 |
| Dual.ReductionCut.Use | Enable the dual reduction cut strategy for nonconvex problems
Range: boolean | 1 |
| 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.
| Option | Description | Default |
| Model.BoundTightening.FeasibilityBased.MaxIterations | Maximal number of bound tightening iterations
Range: {0, ..., ∞} | 5 |
| Model.BoundTightening.InitialPOA.CutStrategy | Dual cut strategy
0: ESH
1: ECP | 1 |
| Model.BoundTightening.InitialPOA.DirectionalSolves | Maximum number of additional solves minimizing or maximizing a variable in a convex constraint without cuts
Range: {0, ..., ∞} | 10 |
| Model.BoundTightening.InitialPOA.IterationLimit | Iteration limit for POA
Range: {1, ..., ∞} | 50 |
| Model.BoundTightening.InitialPOA.StagnationIterationLimit | Limit for iterations without significant progress
Range: {0, ..., ∞} | 5 |
| Model.Reformulation.Bilinear.IntegerFormulation | Reformulate integer bilinear terms
0: No
1: No if nonconvex quadratic terms allowed by MIP solver
2: Yes | 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, ..., ∞} | 250 |
| Model.Reformulation.Bilinear.InverseFormulation | Reformulate constraints a*x1*x2 ≥ c with positive variables as c/(a*x1) - x2 ≤ 0 (and c/(a*x2) - x1 ≤ 0)
0: None
1: One constraint
2: Both constraints | 2 |
| Model.Reformulation.Constraint.PartitionNonlinearTerms | When to partition nonlinear sums in constraints
0: Always
1: If result is convex
2: Never | 1 |
| Model.Reformulation.Constraint.PartitionQuadraticTerms | When to partition quadratic sums in constraints, also in nonlinear constraints
0: Always
1: If result is convex
2: Never | 1 |
| Model.Reformulation.Monomials.Formulation | How to reformulate binary monomials
0: None
1: Simple
2: Costa and Liberti | 1 |
| Model.Reformulation.ObjectiveFunction.EpigraphStrategy | How to choose between objective-function and epigraph-constraint form for the objective. 'Unchanged' performs no epigraph or anti-epigraph reformulation, keeping the objective function exactly as given; 'Objective function' always keeps (or folds back to) a direct objective function; 'Epigraph constraint' always introduces an epigraph auxiliary-variable constraint for nonlinear or quadratic objectives
0: Unchanged
1: Objective function
2: Epigraph constraint | 0 |
| Model.Reformulation.ObjectiveFunction.PartitionNonlinearTerms | When to partition nonlinear sums in objective function
0: Always
1: If result is convex
2: Never | 1 |
| Model.Reformulation.ObjectiveFunction.PartitionQuadraticTerms | When to partition quadratic sums in the objective function, also in a nonlinear objective function
0: Always
1: If result is convex
2: Never | 1 |
| Model.Reformulation.Quadratics.Decomposition.Formulation | Placement of the original term coefficient when decomposing a quadratic term
0: Coefficient is included in reformulation
1: Coefficient remains | 0 |
| Model.Reformulation.Quadratics.Decomposition.Method | How to decompose convex quadratic functions
0: No decomposition
1: Eigenvalue decomposition
2: LDL decomposition | 2 |
| 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.BoundTightening.FeasibilityBased.TimeLimit | Time limit for bound tightening
Range: [0, ∞] | 2 |
| Model.BoundTightening.InitialPOA.ConstraintTolerance | Constraint termination tolerance
Range: [0, ∞] | 0.1 |
| Model.BoundTightening.InitialPOA.ObjectiveConstraintTolerance | Objective constraint termination tolerance
Range: [0, ∞] | 0.001 |
| Model.BoundTightening.InitialPOA.ObjectiveGapAbsolute | Absolute objective gap termination level
Range: [0, ∞] | 0.1 |
| Model.BoundTightening.InitialPOA.ObjectiveGapRelative | Relative objective gap termination level
Range: [0, ∞] | 0.1 |
| Model.BoundTightening.InitialPOA.StagnationConstraintTolerance | Tolerance factor for when no progress is made
Range: [0, ∞] | 0.01 |
| Model.BoundTightening.InitialPOA.TimeLimit | Time limit for all the problems solved for the initial POA
Range: [0, ∞] | 5 |
| Model.Convexity.Quadratics.EigenValueTolerance | Convexity tolerance for the eigenvalues of the Hessian matrix for quadratic terms
Range: [0, ∞] | 1e-05 |
| Model.Reformulation.AbsoluteValue.MaximumBigM | The largest big-M used to bound an absolute value from above with a binary variable; above it, the absolute value is only bounded from below
Range: [0, ∞] | 1e+08 |
| Model.Reformulation.Quadratics.Decomposition.LDLMaximumFill | Skip the LDL decomposition if L would have more than this times the nonzeros of the quadratic matrix, and over a million (0 = no limit)
Range: [0, ∞] | 100 |
| Model.Reformulation.Quadratics.Decomposition.Tolerance | Terms with corresponding eigenvalues or diagonal elements in D-matrix smaller than this value will be ignored
Range: [0, ∞] | 1e-07 |
| Model.Variables.Continuous.MaximumUpperBound | Maximum upper bound for continuous variables
Range: [0, ∞] | 1e+50 |
| Model.Variables.Continuous.MinimumLowerBound | Minimum lower bound for continuous variables
Range: [-∞, 0] | -1e+50 |
| Model.Variables.Integer.MaximumUpperBound | Maximum upper bound for integer variables
Range: [0, ∞] | 2e+09 |
| Model.Variables.Integer.MinimumLowerBound | Minimum lower bound for integer variables
Range: [-∞, 0] | -2e+09 |
| Model.Variables.NonlinearObjectiveVariable.Bound | Absolute bound for the auxiliary nonlinear objective variable, used when the bounds of the objective function cannot be calculated with interval arithmetic
Range: [0, ∞] | 1e+12 |
| Model.BoundTightening.FeasibilityBased.Use | Perform feasibility-based bound tightening
Range: boolean | 1 |
| Model.BoundTightening.FeasibilityBased.UseAfterCallback | Perform feasibility-based bound tightening again after a BoundTightening callback has tightened bounds
Range: boolean | 0 |
| Model.BoundTightening.FeasibilityBased.UseNonlinear | Perform feasibility-based bound tightening on nonlinear expressions
Range: boolean | 1 |
| Model.BoundTightening.InitialPOA.Use | Create an initial polyhedral outer approximation
Range: boolean | 0 |
| Model.Convexity.AssumeConvex | Assume that the problem is convex
Range: boolean | 0 |
| Model.Reformulation.Bilinear.AddConvexEnvelope | Add convex envelopes (subject to original bounds) to bilinear terms
Range: boolean | 0 |
| Model.Reformulation.Monomials.Extract | Extract monomial terms from nonlinear expressions
Range: boolean | 1 |
| Model.Reformulation.Signomials.Extract | Extract signomial terms from nonlinear expressions
Range: boolean | 1 |
Modeling system
These settings control functionality used in the interfaces to different modeling environments.
| Option | Description | Default |
| ModelingSystem.GAMS.QExtractAlg | Extraction algorithm for quadratic equations in GAMS interface
0: automatic
1: threepass
2: doubleforward
3: concurrent | 0 |
| ModelingSystem.GAMS.QExtractDenseSwitchFactor | Sparse/dense factor for quadratic extraction algorithm in GAMS interface.
Range: [0, ∞] | 0.008 |
| ModelingSystem.GAMS.QExtractDenseSwitchLog | Whether to print additional information about sparse/dense factor choice in quadratic extraction algorithm in GAMS interface.
Range: boolean | 0 |
Primal heuristics
These settings control the primal heuristics used in SHOT.
| 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 whenever a MIP solution fulfils the nonlinear constraints | 2 |
| Primal.FixedInteger.Enumeration.MaxCombinations | Max number of combinations of the discrete variables for the exhaustive search to be performed
Range: {1, ..., ∞} | 50 |
| Primal.FixedInteger.Frequency.Iteration | Max number of iterations between calls
Range: {0, ..., ∞} | 10 |
| Primal.FixedInteger.IterationLimit | Max number of iterations per call of the NLP solver: 0: The default of the NLP solver
Range: {0, ..., ∞} | 0 |
| Primal.FixedInteger.MaxStartsPerCall | Maximum number of starting points selected from the dual solution pool per call, for each selected NLP formulation: 0: Unlimited. Does not limit model starting points, final polishing or exhaustive integer search
Range: {0, ..., ∞} | 5 |
| Primal.FixedInteger.NumberOfThreads | Number of threads for each NLP problem, in the NLP solver and its BLAS, OpenMP and Accelerate libraries: 0: Automatic
Range: {0, ..., ∞} | 1 |
| Primal.FixedInteger.Solver | NLP solver to use.
0: Ipopt
1: GAMS
2: SHOT
4: Conopt | 4, if GAMS/CONOPT licensed, otherwise 0 |
| Primal.FixedInteger.Source | Which solutions of the dual problem the fixed-integer NLP problem is solved from. In single-tree, the callbacks use each new incumbent, and this applies to the solution pool after the search
0: All
1: First
2: All feasible
3: First and the one with the smallest constraint deviation
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 | 1 |
| Primal.FixedInteger.SupportingHyperplanes.MaxPerSolution | Max number of supporting hyperplanes in each fixed-integer NLP solution
Range: {0, ..., ∞} | 50 |
| Primal.PolishSolution.NumberOfPoints | After the search, polish the solution with NLP problems started from the best primal solution and from the dual solutions of this many last iterations, not for LP, MILP or convex continuous problems: 0: Off
Range: {0, ..., ∞} | 1 |
| Primal.FixedInteger.DualPointGap.Relative | If the objective gap between the MIP point and dual solution is less than this the fixed strategy is activated
Range: [0, ∞] | 0.001 |
| Primal.FixedInteger.Enumeration.TimeLimit | Time limit (s) for all NLP problems in the exhaustive search
Range: [0, ∞] | 20 |
| Primal.FixedInteger.Frequency.Time | Max duration (s) between calls
Range: [0, ∞] | 5 |
| Primal.FixedInteger.SupportingHyperplanes.ActiveTolerance | A constraint with a value within this tolerance of its bound is active in the fixed-integer NLP solution
Range: [0, ∞] | 1e-05 |
| Primal.FixedInteger.TimeLimit | Time limit (s) per NLP problem
Range: [0, ∞] | 10 |
| Primal.Tolerance.Integer | Integer tolerance for accepting primal solutions
Range: [0, 0.5] | 1e-05 |
| Primal.Tolerance.LinearConstraint | Linear constraint tolerance for accepting primal solutions
Range: [0, ∞] | 1e-06 |
| Primal.Tolerance.NonlinearConstraint | Nonlinear constraint tolerance for accepting primal solutions
Range: [0, ∞] | 1e-05 |
| Primal.FixedInteger.CreateInfeasibilityCut | Create cutting planes in the solution point of the fixed-integer NLP problem for the nonlinear constraints it violates
Range: boolean | 0 |
| Primal.FixedInteger.CreateSupportingHyperplanes | Create supporting hyperplanes in a feasible solution of the fixed-integer NLP problem for the convex nonlinear objective function and the nonlinear constraints active in it.
Range: boolean | 1 |
| Primal.FixedInteger.Enumeration.UseAsFallback | Solve NLP problems for all combinations of the discrete variables if the objective gap could not be closed
Range: boolean | 1 |
| Primal.FixedInteger.Enumeration.UseInitially | Solve NLP problems for all combinations of the discrete variables before the dual strategy
Range: boolean | 0 |
| Primal.FixedInteger.Frequency.Dynamic | Dynamically update the call frequency based on success
Range: boolean | 1 |
| Primal.FixedInteger.OnlyUniqueIntegerCombinations | Solve the NLP problem only once for each combination of the discrete variables. If false, it is solved again from different continuous values, e.g. for nonconvex problems
Range: boolean | 1 |
| Primal.FixedInteger.SupportingHyperplanes.Nonconvex | Also create the supporting hyperplanes for nonconvex constraints and objective functions. As the hyperplanes of the dual strategy for these, they are not global and can be relaxed if they cut away a primal solution
Range: boolean | 0 |
| Primal.FixedInteger.SupportingHyperplanes.OnlyViolated | Only create the supporting hyperplanes that cut away the dual solution the integer assignment comes from
Range: boolean | 0 |
| Primal.FixedInteger.Use | Use the fixed integer primal strategy
Range: boolean | 1 |
| Primal.FixedInteger.UseStartingPoint | Solve an NLP problem from a given starting point that is not feasible, e.g. the levels of the variables in GAMS or the initial values in AMPL, before the first dual problem, and from such points given by the PrimalCandidateSearch callback at the next NLP call
Range: boolean | 1 |
| Primal.FixedInteger.Warmstart | Warm start the NLP solver
Range: boolean | 1 |
| Primal.Rootsearch.Use | Use a rootsearch to find primal solutions
Range: boolean | 1 |
| Primal.Tolerance.TrustLinearConstraintValues | Trust that fixed-integer NLP and LP solvers respect linear constraints; MIP candidates are always checked
Range: boolean | 1 |
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, ..., ∞} | 1000 |
| Termination.IterationLimit | Iteration limit for main strategy
Range: {1, ..., ∞} | GAMS iterlim |
| Termination.PrimalStagnation.IterationLimit | Number of iterations without significant primal improvement after which an objective cut is added (nonconvex problems with reduction cuts only)
Range: {0, ..., ∞} | 50 |
| Termination.ConstraintTolerance | Termination tolerance for nonlinear constraints (not used for termination in the multi-tree strategy)
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 |
Strategy
Overall strategy parameters used in SHOT.
| Option | Description | Default |
| Strategy.UseRecommendedSettings | Use the recommended defaults for nonconvex problems and MIP solvers, shown in the setting descriptions, and the solver-specific adjustments
Range: boolean | 1 |