In this article we introduce an inner parallel cuttingplane method (IPCP) to compute good feasible points along with valid cuttingplanes for mixed-integer convex optimization problems. The method iteratively generat...
详细信息
In this article we introduce an inner parallel cuttingplane method (IPCP) to compute good feasible points along with valid cuttingplanes for mixed-integer convex optimization problems. The method iteratively generates polyhedral outer approximations of an enlarged inner parallel set (EIPS) of the continuously relaxed feasible set. This EIPS possesses the crucial property that any rounding of any of its elements is feasible for the original problem. The outer approximations are refined in each iteration by using modified Kelley cuttingplanes, which are defined via rounded optimal points of linear optimization problems (LPs). We show that the method either computes a feasible point or certifies that the EIPS is empty. Moreover, we demonstrate how inner parallel cuts can be reversed so that they are valid for the original problem, and we provide bounds on the objective value of the generated feasible points. As there exist consistent problems which possess an empty EIPS, the IPCP is not guaranteed to find a feasible point for the latter. Yet, the crucial advantage of the method lies in the difficulty of each iteration: While other approaches need to solve a mixed-integer linear optimization problem, the IPCP only needs to solve an LP. Indeed, our computational study indicates that the IPCP is able to quickly compute feasible points and reversed inner parallel cuttingplanes for many practical applications. It further demonstrates that the computed points are generally of good quality and that the reversed inner parallel cuts have the potential to speed up outer approximation--based methods.
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....
详细信息
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 extendedcuttingplane 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 article, a generalization of the ECP algorithm to cover a class of nondifferentiable Mixed-Integer NonLinear Programming problems is studied. In the generalization constraint functions are required to be -pseu...
详细信息
In this article, a generalization of the ECP algorithm to cover a class of nondifferentiable Mixed-Integer NonLinear Programming problems is studied. In the generalization constraint functions are required to be -pseudoconvex instead of pseudoconvex functions. This enables the functions to be nonsmooth. The objective function is first assumed to be linear but also -pseudoconvex case is considered. Furthermore, the gradients used in the ECP algorithm are replaced by the subgradients of Clarke subdifferential. With some additional assumptions, the resulting algorithm shall be proven to converge to a global minimum.
In this article, generalization of some mixed-integer nonlinear programming algorithms to cover convex nonsmooth problems is studied. In the extendedcuttingplane method, gradients are replaced by the subgradients of...
详细信息
In this article, generalization of some mixed-integer nonlinear programming algorithms to cover convex nonsmooth problems is studied. In the extendedcuttingplane method, gradients are replaced by the subgradients of the convex function and the resulting algorithm shall be proved to converge to a global optimum. It is shown through a counterexample that this type of generalization is insufficient with certain versions of the outer approximation algorithm. However, with some modifications to the outer approximation method a special type of nonsmooth functions for which the subdifferential at any point is a convex combination of a finite number of subgradients at the point can be considered. Numerical results with extendedcuttingplane method are also reported.
暂无评论