The Knapsack Sharing Problem: An Exact Algorithm

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.     

A multi-objective particle swarm for a flow shop scheduling problem

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particle's position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm, i.e. SPEA-II. The computational results show that the proposed MOPS performs better than the genetic algorithm, especially for the large-sized problems.     

智能组合预测方法及其应用

由于具有能以任意精度逼近任意复杂非线性函数的优良性能,神经网络在灰色系统预测中得到了较大的应用。在已有的研究基础上,针对灰色神经网络进化时容易陷入局部最优,参数修正受阻的问题,建立基于遗传粒子群混合算法优化的新型灰色神经网络模型。首先将灰色神经网络进行数学建模,以便于优化算法的应用;其次,综合遗传算法与粒子群算法的优点,构造一种混合算法,运用混合算法对灰色神经网络进行优化;最后通过日本入华游客数量预测的算例研究,比较新型灰色神经网络与灰色神经网络、单一算法优化的灰色神经网络的预测精度。所得结果表明,混合算法优化的新灰色神经网络具有更好的预测性能,在社会经济领域有着广泛的应用前景。     

A new effective branch-and-bound algorithm to the high order MIMO detection problem

This paper develops a branch-and-bound method based on a new convex reformulation to solve the high order MIMO detection problem. First, we transform the original problem into a \(\{-1,1\}\) constrained quadratic programming problem with the smallest size. The size of the reformulated problem is smaller than those problems derived by some traditional transformation methods. Then, we propose a new convex reformulation which gets the maximized average objective value as the lower bound estimator in the branch-and-bound scheme. This estimator balances very well between effectiveness and computational cost. Thus, the branch-and-bound algorithm achieves a high total efficiency. Several simulations are used to compare the performances of our method and other benchmark methods. The results show that this proposed algorithm is very competitive for high accuracy and relatively good efficiency.     

基于灰信息变元的泛函博弈模型研究

现实社会生活中存在局中人的博弈策略或收益值是变元（如时间、环境、空间、制度或相关其它变元）映射的一类博弈问题。本文从灰信息变元的角度给出了的泛函区间灰数的概念,设计了泛函区间灰数的表征形式,提供了泛函区间灰数之间的大小比较与运算法则。分析基于不确定信息的泛函博弈问题,并描述其形式与框架,可以展示不确定信息下博弈的特征、性质、战略表达形式。运用优化理论及其相关技术方法,设计基于不确定信息优化的求解算法,即通过研究和构造泛函博弈收益值的广义满秩扩充方阵求解最优博弈策略和博弈收益值问题,不仅为现实生活中的不确定信息问题提供新的解题思路,更为实际问题的解决提供新的方法参考。最后结合案例“盗版与打击盗版”问题通过计算机仿真对其博弈均衡结果进行详细的对比分析,说明了本文提出基于信息变元泛函博弈模型的科学性和计算结果的精确性。     

随机需求下联合选址-库存模型研究

研究了一类具有季节性需求特性的商品的联合选址-库存模型。在传统的无容量限制的固定费用设施选址问题中考虑了分销中心的运作库存和安全库存的影响,以及规模经济效应和风险分摊效应,同时考虑了季节性商品未来需求的不确定性,将订货决策作为模型的决策变量,建立了一类随机需求下以期望销售收益最大化为目标函数的联合选址-库存模型,拓展了已有的联合选址-库存模型。该模型是一个混合整数规划问题,给出了求解该问题的基于拉格朗日松弛算法的两阶段算法,最后通过随机生成四组不同规模的数值算例,得到的计算结果表明拉格朗日松弛算法可以有效地求解该问题。     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

Solving the maximum vertex weight clique problem via binary quadratic programming

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.     

综合面试中的均衡分组方法

本文针对综合面试中的分组问题,首先分析了分组对综合面试结果的影响,提出了均衡分组的思想;在此基础上,提出了综合面试中的均衡分组方法,该方法构建了双目标优化模型,并开发了一个求解问题的遗传算法,该算法还可以解决一类分组问题;最后,给出算例说明方法的应用及可行性。     

Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of \(\alpha + 4\) for the robust fault-tolerant facility location problem, which is best so far.     

Exact approaches for the pickup and delivery problem with loading cost

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.     

中小呼叫中心月度排班优化模型与算法

国内中小呼叫中心制定坐席人员月度排班表时,通常考虑劳动法规合同约束和体现企业自身用工管理诉求。构建坐席人员月度排班优化问题的二次整数规划模型。鉴于问题模型难解性,依据调研企业需求和模型逻辑结构分析,把问题分解成三个子问题。通过构建整数规划模型和提出启发式算法来求出子问题解,从而生成排班问题优化解。问题实例计算表明,模型算法能够有效控制人力成本和兼顾员工同班次管理目标。与周排班方法比较,该方法能够充分体现月度排班人力灵活性来实现人力优化配置。     

运输网络运量分配问题的模型及算法研究

针对我国在运量分配模型及算法方面研究比较薄弱的现状,本文对此问题进行了系统深人的研究,应用运筹学、计算机科学的新的理论和方法,建立了多目标运量分配优化模型,且在模型中,将一些重要特性考虑成运输流量的函数,从而可使分配结果更符合实际情况。同时为求解该模型,本文研究设计了鲁棒性强、高效、实用的自适应搜索算法。     

基于免疫遗传算法和列生成的多项目人力资源调度研究

主要研究列生成法求解带有人力资源约束的多项目多模式进度管理问题。首先根据问题建立了相应的数学模型,模型中考虑了多种约束,如项目对人员能力、水平的不同要求,目标为满足约束的条件下成本最小化,其中包含固定和可变两类成本。模型分解后,按照列生成法流程求解。由于问题的复杂性,采用启发式算法求解每个子问题:首先由基于优先原则的启发式方法给出问题的初始解,再由免疫遗传算法寻优。通过数值实验分析了算法性能、模型改进情况,不同优先原则组合对目标成本和各项目间时间分配的影响。     

Multi-objective machine-component grouping in cellular manufacturing: A genetic algorithm

The cellular manufacturing system (CMS) is an important group technology (GT) application. The first step of CMS design is cell formation, generally known as machinecell formation (MCF) or machine-component (MCG). A genetic algorithm (GA) is a robust adaptive optimization method based on principles of natural evolution and is appropriate for the MCG problem, which is an NP complete complex problem. In this study, we propose a GA-based procedure to solve the MCG problem. More specifically, this study aims to minimize (1) total cost, which includes intercell and intracell part transportation costs and machines investment cots; (2) intracell machine loading imbalance; and (3) intercell machine loading imbalance under many realistic considerations. An illustrative example and comparisons demonstrate the effectiveness of this procedure. The proposed procedure is extremely adaptive, flexible, efficient and can be used to solve real MCG problems in factories by providing robust manufacturing cell formation in a short execution time.     

一类稀疏投资组合双层参数估计模型及其应用

带基约束的投资组合问题是近年来投资组合领域的热点问题,但是参数不确定性直接影响了模型的效果。带基约束的投资组合问题所涉及的参数不仅包括以往研究认为非常重要的预期收益率,还包括控制投资组合规模的稀疏度,尤其是最优稀疏度估计方面的专门研究还十分匮乏。为了使带基约束的投资组合模型更好地为投资决策服务,本文从投资者效用出发,用双层规划的思想构建了带基约束的投资组合双层参数估计模型。然后根据模型的特点,设计了无导数优化算法框架,并基于ADMM对算法子问题进行求解。本文实验针对真实的市场数据给出了预期收益率和最优稀疏度的估计,接着通过与等权重策略和含上下界约束的均值-方差模型进行比较,说明了模型及算法的有效性和实用性。最后,将本文提出的双层参数估计模型推广到了更一般的形式。     

及时条件下订货策略的优化模型及求解算法

在供应链管理中,兼顾供需双方的利益,采用合适的订购单价,订购批量及运送次数,供需双方都可以提高自己的利润。本文用双层规划模型描述了及时条件下的订货策略模型。然后阐述了用遗传算法求解该模型的基本思想,最后进行了算法设计并给出一个简单算例验证了本模型及其算法的可行性。     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

A simulated annealing algorithm for designing cellular manufacturing systems with productivity consideration

In this paper, we propose a productivity model for solving the machine-part grouping problem in cellular manufacturing (CM) systems. First, a non-linear 0-1 integer programming model is developed to identify machine groups and part families simultaneously. This model aims to maximize the system productivity defined as the ratio of total output to the total material handling cost. Second, an efficient simulated annealing (SA) algorithm is developed to solve large-scale problems. This algorithm provides several advantages over the existing algorithms. It forms part families and machine cells simultaneously. It also considers production volume, sales price, and maximum number of machines in each cell and total material handling cost. The proposed SA also has the ability to determine the optimum number of manufacturing cells. The performance of the developed models is tested on eight problems of different size and complexity selected from the literature. The results show the superiority of the SA algorithm over the mathematical programming model in both productivity and computational time.     

DNMA: A double normalization-based multiple aggregation method for multi-expert multi-criteria decision making

This paper develops a comprehensive algorithm for multi-expert multi-criteria decision making problems considering quantitative and qualitative criteria in forms of benefit, cost or target types. We focus on using probabilistic linguistic term sets to express the qualitative evaluations due to their excellence in expressing complex individual and collective linguistic assessments. Firstly, we develop a target-based linear normalization technique and a target-based vector normalization technique. A weight adjustment method is proposed to achieve the tradeoff between criteria after normalization. Given that the two target-based normalization techniques have different advantages, we then propose a ranking method, which consists three subordinate models, based on these two target-based normalization approaches and three aggregation techniques. Reliable results of a multi-expert multi-criteria decision making problem are determined by integrating the subordinate utility values and the ranks of alternatives. The proposed method is implemented to solve the green enterprise ranking problems and the excavation scheme selection problem for shallow buried tunnels, respectively. The advantages of the proposed method are emphasized through comparative analyses with other ranking methods.