An Algorithm for Solving a Resource Allocation Problem

The paper discusses the solution of a resource allocation problem and a new method for solving a special case of the problem. An algorithm for solving the general problem is presented, and computational experience comparing it with existing methods is given.     

On Reducing a Resource Allocation Problem to a Single One-Dimensional Minimization of a Differentiable Convex Function

By very elementary arguments on Lagrangian duality it is shown that the classical resource allocation problem can be reduced to a single one-dimensional minimization of a differentiable convex function. An optimality condition is given that can be used for testing optimality of some proposed heuristic solutions.     

凸多乘积问题的完全多项式时间近似算法

针对凸多乘积问题,提出一种求其全局最优解的近似算法.首先,通过引入参量获得一个等价问题,然后估计问题中每一乘积项的上下界,进而借助网格结点,获得一些凸规划问题,通过求解这些凸规划问题获得原问题的近似最优解.最后,给出了该算法的收敛性证明和计算复杂性分析.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

满足多断点折扣费用函数的经济批量问题的多项式时间算法

在进货费用为全单位数量折扣函数的基础上,建立了一类有限时期内的经济批量问题.通过分析最优解的性质,设计了一个计算复杂性为O(T3+mT2)的动态规划算法,其中m为全单位数量折扣费用中的断点数,T为时期数.最后的算例进一步说明了该算法的有效性.     

一种新的求解凸二次规划的原始-对偶多项式内点算法

对凸二次规划问题提出了一种新的原始-对偶路径跟踪算法,算法迭代方向的求解是不同于传统的牛顿法,而是借助于一种新的工具找到搜寻方向.最后证明了算法具有多项式复杂性.     

凸可行问题的一种强收敛算法

无限维Hilbert空间中,解凸可行问题的平行投影算法通常是弱收敛的.本文对一般的平行投影算法进行改进,设计了一种解凸可行问题的具有强收敛性的新算法.该算法主要是在原有算法基础上引入了一个参数序列,在参数序列满足一定的控制条件下保证了算法的强收敛性.为了简单证明算法的强收敛性,我们构建了一个新的积空间,然后把原空间的这种改进平行投影算法转换为积空间中的交替投影算法.这样,改进的平行投影算法的强收敛性就可以通过交替投影算法的收敛性证明得到.     

Efficient Resource Allocation with Non-Concave Objective Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximization version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with non-concave functions is difficult. In this article we show that for fairly well-shaped non-concave objective functions, the optimal solution can be computed efficiently. Our main enabling ingredient is an algorithm for aggregating two objective functions, where the cost depends on the complexity of the two involved functions. As a measure of complexity of a function, we use the number of subintervals that are convex or concave.     

An Algorithm for the Allocation Problem

This paper* sets out a procedure for solving allocation problems, on different lines from procedures based on linear programming.     

A Bilinear Algorithm for Optimizing a Linear Function over the Efficient Set of a Multiple Objective Linear Programming Problem

The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set EP nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported.     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

交替最小化算法求解强凸函数与弱凸函数和的极小值问题

交替最小化算法(简称AMA)最早由[SIAM,Control Optim.,1991,29(1):119-138]提出,并能用于求解强凸函数与凸函数和的极小值问题.本文直接利用AMA算法来求解强凸函数与弱凸函数和的极小值问题.在强凸函数的模大于弱凸函数的模的假设下,我们证明了AMA生成的点列全局收敛到优化问题的解,并且...     

论一类资源最优配置问题及应用

本文考虑了一类资源最优配置问题.应用Kuhn-Tucher定理得到了这类问题最优解的充要条件.我们应用这个条件来考虑一类从工业投资、教育投资等问题中导出的最优投资模型,得到了这个问题最优解的充要条件,应用这个条件导出了求解这个模型的具有时间复杂度为o(mn)的多项式型新算法.     

A Hybrid Particle Swarm Optimization Algorithm for the Redundancy Allocation Problem

The Redundancy Allocation Problem generally involves the selection of components with multiple choices and redundancy levels that produce maximum system reliability given various system level constraints as cost and weight. In this paper we investigate the series–parallel redundant reliability problems, when a mixing of components was considered. In this type of problem both the number of redundancy components and the corresponding component reliability in each subsystem are to be decided simultaneously so as to maximise the reliability of system. A hybrid algorithm is based on particle swarm optimization and local search algorithm. In addition, we propose an adaptive penalty function which encourages our algorithm to explore within the feasible region and near feasible region, and discourage search beyond that threshold. The effectiveness of our proposed hybrid PSO algorithm is proved on numerous variations of three different problems and compared to Tabu Search and Multiple Weighted Objectives solutions.     

A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

A Polynomial Time Algorithm to Compute the Abelian Kernel of a Finite Monoid

Abstract. The time complexity of the best previously known algorithm to compute the Abelian kernel of a finite monoid with a fixed number of generators is exponential. In this paper we use results on subgroups of the free Abelian group and constructions on labeled graphs to develop a polynomial time algorithm for this problem.