Explore the vast range of titles available.

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.

In this paper, an open-source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The POA is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended supporting hyperplane (ESH) and extended cutting plane (ECP) algorithms. The dual strategy can be tightly integrated with the mixed-integer programming (MIP) subsolver in a so-called single-tree manner, i.e., only a single MIP optimization problem is solved, where the polyhedral linearizations are added as lazy constraints through callbacks in the MIP solver. This enables the MIP solver to reuse the branching tree in each iteration, in contrast to most other POA-based methods. SHOT is available as a COIN-OR open-source project, and it utilizes a flexible task-based structure making it easy to extend and modify. It is currently available in GAMS, and can be utilized in AMPL, Pyomo and JuMP as well through its ASL interface. The main functionality and solution strategies implemented in SHOT are described in this paper, and their impact on the performance are illustrated through numerical benchmarks on 406 convex MINLP problems from the MINLPLib problem library. Many of the features introduced in SHOT can be utilized in other POA-based solvers as well. To show the overall effectiveness of SHOT, it is also compared to other state-of-the-art solvers on the same benchmark set.

Several deterministic methods for convex mixed integer nonlinear programming generate a polyhedral approximation of the feasible region, and utilize this approximation to obtain trial solutions. Such methods are, e.g., outer approximation, the extended cutting plane method and the extended supporting hyperplane method. In order to obtain the optimal solution and verify global optimality, these methods often require a quite accurate polyhedral approximation. In case the nonlinear functions are convex and separable to some extent, it is possible to obtain a tighter approximation by using a lifted polyhedral approximation, which can be achieved by reformulating the problem. We prove that under mild assumptions, it is possible to obtain tighter linear approximations for a type of functions referred to as almost additively separable. Here it is also shown that solvers, by a simple reformulation, can benefit from the tighter approximation, and a numerical comparison demonstrates the potential of the reformulation. The reformulation technique can also be combined with other known transformations to make it applicable to some nonseparable convex functions. By using a power transform and a logarithmic transform the reformulation technique can for example be applied to p-norms and some convex signomial functions, and the benefits of combining these transforms with the reformulation technique are illustrated with some numerical examples.

In this paper some transformation techniques, based on power transformations, are discussed. The techniques can be applied to solve optimization problems including signomial functions to global optimality. Signomial terms can always be convexified and underestimated using power transformations on the individual variables in the terms. However, often not all variables need to be transformed. A method for minimizing the number of original variables involved in the transformations is, therefore, presented. In order to illustrate how the given method can be integrated into the transformation framework, some mixed integer optimization problems including signomial functions are finally solved to global optimality using the given techniques.

Solution methods for convex mixed integer nonlinear programming (MINLP) problems have, usually, proven convergence properties if the functions involved are differentiable and convex. For other classes of convex MINLP problems fewer results have been given. Classical differential calculus can, though, be generalized to more general classes of functions than differentiable, via subdifferentials and subgradients. In addition, more general than convex functions can be included in a convex problem if the functions involved are defined from convex level sets, instead of being defined as convex functions only. The notion generalized convex, used in the heading of this paper, refers to such additional properties. The generalization for the differentiability is made by using subgradients of Clarke’s subdifferential. Thus, all the functions in the problem are assumed to be locally Lipschitz continuous. The generalization of the functions is done by considering quasiconvex functions. Thus, instead of differentiable convex functions, nondifferentiable f∘-quasiconvex functions can be included in the actual problem formulation and a supporting hyperplane approach is given for the solution of the considered MINLP problem. Convergence to a global minimum is proved for the algorithm, when minimizing an f∘-pseudoconvex function, subject to f∘-pseudoconvex constraints. With some additional conditions, the proof is also valid for f∘-quasiconvex functions, which sums up the properties of the method, treated in the paper. The main contribution in this paper is the generalization of the Extended Supporting Hyperplane method in Eronen et al. (J Glob Optim 69(2):443–459, 2017) to also solve problems with f∘-pseudoconvex objective function.

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called α BB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.

Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The BB methodology produces such underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.

In this paper, we generalize the extended supporting hyperplane algorithm for a convex continuously differentiable mixed-integer nonlinear programming problem to solve a wider class of nonsmooth problems. The generalization is made by using the subgradients of the Clarke subdifferential instead of gradients. Consequently, all the functions in the problems are assumed to be locally Lipschitz continuous. The algorithm is shown to converge to a global minimum of an MINLP problem if the objective function is convex and the constraint functions are f ∘ -pseudoconvex. With some additional assumptions, the constraint functions may be f ∘ -quasiconvex.

Branch-and-bound in combination with convex underestimators constitute the basis for many algorithms in global nonconvex mixed-integer nonlinear programming (MINLP). Another option is to rely on reformulation-based techniques such as the α signomial global optimization (αSGO) algorithm, where power and exponential transformations for signomial or polynomial function and the α reformulation (αR) technique for general nonconvex twice-differentiable functions are used to reformulate the nonconvex problem. The transformations are approximated using piecewise linear functions (PLFs), resulting in a convex relaxation of the original nonconvex problem in an extended variable space. The solution to this reformulated problem provides a lower bound to the global minimum (of a minimization problem), and by iteratively refining the PLFs, the ε-global solution can be obtained. A drawback with many reformulation-based techniques is that known convex envelopes cannot directly be utilized. However, in this paper, a formulation for expressing the convex envelope of bilinear terms in the αSGO framework is described, and it is shown that this improves the tightness of the lower bound.