An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations

In this paper we propose an exact algorithm for the Resource Constrained Project Scheduling Problem (RCPSP) with generalized precedence relationships (GPRs) and minimum makespan objective. For the RCPSP with GPRs we give a new mathematical formulation and a branch and bound algorithm exploiting such a formulation. The exact algorithm takes advantage also of a lower bound based on a Lagrangian relaxation of the same mathematical formulation. We provide an extensive experimentation and a comparison with known lower bounds and competing exact algorithms drawn from the state of the art.     

Apical-dominant particle swarm optimization

Particle swarm optimization （PSO） is a new stochastic population-based search methodology by simulating the animal social behaviors such as birds flocking and fish schooling. Many improvements have been proposed within the framework of this biological assumption. However, in this paper, the search pattern of PSO is used to model the branch growth process of natural plants. It provides a different potential manner from artificialplant. To illustrate the effectiveness of this new model, apical dominance phenomenon is introduced to construct a novel variant by emphasizing the influence of the phototaxis. In this improvement, the population is divided into three different kinds of buds associated with their performances. Furthermore, a mutation strategy is applied to enhance the ability escaping from a local optimum. Simulation results demonstrate good performance of the new method when solving high-dimensional multi-modal problems.     

Decomposition Methods for Solving Nonconvex Quadratic Programs via Branch and Bound*

The aim of this paper is to suggest branch and bound schemes, based on a relaxation of the objective function, to solve nonconvex quadratic programs over a compact polyhedral feasible region. The various schemes are based on different d.c. decomposition methods applied to the quadratic objective function. To improve the tightness of the relaxations, we also suggest solving the relaxed problems with an algorithm based on the so called “optimal level solutions” parametrical approach. *This paper has been partially supported by M.I.U.R. and C.N.R.     

豫北某市畜群结构非线性优化模型分析

本文从当豫北某市饲料和饲养力水平无法再提高出发，通过对畜群结构分析，建立了畜群结构非线性优化模型，通过对模型线性化和分支定界算法对模型进行求解，并给出了实例，最后对模型进行了分析和展望．     

Exact and heuristic solutions of the global supply chain problem with transfer pricing

We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx [Vidal, C.J., Goetschalckx, M., 2001. A global supply chain model with transfer pricing and transportation cost allocation. European Journal of Operational Research 129 (1), 134–158] proposed a bilinear model of this problem and solved it by an Alternate heuristic. We propose a reformulation of this model reducing the number of bilinear terms and accelerating considerably the exact solution. We also present three other solution methods: an implementation of Variable Neighborhood Search (VNS) designed for any bilinear model, an implementation of VNS specifically designed for the problem considered here and an exact method based on a branch and cut algorithm. The solution methods are tested on artificial instances. These results show that our implementation of VNS outperforms the two other heuristics. The exact method found the optimal solution of all small instances and of 26% of medium instances.     

Exact solution procedures for the balanced unidirectional cyclic layout problem

In this paper, we consider the balanced unidirectional cyclic layout problem (BUCLP) arising in the determination of workstation locations around a closed loop conveyor system, in the allocation of cutting tools on the sites around a turret, in the positioning of stations around a unidirectional single loop AGV path. BUCLP is known to be NP-Complete. One important property of this problem is the balanced material flow assumption where the material flow is conserved at every workstation. We first develop a branch-and-bound procedure by using the special material flow property of the problem. Then, we propose a dynamic programming algorithm, which provides optimum solutions for instances with up to 20 workstations due to memory limitations. The branch and bound procedure can solve problems with up to 50 workstations.     

A BSSS algorithm for the single facility location problem in two regions with different norms

Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.     

LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINLPs

We present a Branch and Cut algorithm of the software package LaGO to solve nonconvex mixed-integer nonlinear programs (MINLPs). A linear outer approximation is constructed from a convex relaxation of the problem. Since we do not require an algebraic representation of the problem, reformulation techniques for the construction of the convex relaxation cannot be applied, and we are restricted to sampling techniques in case of nonquadratic nonconvex functions. The linear relaxation is further improved by mixed-integer-rounding cuts. Also box reduction techniques are applied to improve efficiency. Numerical results on medium size test problems are presented to show the efficiency of the method.     

Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times

We consider an extension of the optimal searcher path problem (OSP), where a searcher moving through a discretised environment may now need to spend a non-uniform amount of time travelling from one region to another before being able to search it for the presence of a moving target. In constraining not only where but when the search of each cell can take place, the problem more appropriately models the search of environments which cannot be easily partitioned into equally sized cells. An existing OSP bounding method in literature, the MEAN bound, is generalised to provide bounds for solving the new problem in a branch and bound framework. The main contribution of this paper is an enhancement, discounted MEAN (DMEAN), which greatly tightens the bound for the new and existing problems alike with almost no additional computation. We test the new algorithm against existing OSP bounding methods and show it leads to faster solution times for moving target search problems.     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.