Authors:Douglas S. Gonçalves; Antonio Mucherino; Carlile Lavor; Leo Liberti Pages: 525 - 545 Abstract: We discuss a discretization-based solution approach for a classic problem in global optimization, namely the distance geometry problem (DGP). We focus our attention on a particular class of the DGP which is concerned with the identification of the conformation of biological molecules. Among the many relevant ideas for the discretization of the DGP in the literature, we identify the most promising ones and address their inherent limitations to application to this class of problems. The result is an improved method for estimating 3D structures of small proteins based only on the knowledge of some distance restraints between pairs of atoms. We present computational results showcasing the usefulness of the new proposed approach. Proteins act on living cells according to their geometric and chemical properties: finding protein conformations can be very useful within the pharmaceutical industry in order to synthesize new drugs. PubDate: 2017-11-01 DOI: 10.1007/s10898-016-0493-6 Issue No:Vol. 69, No. 3 (2017)

Authors:Juan F. R. Herrera; José M. G. Salmerón; Eligius M. T. Hendrix; Rafael Asenjo; Leocadio G. Casado Pages: 547 - 560 Abstract: Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0508-y Issue No:Vol. 69, No. 3 (2017)

Authors:Ana Maria A. C. Rocha; M. Fernanda P. Costa; Edite M. G. P. Fernandes Pages: 561 - 585 Abstract: This paper presents a coercive smoothed penalty framework for nonsmooth and nonconvex constrained global optimization problems. The properties of the smoothed penalty function are derived. Convergence to an \(\varepsilon \) -global minimizer is proved. At each iteration k, the framework requires the \(\varepsilon ^{(k)}\) -global minimizer of a subproblem, where \(\varepsilon ^{(k)} \rightarrow \varepsilon \) . We show that the subproblem may be solved by well-known stochastic metaheuristics, as well as by the artificial fish swarm (AFS) algorithm. In the limit, the AFS algorithm convergence to an \(\varepsilon ^{(k)}\) -global minimum of the real-valued smoothed penalty function is guaranteed with probability one, using the limiting behavior of Markov chains. In this context, we show that the transition probability of the Markov chain produced by the AFS algorithm, when generating a population where the best fitness is in the \(\varepsilon ^{(k)}\) -neighborhood of the global minimum, is one when this property holds in the current population, and is strictly bounded from zero when the property does not hold. Preliminary numerical experiments show that the presented penalty algorithm based on the coercive smoothed penalty gives very competitive results when compared with other penalty-based methods. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0504-2 Issue No:Vol. 69, No. 3 (2017)

Authors:Richard Oberdieck; Nikolaos A. Diangelakis; Styliani Avraamidou; Efstratios N. Pistikopoulos Pages: 587 - 606 Abstract: In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem. PubDate: 2017-11-01 DOI: 10.1007/s10898-016-0463-z Issue No:Vol. 69, No. 3 (2017)

Authors:G. Ortega; E. Filatovas; E. M. Garzón; L. G. Casado Pages: 607 - 627 Abstract: Evolutionary multi-objective optimization algorithms aim at finding an approximation of the Pareto set. For hard to solve problems with many conflicting objectives, the number of functions evaluations to represent the Pareto front can be large and time consuming. Parallel computing can reduce the wall-clock time of such algorithms. Previous studies tackled the parallelization of a particular evolutionary algorithm. In this research, we focus on improving one of the most time consuming procedures—the non-dominated sorting—, which is used in the state-of-the-art multi-objective genetic algorithms. Here, three parallel versions of the non-dominated sorting procedure are developed: (1) a multicore (based on Pthreads); (2) a Graphic Processing Unit (GPU) (based on CUDA interface); and (3) a hybrid (based on Pthreads and CUDA). The user can select the most suitable option to efficiently compute the non-dominated sorting procedure depending on the available hardware. Results show that the use of GPU computing provides a substantial improvement in terms of performance. The hybrid approach has the best performance when a good load balance is established among cores and GPU. PubDate: 2017-11-01 DOI: 10.1007/s10898-016-0468-7 Issue No:Vol. 69, No. 3 (2017)

Authors:Rohit Kannan; Paul I. Barton Pages: 629 - 676 Abstract: Deterministic branch-and-bound algorithms for continuous global optimization often visit a large number of boxes in the neighborhood of a global minimizer, resulting in the so-called cluster problem (Du and Kearfott in J Glob Optim 5(3):253–265, 1994). This article extends previous analyses of the cluster problem in unconstrained global optimization (Du and Kearfott 1994; Wechsung et al. in J Glob Optim 58(3):429–438, 2014) to the constrained setting based on a recently-developed notion of convergence order for convex relaxation-based lower bounding schemes. It is shown that clustering can occur both on nearly-optimal and nearly-feasible regions in the vicinity of a global minimizer. In contrast to the case of unconstrained optimization, where at least second-order convergent schemes of relaxations are required to mitigate the cluster problem when the minimizer sits at a point of differentiability of the objective function, it is shown that first-order convergent lower bounding schemes for constrained problems may mitigate the cluster problem under certain conditions. Additionally, conditions under which second-order convergent lower bounding schemes are sufficient to mitigate the cluster problem around a global minimizer are developed. Conditions on the convergence order prefactor that are sufficient to altogether eliminate the cluster problem are also provided. This analysis reduces to previous analyses of the cluster problem for unconstrained optimization under suitable assumptions. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0531-z Issue No:Vol. 69, No. 3 (2017)

Authors:Jon Lee; Daphne Skipper Pages: 677 - 697 Abstract: In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ( \(w^p\) with \(0<p<1\) ) and their increasing concave relatives. We provide (i) a sufficient condition (which applies to functions more general than root functions) for our smoothing to be increasing and concave, (ii) a proof that when \(p=1/q\) for integers \(q\ge 2\) , our smoothing lower bounds the root function, (iii) substantial progress (i.e., a proof for integers \(2\le q\le 10{,}000\) ) on the conjecture that our smoothing is a sharper bound on the root function than the natural and simpler “shifted root function”, and (iv) for all root functions, a quantification of the superiority (in an average sense) of our smoothing versus the shifted root function near 0. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0533-x Issue No:Vol. 69, No. 3 (2017)

Authors:Özgür Özpeynirci Pages: 699 - 712 Abstract: In this study, we consider the nadir points of multiobjective integer programming problems. We introduce new properties that restrict the possible locations of the nondominated points necessary for computing the nadir points. Based on these properties, we reduce the search space and propose an exact algorithm for finding the nadir point of multiobjective integer programming problems. We present an illustrative example on a three objective knapsack problem. We conduct computational experiments and compare the performances of two recent algorithms and the proposed algorithm. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0534-9 Issue No:Vol. 69, No. 3 (2017)

Authors:Kameng Nip; Zhenbo Wang; Zizhuo Wang Pages: 713 - 725 Abstract: We introduce a variant of the knapsack problem, in which the weights of items are also variables but must satisfy a system of linear constraints, and the capacity of knapsack is given and known. We discuss two models: (1) the value of each item is given; (2) the value-to-weight ratio of each item is given. The goal is to determine the weight of each item, and to find a subset of items such that the total weight is no more than the capacity and the total value is maximized. We provide several practical application scenarios that motivate our study, and then investigate the computational complexity and corresponding algorithms. In particular, we show that if the number of constraints is a fixed constant, then both problems can be solved in polynomial time. If the number of constraints is an input, then we show that the first problem is NP-Hard and cannot be approximated within any constant factor unless \(\mathrm{P}= \mathrm{NP}\) , while the second problem is NP-Hard but admits a polynomial time approximation scheme. We further propose approximation algorithms for both problems, and extend the results to multiple knapsack cases with a fixed number of knapsacks and identical capacities. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0540-y Issue No:Vol. 69, No. 3 (2017)

Authors:Giovanni Felici; Kumar Parijat Tripathi; Daniela Evangelista; Mario Rosario Guarracino Pages: 727 - 744 Abstract: The analysis of high throughput gene expression patients/controls experiments is based on the determination of differentially expressed genes according to standard statistical tests. A typical bioinformatics approach to this problem is composed of two separate steps: first, a subset of genes with altered expression level is identified; then the pathways which are statistically enriched by those genes are selected, assuming they play a relevant role for the biological condition under study. Often, the set of selected pathways contains elements that are not related to the condition. This is due to the fact that the statistical significance is not sufficient for biological relevance. To overcome these problems, we propose a method based on a large mixed integer program that implements a new feature selection model to simultaneously identify the genes whose over- and under-expressions, combined together, discriminate different cancer subtypes, as well as the pathways that are enriched by these genes. The innovation in this model is the solutions are driven towards the enrichment of pathways. That may indeed introduce a bias in the search; such a bias is counter-balanced by a wide exploration of the solution space, varying the involved parameters in their feasible region, and then using a global optimization approach. The conjoint analysis of the pool of solutions obtained by this exploration should indeed provide a robust final set of genes and pathways, overcoming the potential drawbacks of relying solely on statistical significance. Experimental results on transcriptomes for different types of cancer from the Cancer Genome Atlas are presented. The method is able to identify crisp relations between the considered subtypes of cancer and few selected pathways, eventually validated by the biological analysis. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0530-0 Issue No:Vol. 69, No. 3 (2017)

Authors:Y. Shi; H. D. Tuan; H. Tuy; S. Su Pages: 745 - 760 Abstract: The optimal power flow (OPF) problem for power transmission networks is an NP-hard optimization problem with nonlinear constraints on complex bus voltages. The existing nonlinear solvers may fail in yielding a feasible point. Semi-definite relaxation (SDR) could provide the global solution only when the matrix solution of the relaxed semi-definite program (SDP) is of rank-one, which does not hold in general. Otherwise, the point found by SDR is infeasible. High-order SDR has recently been used to find the global solution, which leads to explosive growth of the matrix variable dimension and semi-definite constraints. Consequently, it is suitable only for OPF over very small networks with a few buses. In this paper, we follow our previously developed nonsmooth optimization approach to address this difficult OPF problem, which is an iterative process to generate a sequence of improved points that converge to a global solution in many cases. Each iteration calls an SDP of moderate dimension. Simulations are provided to demonstrate the efficiency of our approach. PubDate: 2017-11-01 DOI: 10.1007/s10898-017-0538-5 Issue No:Vol. 69, No. 3 (2017)

Authors:Khushboo; C. S. Lalitha Abstract: The aim of this paper is to study characterizations of minimal and approximate minimal solutions for a unified vector optimization problem in a Hausdorff real topological vector space. These characterizations have been obtained via scalarizations which are based on general order representing and order preserving properties. A nonlinear scalarization based on Gerstewitz function is shown to be a particular case of the proposed scalarizations. Furthermore, in the setting of normed space, characterizations are given for minimal solutions by using scalarization function based on the oriented distance function. Finally, under appropriate assumptions it is shown that this function satisfies order representing and order preserving properties. PubDate: 2017-11-10 DOI: 10.1007/s10898-017-0582-1

Authors:Xinbao Liu; Xiaofei Qian; Jun Pei; Panos M. Pardalos Abstract: We study a differential game of information security investment and information sharing in a market consisting of n complementary firms. Two game approaches, the non-cooperative game and the totally cooperative game, are employed to investigate the steady state strategy of each firm. Under certain conditions, a unique steady state can be obtained for both games. We find that the steady state security investment and information sharing level are not always less in the non-cooperative game than that in the totally cooperative game. In addition, some theoretical analyses are made on the impacts of the complementarity degree and industry size on firms’ steady state strategies for both games. Finally, some numerical experiments are conducted to give some insights related to the instantaneous profit in the steady state. It can be found that a firm will obtain more instantaneous profit in the steady state of the totally cooperative game than that of the non-cooperative game, which emphasizes the importance of coordinating strategies. The effects of the complementarity degree and industry size on the instantaneous profits in the steady state are also obtained through the numerical experiment results. PubDate: 2017-11-10 DOI: 10.1007/s10898-017-0585-y

Authors:E. Allevi; L. Boffino; M. E. De Giuli; G. Oggioni Abstract: A large part of the European natural gas imports originates from unstable regions exposed to the risk of supply failure due to economical and political reasons. This has increased the concerns on the security of supply in the European natural gas market. In this paper, we analyze the security of external supply of the Italian gas market that mainly relies on natural gas imports to cover its internal demand. To this aim, we develop an optimization problem that describes the equilibrium state of a gas supply chain where producers, mid-streamers, and final consumers exchange natural gas and liquefied natural gas. Both long-term contracts (LTCs) and spot pricing systems are considered. Mid-streamers are assumed to be exposed to the external supply risk, which is estimated with indicators that we develop starting from those already existing in the literature. In addition, we investigate different degrees of mid-streamers’ flexibility by comparing a situation where mid-streamers fully satisfy the LTC volume clause (“No FLEX” assumption) to a case where the fulfillment of this volume clause is not compulsory (“FLEX” assumption). Our analysis shows that, in the “No FLEX” case, mid-streamers do not significantly change their supplying choices even when the external supply risk is considered. Under this assumption, they face significant profit losses that, instead, disappear in the “FLEX” case when mid-streamers are more flexible and can modify their supply mix. However, the “FLEX” strategy limits the gas availability in the supply chain leading to a curtailment of the social welfare. PubDate: 2017-11-03 DOI: 10.1007/s10898-017-0584-z

Authors:Chunfeng Cui; Qingna Li; Liqun Qi; Hong Yan Abstract: Hypergraph matching is a fundamental problem in computer vision. Mathematically, it maximizes a polynomial objective function, subject to assignment constraints. In this paper, we reformulate the hypergraph matching problem as a sparse constrained optimization problem. By dropping the sparse constraint, we show that the resulting relaxation problem can recover the global minimizer of the original problem. This property heavily depends on the special structures of hypergraph matching. The critical step in solving the original problem is to identify the location of nonzero entries (referred to as the support set) in a global minimizer. Inspired by such observation, we apply the quadratic penalty method to solve the relaxation problem. Under reasonable assumptions, we show that the support set of the global minimizer in a hypergraph matching problem can be correctly identified when the number of iterations is sufficiently large. A projected gradient method is applied as a subsolver to solve the quadratic penalty subproblem. Numerical results demonstrate that the exact recovery of the support set indeed happens, and the proposed algorithm is efficient in terms of both accuracy and CPU time. PubDate: 2017-10-30 DOI: 10.1007/s10898-017-0583-0

Authors:Mehdi Karimi; Somayeh Moazeni; Levent Tunçel Abstract: We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. After introducing our approach, we develop interactive cutting-plane algorithms for robust optimization, based on concave and quasi-concave utility functions. In addition to practical advantages, due to the flexibility of our approach, we prove that under a theoretical framework proposed by Bertsimas and Sim (Oper Res 52:35–53, 2004), which establishes the existence of certain convex formulation of robust optimization problems, the robust optimal solutions generated by our algorithms are at least as desirable to the decision maker as any solution generated by many other robust optimization algorithms in the theoretical framework. We present some probabilistic bounds for feasibility of robust solutions and evaluate our approach by means of computational experiments. PubDate: 2017-10-30 DOI: 10.1007/s10898-017-0581-2

Authors:Leonardo Fontoura; Rafael Martinelli; Marcus Poggi; Thibaut Vidal Abstract: The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points. PubDate: 2017-10-27 DOI: 10.1007/s10898-017-0579-9

Authors:Radu Baltean-Lugojan; Ruth Misener Abstract: The standard pooling problem is a NP-hard subclass of non-convex quadratically-constrained optimization problems that commonly arises in process systems engineering applications. We take a parametric approach to uncovering topological structure and sparsity, focusing on the single quality standard pooling problem in its p-formulation. The structure uncovered in this approach validates Professor Christodoulos A. Floudas’ intuition that pooling problems are rooted in piecewise-defined functions. We introduce dominant active topologies under relaxed flow availability to explicitly identify pooling problem sparsity and show that the sparse patterns of active topological structure are associated with a piecewise objective function. Finally, the paper explains the conditions under which sparsity vanishes and where the combinatorial complexity emerges to cross over the P / NP boundary. We formally present the results obtained and their derivations for various specialized single quality pooling problem subclasses. PubDate: 2017-10-25 DOI: 10.1007/s10898-017-0577-y

Authors:Laura Scrimali; Cristina Mirabella Abstract: In this paper, we develop a cooperative game framework for modeling the pollution control problem in a time-dependent setting. We examine the situation in which different countries, aiming at reducing pollution emissions, coordinate both emissions and investment strategies to optimize jointly their welfare. We state the equilibrium conditions underlying the model and provide a formulation in terms of an evolutionary variational inequality. Then, by means of infinite dimensional duality tools, we prove the existence of Lagrange multipliers that play a fundamental role to describe countries’ decision-making processes. Finally, we discuss the existence of solutions and provide a numerical example. PubDate: 2017-10-25 DOI: 10.1007/s10898-017-0580-3

Authors:Rundong Du; Barry Drake; Haesun Park Abstract: A hybrid method called JointNMF is presented which is applied to latent information discovery from data sets that contain both text content and connection structure information. The new method jointly optimizes an integrated objective function, which is a combination of two components: the Nonnegative Matrix Factorization (NMF) objective function for handling text content and the Symmetric NMF (SymNMF) objective function for handling network structure information. An effective algorithm for the joint NMF objective function is proposed so that the efficient method of block coordinate descent framework can be utilized. The proposed hybrid method simultaneously discovers content associations and related latent connections without any need for postprocessing of additional clustering. It is shown that the proposed method can also be applied when the text content is associated with hypergraph edges. An additional capability of the JointNMF is prediction of unknown network information which is illustrated using several real world problems such as citation recommendations of papers and leader detection in organizations. The proposed method can also be applied to general data expressed with both feature space vectors and pairwise similarities and can be extended to the case with multiple feature spaces or multiple similarity measures. Our experimental results illustrate multiple advantages of the proposed hybrid method when both content and connection structure information is available in the data for obtaining higher quality clustering results and discovery of new information such as unknown link prediction. PubDate: 2017-10-24 DOI: 10.1007/s10898-017-0578-x