Authors:Konstantin Barkalov; Victor Gergel Pages: 3 - 20 Abstract: Abstract
This work considers a parallel algorithm for solving multidimensional multiextremal optimization problems. This algorithm uses Peano-type space filling curves for dimension reduction. Conditions of non-redundant parallelization of the algorithm are considered. Efficiency of the algorithm on modern computing systems with the use of graphics processing units (GPUs) is investigated. Speedup of the algorithm using GPU as compared with the same algorithm implemented on CPU only is demonstrated experimentally. Computational experiments are carried out on a series of several hundred multidimensional multiextremal problems. PubDate: 2016-09-01 DOI: 10.1007/s10898-016-0411-y Issue No:Vol. 66, No. 1 (2016)

Authors:M. Gaudioso; T. V. Gruzdeva; A. S. Strekalovsky Pages: 21 - 34 Abstract: Abstract
The separation problem of two sets, whose convex hulls have a nonempty intersection, is considered. In order to find a solution of the problem algorithms of local and global search are developed. The efficiency of the algorithms is demonstrated by computational simulations on test examples. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0319-y Issue No:Vol. 66, No. 1 (2016)

Authors:Victor Gergel; Vladimir Grishagin; Alexander Gergel Pages: 35 - 51 Abstract: Abstract
Methods for solving the multidimensional multiextremal optimization problems using the nested optimization scheme are considered. A novel approach for solving the multidimensional multiextremal problems based on the adaptive nested optimization has been proposed. This approach enables to develop methods of the global optimum search which are more efficient in comparison with the ones on the base of the traditional nested optimization scheme. The new approach provides advantages due to better usage of the information on the problem in the course of optimization. A general scheme of a adaptive nested optimization is described. A theoretical substantiation of the method convergence is given for the case when for solving the univariate subproblems within the nested scheme an information algorithm of global search is used. Results of numerical experiments on the well-known classes of the test multiextremal functions confirming the efficiency of the proposed scheme are presented. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0355-7 Issue No:Vol. 66, No. 1 (2016)

Authors:Alexandr Yu. Gornov; Tatiana S. Zarodnyuk; Evgeniya A. Finkelstein; Anton S. Anikin Pages: 53 - 64 Abstract: Abstract
A numerical method of a two-dimensional non-linear controllable system reachable set boundary approximation is considered. In order to approximate the boundary right piecewise linear closed contours are used: a set of broken lines on a plane. As an application of the proposed technique a method of finding linear functional global extremum is described, including its use for systems with arbitrary dimensionality. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0346-8 Issue No:Vol. 66, No. 1 (2016)

Authors:Michael Khachay; Katherine Neznakhina Pages: 65 - 82 Abstract: Abstract
The cycle cover problem is a combinatorial optimization problem, which is to find a minimum cost cover of a given weighted digraph by a family of vertex-disjoint cycles. We consider a special case of this problem, where, for a fixed number k, all feasible cycle covers are restricted to be of the size k. We call this case the minimum weight k-size cycle cover problem (Min-k-SCCP). Since each cycle in a cover can be treated as a tour of some vehicle visiting an appropriate set of clients, the problem in question is closely related to the vehicle routing problem. Moreover, the studied problem is a natural generalization of the well-known traveling salesman problem (TSP), since the Min-1-SCCP is equivalent to the TSP. We show that, for any fixed
\(k>1\)
, the Min-k-SCCP is strongly NP-hard in the general setting. The Metric and Euclidean special cases of the problem are intractable as well. Also, we prove that the Metric Min-k-SCCP belongs to APX class and has a 2-approximation polynomial-time algorithm, even if k is not fixed. For the Euclidean Min-2-SCCP in the plane, we present a polynomial-time approximation scheme extending the famous result obtained by S. Arora for the Euclidean TSP. Actually, for any fixed
\(c>1\)
, the scheme finds a
\((1+1/c)\)
-approximate solution of the Euclidean Min-2-SCCP in
\(O(n^3(\log n)^{O(c)})\)
time. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0391-3 Issue No:Vol. 66, No. 1 (2016)

Authors:N. N. Novitsky; A. V. Lutsenko Pages: 83 - 94 Abstract: Abstract
The paper addresses an optimization problem of hydraulic conditions of heat supply systems. The research shows that when the main methods of operation control, including the control of the number of connected pumps at pumping stations, are used this problem is reduced to a mixed discrete-continuous programming problem which involves a nonlinear objective function, nonlinear equality constraints and simple inequalities. The paper presents the basic principles of the methods for calculation of feasible and optimal conditions on the basis of continuous variables as a constituent of the suggested technique for solving the general problem. Consideration is given to four possible strategies to fraction and cut the variants while searching for solutions on the basis of discrete variables. The results of computational experiments illustrating the comparative efficiency of different strategies are presented. PubDate: 2016-09-01 DOI: 10.1007/s10898-016-0403-y Issue No:Vol. 66, No. 1 (2016)

Authors:E. A. Nurminski Pages: 95 - 110 Abstract: Abstract
It is shown in this paper that under strict complementarity condition, a linear programming problem can be solved by a single orthogonal projection operation onto the cone generated by rows of constraint matrix and corresponding right-hand sides. The efficient projection procedure with the finite termination is provided and computational experiments are reported. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0337-9 Issue No:Vol. 66, No. 1 (2016)

Authors:Sergey P. Shary Pages: 111 - 126 Abstract: Abstract
The work is devoted to application of global optimization in data fitting problem under interval uncertainty. Parameters of the linear function that best fits intervally defined data are taken as the maximum point for a special (“recognizing”) functional which is shown to characterize consistency between the data and parameters. The new data fitting technique is therefore called “maximum consistency method”. We investigate properties of the recognizing functional and present interpretation of the parameter estimates produced by the maximum consistency method. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0340-1 Issue No:Vol. 66, No. 1 (2016)

Authors:Igor Vasilyev; Maurizio Boccia; Saïd Hanafi Pages: 127 - 150 Abstract: Abstract
Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated
\(p\)
-median problem and capacitated network location problem to optimality. PubDate: 2016-09-01 DOI: 10.1007/s10898-015-0294-3 Issue No:Vol. 66, No. 1 (2016)

Authors:Marco Locatelli Pages: 637 - 655 Abstract: Abstract
In this paper we discuss how to derive the non polyhedral convex envelopes for some functions, called 1-convex throughout the paper, over boxes. The main result is about n-dimensional 1-convex functions, but we get to it by first discussing in detail some special cases, namely functions
\(xyz^\delta \)
,
\(\delta >1\)
, and, next, more general trivariate functions. The relation between the class of functions investigated in this paper and other classes investigated in the existing literature is discussed. PubDate: 2016-08-01 DOI: 10.1007/s10898-016-0409-5 Issue No:Vol. 65, No. 4 (2016)

Authors:William W. Hager; Dzung T. Phan; Jiajie Zhu Pages: 657 - 676 Abstract: Abstract
We consider concave minimization problems over nonconvex sets. Optimization problems with this structure arise in sparse principal component analysis. We analyze both a gradient projection algorithm and an approximate Newton algorithm where the Hessian approximation is a multiple of the identity. Convergence results are established. In numerical experiments arising in sparse principal component analysis, it is seen that the performance of the gradient projection algorithm is very similar to that of the truncated power method and the generalized power method. In some cases, the approximate Newton algorithm with a Barzilai–Borwein Hessian approximation and a nonmonotone line search can be substantially faster than the other algorithms, and can converge to a better solution. PubDate: 2016-08-01 DOI: 10.1007/s10898-016-0402-z Issue No:Vol. 65, No. 4 (2016)

Authors:Chungen Shen; Lei-Hong Zhang; Wei Liu Pages: 677 - 708 Abstract: Abstract
This paper presents a stabilized filter sequential quadratic programming (SQP) method for the general nonlinear optimization problems. The technique of stabilizing the inner quadratic programmings is an efficient strategy for the degenerate problem and brings the local superlinear convergence, while the integrated filter technique works effectively and guarantees the global convergence. The new algorithm works on both the primal and dual variables and solves the problem within the computational complexity comparable to the classical SQP algorithm. For the convergence, we show that (1) it converges either to a Karush–Kuhn–Tucker point at which the cone-continuity property holds, or to a stationary point in the sense of minimizing the constraint violation, and (2) under some second-order sufficient conditions, it converges locally superlinearly without any constraint qualifications. Our preliminary numerical results on a set of CUTEr test problems as well as on degenerate problems demonstrate the efficiency of the new algorithm. PubDate: 2016-08-01 DOI: 10.1007/s10898-015-0400-6 Issue No:Vol. 65, No. 4 (2016)

Authors:E. G. Birgin; R. D. Lobato; J. M. Martínez Pages: 709 - 743 Abstract: Abstract
In this paper, continuous and differentiable nonlinear programming models and algorithms for packing ellipsoids in the n-dimensional space are introduced. Two different models for the non-overlapping and models for the inclusion of ellipsoids within half-spaces and ellipsoids are presented. By applying a simple multi-start strategy combined with a clever choice of starting guesses and a nonlinear programming local solver, illustrative numerical experiments are presented. PubDate: 2016-08-01 DOI: 10.1007/s10898-015-0395-z Issue No:Vol. 65, No. 4 (2016)

Authors:Hark-Chin Hwang; Hyun-Soo Ahn; Philip Kaminsky Pages: 777 - 799 Abstract: Abstract
We model the two-stage production-capacitated lot-sizing problem as a concave minimum cost network flow problem and characterize the possible patterns of flow between successive periods in which transportation occurs. We demonstrate that production and transportation decisions can be made based only on the local state of transportation patterns between successive transportation periods. Utilizing this observation together with the insight that it is not necessary to consider transportation decisions between transportation periods, we provide a novel improved
\(O(T^6)\)
algorithm (where T is the length of the planning horizon). We extend this approach to special cases, and develop an
\(O(T^5)\)
algorithm for the case with non-speculative costs, and an
\(O(T^4)\)
algorithm for the case with linear costs. PubDate: 2016-08-01 DOI: 10.1007/s10898-015-0392-2 Issue No:Vol. 65, No. 4 (2016)

Authors:Zhao Zhang; Shuangshuang Li; Hong-Jian Lai; Ding-Zhu Du Pages: 801 - 811 Abstract: Abstract
In a partial inverse combinatorial problem, given a partial solution, the goal is to modify data as small as possible such that there exists an optimal solution containing the given partial solution. In this paper, we study a constraint version of the partial inverse matroid problem in which the weight can only be increased. Two polynomial time algorithms are presented for this problem. PubDate: 2016-08-01 DOI: 10.1007/s10898-016-0412-x Issue No:Vol. 65, No. 4 (2016)

Authors:Julliany S. Brandão; Thiago F. Noronha; Celso C. Ribeiro Pages: 813 - 835 Abstract: Abstract
Given a set of lightpath requests, the problem of routing and wavelength (RWA) assignment in wavelength division multiplexing (WDM) optical networks consists in routing a subset of these requests and assigning a wavelength to each of them, such that two lightpaths that share a common link are assigned to different wavelengths. There are many variants of this problem in the literature. We focus in the variant in which the objective is to maximize the number of requests that may be accepted, given a limited set of available wavelengths. This problem is called max-RWA and it is of practical and theoretical interest, because algorithms for this variant can be extended for other RWA problems that arise from the design of WDM optical networks. A number of exact algorithms based on integer programming formulations have been proposed in the literature to solve max-RWA, as well as algorithms to provide upper bounds to the optimal solution value. However, the algorithms based on the state-of-the-art formulations in the literature cannot solve the largest instances to optimality. For these instances, only upper bounds to the value of the optimal solutions are known. The literature on heuristics for max-RWA is short and focus mainly on solving small size instances with up to 27 nodes. In this paper, we propose new greedy constructive heuristics and a biased random-key genetic algorithm, based on the best of the proposed greedy heuristics. Computational experiments showed that the new heuristic outperforms the best ones in literature. Furthermore, for the largest instances in the literature where only upper bounds to the value of the optimal solutions are known, the average optimality gap of the best of the proposed heuristics is smaller than 4 %. PubDate: 2016-08-01 DOI: 10.1007/s10898-015-0389-x Issue No:Vol. 65, No. 4 (2016)

Authors:Ignacio Araya; Victor Reyes Pages: 837 - 866 Abstract: Abstract
Interval Branch and Bound algorithms are used to solve rigorously continuous constraint satisfaction and constrained global optimization problems. In this paper, we explain the basic principles behind interval Branch and Bound algorithms. We detail the main components and describe issues that should be considered to improve the efficiency of the algorithms. PubDate: 2016-08-01 DOI: 10.1007/s10898-015-0390-4 Issue No:Vol. 65, No. 4 (2016)

Abstract: Abstract
An approach for solving quasi-equilibrium problems (QEPs) is proposed relying on gap functions, which allow reformulating QEPs as global optimization problems. The (generalized) smoothness properties of a gap function are analysed and an upper estimate of its Clarke directional derivative is given. Monotonicity assumptions on both the equilibrium and constraining bifunctions are a key tool to guarantee that all the stationary points of a gap function actually solve QEP. A few classes of constraints satisfying such assumptions are identified covering a wide range of situations. Relying on these results, a descent method for solving QEP is devised and its convergence proved. Finally, error bounds are given in order to guarantee the boundedness of the sequence generated by the algorithm. PubDate: 2016-08-23 DOI: 10.1007/s10898-016-0458-9

Authors:Qunfeng Liu; Guang Yang; Zhongzhi Zhang; Jinping Zeng Abstract: Abstract
DIRECT is derivative-free global-search algorithm has been found to perform robustly across a wide variety of low-dimensional test problems. The reason DIRECT’s robustness is its lack of algorithmic parameters that need be “tuned” to make the algorithm perform well. In particular, there is no parameter that determines the relative emphasis on global versus local search. Unfortunately, the same algorithmic features that enable DIRECT to perform so robustly have a negative side effect. In particular, DIRECT is usually quick to get close to the global minimum, but very slow to refine the solution to high accuracy. This is what we call DIRECT’s “eventually inefficient behavior.” In this paper, we outline two root causes for this undesirable behavior and propose modifications to eliminate it. The paper builds upon our previously published “MrDIRECT” algorithm, which we can now show only addressed the first root cause of the “eventually inefficient behavior.” The key contribution of the current paper is a further enhancement that allows MrDIRECT to address the second root cause as well. To demonstrate the effectiveness of the enhanced MrDIRECT, we have identified a set of test functions that highlight different situations in which DIRECT has convergence issues. Extensive numerical work with this test suite demonstrates that the enhanced version of MrDIRECT does indeed improve the convergence rate of DIRECT. PubDate: 2016-08-12 DOI: 10.1007/s10898-016-0447-z