Authors:Kai Zhou; Mustafa R. Kılınç; Xi Chen; Nikolaos V. Sahinidis Pages: 497 - 516 Abstract: Abstract Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0559-0 Issue No:Vol. 70, No. 3 (2018)

Authors:Jian Lv; Li-Ping Pang; Fan-Yun Meng Pages: 517 - 549 Abstract: Abstract We propose an inexact proximal bundle method for constrained nonsmooth nonconvex optimization problems whose objective and constraint functions are known through oracles which provide inexact information. The errors in function and subgradient evaluations might be unknown, but are merely bounded. To handle the nonconvexity, we first use the redistributed idea, and consider even more difficulties by introducing inexactness in the available information. We further examine the modified improvement function for a series of difficulties caused by the constrained functions. The numerical results show the good performance of our inexact method for a large class of nonconvex optimization problems. The approach is also assessed on semi-infinite programming problems, and some encouraging numerical experiences are provided. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0565-2 Issue No:Vol. 70, No. 3 (2018)

Authors:Xiaolong Kuang; Luis F. Zuluaga Pages: 551 - 577 Abstract: Abstract Completely positive (CP) tensors, which correspond to a generalization of CP matrices, allow to reformulate or approximate a general polynomial optimization problem (POP) with a conic optimization problem over the cone of CP tensors. Similarly, completely positive semidefinite (CPSD) tensors, which correspond to a generalization of positive semidefinite (PSD) matrices, can be used to approximate general POPs with a conic optimization problem over the cone of CPSD tensors. In this paper, we study CP and CPSD tensor relaxations for general POPs and compare them with the bounds obtained via a Lagrangian relaxation of the POPs. This shows that existing results in this direction for quadratic POPs extend to general POPs. Also, we provide some tractable approximation strategies for CP and CPSD tensor relaxations. These approximation strategies show that, with a similar computational effort, bounds obtained from them for general POPs can be tighter than bounds for these problems obtained by reformulating the POP as a quadratic POP, which subsequently can be approximated using CP and PSD matrices. To illustrate our results, we numerically compare the bounds obtained from these relaxation approaches on small scale fourth-order degree POPs. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0558-1 Issue No:Vol. 70, No. 3 (2018)

Authors:Yiduo Zhan; Qipeng P. Zheng; Chung-Li Tseng; Eduardo L. Pasiliao Pages: 579 - 599 Abstract: Abstract This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0563-4 Issue No:Vol. 70, No. 3 (2018)

Authors:Terry-Leigh Oliphant; M. Montaz Ali Pages: 601 - 623 Abstract: Abstract A local trajectory-based method for solving mixed integer nonlinear programming problems is proposed. The method is based on the trajectory-based method for continuous optimization problems. The method has three phases, each of which performs continuous minimizations via the solution of systems of differential equations. A number of novel contributions, such as an adaptive step size strategy for numerical integration and a strategy for updating the penalty parameter, are introduced. We have shown that the optimal value obtained by the proposed method is at least as good as the minimizer predicted by a recent definition of a mixed integer local minimizer. Computational results are presented, showing the effectiveness of the method. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0570-5 Issue No:Vol. 70, No. 3 (2018)

Authors:Christoph Buchheim; Marianna De Santis; Francesco Rinaldi; Long Trieu Pages: 625 - 644 Abstract: Abstract We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. We address this class of convex mixed-integer minimization problems by designing a branch-and-bound algorithm, where at each node, the continuous relaxation is solved by a non-monotone Frank–Wolfe type algorithm with away-steps. Experimental results on portfolio optimization problems show that our approach can outperform the MISOCP solver of CPLEX 12.6 for instances where a linear risk-weighting function is considered. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0571-4 Issue No:Vol. 70, No. 3 (2018)

Authors:Charles Audet; Michael Kokkolaras; Sébastien Le Digabel; Bastien Talgorn Pages: 645 - 675 Abstract: Abstract We investigate surrogate-assisted strategies for global derivative-free optimization using the mesh adaptive direct search (MADS) blackbox optimization algorithm. In particular, we build an ensemble of surrogate models to be used within the search step of MADS to perform global exploration, and examine different methods for selecting the best model for a given problem at hand. To do so, we introduce an order-based error tailored to surrogate-based search. We report computational experiments for ten analytical benchmark problems and three engineering design applications. Results demonstrate that different metrics may result in different model choices and that the use of order-based metrics improves performance. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0574-1 Issue No:Vol. 70, No. 3 (2018)

Authors:Xianyue Li; Zhao Zhang; Ding-Zhu Du Pages: 677 - 685 Abstract: Abstract The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0554-5 Issue No:Vol. 70, No. 3 (2018)

Authors:Q. L. Dong; Y. J. Cho; L. L. Zhong; Th. M. Rassias Pages: 687 - 704 Abstract: Abstract In this article, we introduce an inertial projection and contraction algorithm by combining inertial type algorithms with the projection and contraction algorithm for solving a variational inequality in a Hilbert space H. In addition, we propose a modified version of our algorithm to find a common element of the set of solutions of a variational inequality and the set of fixed points of a nonexpansive mapping in H. We establish weak convergence theorems for both proposed algorithms. Finally, we give the numerical experiments to show the efficiency and advantage of the inertial projection and contraction algorithm. PubDate: 2018-03-01 DOI: 10.1007/s10898-017-0506-0 Issue No:Vol. 70, No. 3 (2018)

Authors:Xiaojin Zheng; Yutong Pan; Xueting Cui Abstract: Abstract We investigate in this paper nonconvex binary quadratically constrained quadratic programming (QCQP) which arises in various real-life fields. We propose a novel approach of getting quadratic convex reformulation (QCR) for this class of optimization problem. Our approach employs quadratic surrogate functions and convexifies all the quadratic inequality constraints to construct QCR. The price of this approach is the introduction of an extra quadratic inequality. The “best” QCR among the proposed family, in terms that the bound of the corresponding continuous relaxation is best, can be found via solving a semidefinite programming problem. Furthermore, we prove that the bound obtained by continuous relaxation of our best QCR is as tight as Lagrangian bound of binary QCQP. Computational experiment is also conducted to illustrate the solution efficiency improvement of our best QCR when applied in off-the-shell software. PubDate: 2018-02-26 DOI: 10.1007/s10898-017-0591-0

Authors:Emily Speakman; Jon Lee Abstract: Abstract In Speakman and Lee (Math Oper Res 42(4):1230–1253, 2017), we analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and-bound. Specifically, for trilinear monomials, we analytically compared the three possible “double-McCormick relaxations” with the tight convex-hull relaxation. Here, again using volume as a measure, for the convex-hull relaxation of trilinear monomials, we establish simple rules for determining the optimal branching variable and optimal branching point. Additionally, we compare our results with current software practice. PubDate: 2018-02-23 DOI: 10.1007/s10898-018-0620-7

Authors:Marco Locatelli Abstract: Abstract In this paper we exploit a slight variant of a result previously proved in Locatelli and Schoen (Math Program 144:65–91, 2014) to define a procedure which delivers the convex envelope of some bivariate functions over polytopes. The procedure is based on the solution of a KKT system and simplifies the derivation of the convex envelope with respect to previously proposed techniques. The procedure is applied to derive the convex envelope of the bilinear function xy over any polytope, and the convex envelope of functions \(x^n y^m\) over boxes. PubDate: 2018-02-23 DOI: 10.1007/s10898-018-0626-1

Authors:D. Kirszenblat; K. G. Sirinanda; M. Brazil; P. A. Grossman; J. H. Rubinstein; D. A. Thomas Abstract: Abstract This paper introduces an exact algorithm for the construction of a shortest curvature-constrained network interconnecting a given set of directed points in the plane and a gradient descent method for doing so in 3D space. Such a network will be referred to as a minimum Dubins tree, since its edges are Dubins paths (or slight variants thereof). The problem of constructing a minimum Dubins tree appears in the context of underground mining optimisation, where the objective is to construct a least-cost network of tunnels navigable by trucks with a minimum turning radius. The Dubins tree problem is similar to the Steiner tree problem, except the terminals are directed and there is a curvature constraint. We propose the minimum curvature-constrained Steiner point algorithm for determining the optimal location of the Steiner point in a 3-terminal network. We show that when two terminals are fixed and the third varied in the planar version of the problem, the Steiner point traces out a limaçon. PubDate: 2018-02-21 DOI: 10.1007/s10898-018-0625-2

Authors:Cristiana L. Lara; Francisco Trespalacios; Ignacio E. Grossmann Abstract: Abstract In this paper we propose a nonlinear Generalized Disjunctive Programming model to optimize the 2-dimensional continuous location and allocation of the potential facilities based on their maximum capacity and the given coordinates of the suppliers and customers. The model belongs to the class of Capacitated Multi-facility Weber Problem. We propose a bilevel decomposition algorithm that iteratively solves a discretized MILP version of the model, and its nonconvex NLP for a fixed selection of discrete variables. Based on the bounding properties of the subproblems, \(\epsilon \) -convergence is proved for this algorithm. We apply the proposed method to random instances varying from 2 suppliers and 2 customers to 40 suppliers and 40 customers, from one type of facility to 3 different types, and from 2 to 32 potential facilities. The results show that the algorithm is more effective at finding global optimal solutions than general purpose global optimization solvers tested. PubDate: 2018-02-21 DOI: 10.1007/s10898-018-0621-6

Authors:Wendel Melo; Marcia Fampa; Fernanda Raupp Abstract: Abstract We present two feasibility heuristics for binary mixed integer nonlinear programming. Called integrality gap minimization algorithm (IGMA)—versions 1 and 2, our heuristics are based on the solution of integrality gap minimization problems with a space partitioning scheme defined over the integer variables of the problem addressed. Computational results on a set of benchmark instances show that the proposed approaches present satisfactory results. PubDate: 2018-02-20 DOI: 10.1007/s10898-018-0623-4

Authors:Antanas Žilinskas; James Calvin Abstract: Abstract A global optimization problem is considered where the objective functions are assumed “black box” and “expensive”. An algorithm is theoretically substantiated using a statistical model of objective functions and the theory of rational decision making under uncertainty. The search process is defined as a sequence of bi-objective selections of sites for the computation of the objective function values. It is shown that two well known (the maximum average improvement, and the maximum improvement probability) algorithms are special cases of the proposed general approach. PubDate: 2018-02-19 DOI: 10.1007/s10898-018-0622-5

Authors:A. L. Custódio; J. F. A. Madeira Abstract: Abstract The optimization of multimodal functions is a challenging task, in particular when derivatives are not available for use. Recently, in a directional direct search framework, a clever multistart strategy was proposed for global derivative-free optimization of single objective functions. The goal of the current work is to generalize this approach to the computation of global Pareto fronts for multiobjective multimodal derivative-free optimization problems. The proposed algorithm alternates between initializing new searches, using a multistart strategy, and exploring promising subregions, resorting to directional direct search. Components of the objective function are not aggregated and new points are accepted using the concept of Pareto dominance. The initialized searches are not all conducted until the end, merging when they start to be close to each other. The convergence of the method is analyzed under the common assumptions of directional direct search. Numerical experiments show its ability to generate approximations to the different Pareto fronts of a given problem. PubDate: 2018-02-19 DOI: 10.1007/s10898-018-0618-1

Authors:Victor Gergel; Evgeny Kozinov Abstract: Abstract This paper proposes an efficient method for solving complex multicriterial optimization problems, for which the optimality criteria may be multiextremal and the calculations of the criteria values may be time-consuming. The approach involves reducing multicriterial problems to global optimization ones through minimax convolution of partial criteria, reducing dimensionality by using Peano curves and implementing efficient information-statistical methods for global optimization. To efficiently find the set of Pareto-optimal solutions, it is proposed to reuse all the search information obtained in the course of optimization. The results of computational experiments indicate that the proposed approach greatly reduces the computational complexity of solving multicriterial optimization problems. PubDate: 2018-02-19 DOI: 10.1007/s10898-018-0624-3

Authors:Zilong Wang; Marianthi Ierapetritou Abstract: Abstract Feasibility analysis has been developed to evaluate and quantify the capability that a process can remain feasible under uncertainty of model inputs and parameters. It can be conducted during the design stage when the objective is to get a robust design which can tolerate a certain amount of variations in the process conditions. Also, it can be used after a design is fixed when the objective is to characterize its feasible region. In this work, we have extended the usage of feasibility analysis to the cases in which inherent stochasticity is existent in the model outputs. With a surrogate-based adaptive sampling framework, we have developed and compared three algorithms that are promising to make accurate predictions on the feasible regions with a limited sampling budget. Both the advantages and limitations are discussed based on the results from five benchmark problems. Finally, we apply such methods to a pharmaceutical manufacturing process and demonstrate its potential application in characterizing the design space of the process. PubDate: 2018-02-16 DOI: 10.1007/s10898-018-0615-4

Authors:Kamil A. Khan; Matthew Wilhelm; Matthew D. Stuber; Huiyi Cao; Harry A. J. Watson; Paul I. Barton Abstract: Abstract These errata correct various errors in the closed-form relaxations provided by Khan, Watson, and Barton in the article “Differentiable McCormick Relaxations” (J Glob Optim, 67:687–729, 2017). Without these corrections, the provided closed-form relaxations may fail to be convex or concave and may fail to be valid relaxations. PubDate: 2018-01-25 DOI: 10.1007/s10898-017-0601-2