Localization of diffusion sources in complex networks with sparse observations

Locating sources in a large network is of paramount importance to reduce the spreading of disruptive behavior. Based on the backward diffusion-based method and integer programming, we propose an efficient approach to locate sources in complex networks with limited observers. The results on model networks and empirical networks demonstrate that, for a certain fraction of observers, the accuracy of our method for source localization will improve as the increase of network size. Besides, compared with the previous method (the maximum–minimum method), the performance of our method is much better with a small fraction of observers, especially in heterogeneous networks. Furthermore, our method is more robust against noise environments and strategies of choosing observers.     

Multi-funnel optimization using Gaussian underestimation

In several applications, underestimation of functions has proven to be a helpful tool for global optimization. In protein–ligand docking problems as well as in protein structure prediction, single convex quadratic underestimators have been used to approximate the location of the global minimum point. While this approach has been successful for basin-shaped functions, it is not suitable for energy functions with more than one distinct local minimum with a large magnitude. Such functions may contain several basin-shaped components and, thus, cannot be underfitted by a single convex underestimator. In this paper, we propose using an underestimator composed of several negative Gaussian functions. Such an underestimator can be computed by solving a nonlinear programming problem, which minimizes the error between the data points and the underestimator in the L ¹ norm. Numerical results for simulated and actual docking energy functions are presented.     

The empirical behavior of sampling methods for stochastic programming

We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

Solving the maximum edge weight clique problem via unconstrained quadratic programming

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.     

一类灰色动态投入产出优化模型的设计及其在农业经济发展规划中的应用

本文应用灰色系统理论和方法，把动态Ｌｅｏｎｔｉｅｆ投入产出模型和线性规划结合起来，建立一种灰色动态投入产出优化模型，在山东省农业经济发展规划定量研究中，应用该模型取得比较满意的结果．     

Remarks on the Analytic Centers of Convex Sets

In this paper we analyze properties of the analytic centers for perturbed convex problems. In particular we study the continuity of convex regions with respect to such characteristics as boundedness, full dimensionality and the existence of an analytic centre. Furthermore, we state the necessary and sufficient conditions for the existence of the analytic centre for possibly unbounded regions and we show that the analytic centre is identical for any minimal representation of the convex set. We are also concerned with the limiting behaviour of the central path as it approaches the set of optimal solutions of the problem.     

Scalarization for characterization of approximate strong/weak/proper efficiency in multi-objective optimization

In this article, approximate solutions of multi-objective optimization problems are analysed. The notion of approximate solution suggested by Kutateladze is dealt with, and, utilizing different scalarization approaches, some necessary and sufficient conditions for ?-(strong, weak, proper) efficiency are provided. Almost all of the provided results are established without any convexity assumption.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Designing an optimal connected nature reserve

We consider a landscape divided into elementary cells, each of these cells containing some species to be protected. We search to select a set of cells to form a natural reserve in order to protect all the species present in the landscape. A species is considered protected if it is present in a certain number of cells of the reserve. There is an important spatial constraint concerning the set of selected cells: a species must be able to go from any cell to any cell without leaving the reserve. An integer linear programming model was proposed by Önal and Briers [2] for this reserve selection problem, but the size of the problems which can be handled by this model is limited: several hours of computation are required for solving instances with hundred of cells and hundred of species. Having proposed an improvement of this model which reduces appreciably the computation time, we propose another integer linear programming model, easy to carry out, which allows to obtain, in a few seconds of computation, optimal or near-optimal solutions for instances with hundred of cells and hundred of species. However, the computation time becomes prohibitive for instances with more than 200 cells and 100 species. But, this approach can be particularly useful to solve the problem, in an approximate way, by aggregation of cells as proposed by Önal and Briers [2].     

ON THE PROJECTION OF THE EFFICIENT SET AND POTENTIAL APPLICATIONS

Abstract

We study the efficient set X _E for a multiple objective linear program by using its projection into the linear space L spanned by the independent criteria. We show that in the orthogonally complementary space of L, the efficient points form a polyhedron, while in L an efficiency-equivalent polyhedron for the projection P(X _E ) of X _E can be constructed by algorithms of outer and inner approximation types. These algorithms can be also used for generating all extreme points of P(X _E ). Application to optimization over the efficient set for a multiple objective linear program is considered.