# Algorithm SHOT is a software for solving mathematical optimization problems of the mixed-integer nonlinear programming (MINLP) class. Originally SHOT was intended for convex MINLP problems only, but as of version 1.0 it 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. {% hint style="info" %} In contrast to other polyhedral outer approximation solvers, the bounds on the objective function value provided by SHOT are valid also for nonconvex problems (with the exception when using the `Model.Convexity.AssumeConvex=true`setting for nonconvex problems). {% endhint %} ## Dual bound through polyhedral (outer) approximation 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 an mixed-integer linear programming (MILP) solver such as CPLEX, Gurobi or Cbc. If CPLEX or Gurobi is used, the subproblems can also include quadratic and bilinear nonlinearities directly; then MIQP or MIQCQP subproblems are solved. ## Primal bound using heuristics The solution to the outer approximation problem provides a lower (dual) bound (when solving a minimization problem) to the original problem if the problem 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. ). To get an upper (primal) bound (when solving a minimization problem) on the optimal solution 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 external NLP solver (e.g. Ipopt). * By checking solutions from the MIP solver's solution pool for points that fulfill also the nonlinearities in the original MINLP problem. * By performing root searches. ## Termination When the relative or absolute difference (objective gap) between the primal and dual bounds is less than a user-specified value, SHOT terminates with the current primal solution. If the original problem is convex, this is a global solution to the problem. If it is nonconvex, there is normally no guarantee that such a solution can be found, however SHOT will always in addition to the primal solution give a valid lower bound on the solution. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://www.shotsolver.dev/shot/about-shot/algorithm.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.