Minimizing makespan in a two-stage system with flowshop and open shop

This paper studies two models of two-stage processing with flowshop at the first stage followed by open shop at the second stage. The first model involves multiple machines at the first stage and two machines at the second stage, and the other involves multiple machines at both stages. In both models, the objective is to minimize the makespan. This problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its worst-case performance guarantee is analyzed for both models. An integer programming model and a branch and bound algorithm are proposed for model 1 and a lower bound is developed for model 2 as benchmarks for the heuristic algorithms. Computational experiences show that the heuristic algorithms consistently generate good schedule and the branch and bound algorithm is much efficient than the integer-programming model.     

Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.     

Parametric tabu-search for mixed integer programs

A parametric form of tabu-search is proposed for solving mixed integer programming (MIP) problems that creates and solves a series of linear programming (LP) problems embodying branching inequalities as weighted terms in the objective function. The approach extends and modifies a parametric branch and bound procedure of Glover [Parametic branch and bound. OMEGA, The International Journal of Management Science 1978;6:1–9], replacing its tree search memory by the adaptive memory framework of tabu-search and introducing new associated strategies that are more flexible than the mechanisms of branch and bound.     

A traffic grooming problem considering hub location for synchronous optical network-wavelength division multiplexing networks

In this paper, we deal with a traffic demand clustering problem for designing SONET-WDM rings. The objective is to minimize the total cost of optical add-drop multiplexers (OADMs) and inter-ring hub equipments, while satisfying intra-ring and inter-ring capacities. Also, the minimum number of nodes, for example three, for each ring should be satisfied. We develop an integer programming (IP) formulation for the problem and develop some valid inequalities that provide a tight lower bound for the problem. Dealing with the inherent computational complexity of the problem, we also devise an effective tabu search procedure for finding a feasible solution of good quality within reasonable computing time. Computational results are provided to demonstrate the efficacy of the lower and upper bound procedures for solving the problem.     

改进的求解TSP混合分支裁剪法

分支裁减法是一种有效的求解小规模TSP的整数规划方法.随着TSP规模的逐步扩大,问题求解的复杂性也随之增加.在TSP的可计算数学研究领域中,局部搜索算法能快速求解TSP的局部最优解.通过将局部搜索算法与分支裁减法结合,利用局部搜索算法对分支裁减法获得上界所对应环路进行优化,使分支限界算法的上界更快地向全局最优解靠近,提高算法的求解效率,扩大了分支裁减法求解TSP的规模.     

Maximum-likelihood detection based on branch and bound algorithm for MIMO systems

Maximum likelihood detection for MIMO systems can be formulated as an integer quadratic programming problem. In this paper, we introduce depth-first branch and bound algorithm with variable dichotomy into MIMO detection. More nodes may be pruned with this structure. At each stage of the branch and bound algorithm, active set algorithm is adopted to solve the dual subproblem. In order to reduce the complexity further, the Cholesky factorization update is presented to solve the linear system at each iteration of active set algorithm efficiently. By relaxing the pruning conditions, we also present the quasi branch and bound algorithm which implements a good tradeoff between performance and complexity. Numerical results show that the complexity of MIMO detection based on branch and bound algorithm is very low, especially in low SNR and large constellations.     

Searching for optimal integer solutions to set partitioning problems using column generation

In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation.     

Faster MIP solutions via new node selection rules

When a branch and bound method is used to solve a linear mixed integer program (MIP), the order in which the nodes of the branch and bound tree are explored significantly affects how quickly the MIP is solved. In this paper, new methods are presented that exploit correlation and distribution characteristics of branch and bound trees to trigger backtracking and to choose the next node to solve when backtracking. A new method is also presented that determines when the cost of using a node selection method outweighs its benefit, in which case it is abandoned in favor of a simpler method. Empirical experiments show that these proposed methods outperform the current state of the art.     

An interior point cutting plane heuristic for mixed integer programming

We explore the use of interior point methods in finding feasible solutions to mixed integer programming. As integer solutions are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior of the feasible set. The algorithm searches along two line segments that connect the weighted analytic center and two extreme points of the linear programming relaxation. Candidate points are rounded and tested for feasibility. Cuts aimed to improve the objective function and restore feasibility are then added to displace the weighted analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along the two line segments are rounded gradually to find integer feasible solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated and a new weighted analytic center is found. Upon failing to find a feasible integer solution, a second phase is started where cuts related to the violated feasibility constraints are added. As a last resort, the algorithm solves a minimum distance problem in a third phase. The heuristic is tested on a set of problems from MIPLIB and CORAL. The algorithm finds good quality feasible solutions in the first two phases and never requires the third phase.     

A Library Hierarchy for Implementing Scalable Parallel Search Algorithms

This paper describes the design of the Abstract Library for Parallel Search (ALPS), a framework for implementing scalable, parallel algorithms based on tree search. ALPS is specifically designed to support data-intensive algorithms, in which large amounts of data are required to describe each node in the search tree. Implementing such algorithms in a scalable manner is challenging both because of data storage requirements and communication overhead. ALPS incorporates a number of new ideas to address this challenge. The paper also describes the design of two other libraries forming a hierarchy built on top of ALPS. The first is the Branch, Constrain, and Price Software (BiCePS) library, a framework that supports the implementation of parallel branch and bound algorithms in which the bounds are obtained by solving some sort of relaxation, usually Lagrangian. In this layer, the notion of global data objects associated with the variables and constraints is introduced. These global objects provide a connection between the various subproblems in the search tree, but they pose further difficulties for designing scalable algorithms. The other library is the BiCePS linear integer solver (BLIS), a concretization of BiCePS, in which linear programming is used to obtain bounds in each search tree node.     

业务流程管理中的大规模整数规划问题求解

对从企业业务流程管理中抽象出来的大规模整数规划问题的计算机求解方法进行讨论。提出一种内存优化管理方法,能更高效地存储海量数据。同时对求解整数规划问题的经典算法——分枝定界算法进行研究,利用人工智能的搜索思想,给出分枝定界法的改进算法,使其能快速求解大规模整数规划问题。     

三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.     

The reduced cost branch and bound algorithm for mixed integer programming

A different branch and bound algorithm for mixed integer programming is presented. Unlike standard linear programming based branch and bound algorithms, where a single fractional variable (or Special Ordered Set) is selected for problem separation, the proposed method selects groups of variables for separation on the basis of their reduced cost in an LP relaxation. The proposed method restricts a large portion of the integer variables to zero on one branch. The net effect is that the original integer program is solved by optimizing a series of smaller, more tightly restricted, integer programs. The authors have programmed the algorithm using the Extended Control Language of the IBM MPSX/370-MIP/370 mixed integer programming package. Computational results are presented that demonstrate the efficiency of the method on problems where the $\text{0}\text{1}$ variables are partitioned into multiple choice constraints containing special ordered sets of variables. While the computational results are limited to this class of problems the algorithm can, in theory, be applied to any mixed integer programming problem.     

A two-stage adaptive fruit fly optimization algorithm for unrelated parallel machine scheduling problem with additional resource constraints

In this paper, an unrelated parallel machine scheduling problem with additional resource constraints (UPMSP_RC) from the real world manufacturing systems is studied. With the objective of minimizing the makespan, a mixed integer linear programming model is presented and several properties are analyzed. Furthermore, a two-stage adaptive fruit fly optimization algorithm (TAFOA) is proposed to solve the UPMSP_RC. At the first stage, a heuristic is proposed to generate an initial solution with high quality. At the second stage, the initial solution is adopted as the initial swarm center for further evolution. During the evolution, the search manners are selected adaptively with the guidance of the problem-specific knowledge, which is a sufficient condition of the best schedule under a given job-to-machine assignment. Moreover, the effect of parameters on the performance of the TAFOA is investigated by using the two-factor analysis of variance (ANOVA). Finally, extensive numerical comparisons are carried out to show the effectiveness of the TAFOA in solving the UPMSP_RC.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

TurboTree: a fast algorithm for minimal trees

A branch and bound algorithm is described for searching rapidly for minimal length trees from biological data. The algorithm adds characters one at a time, rather than adding taxa, as in previous branch and bound methods. The algorithm has been programmed and is available from the authors. A worked example is given with 33 characters and 15 taxa. About 8 x 10(12) binary trees are possible with 15 taxa but the branch and bound program finds the minimal tree in less than 5 min on an IBM PC.     

基于削减搜索分支的快速模板匹配算法

提出了一种在完全搜索中寻找最优匹配点的模板匹配算法。它首先为图像建立一种类似金字塔的特殊层次结构。利用该结构的特点，削减匹配中无用的搜索分支，以达到提高处理效率的目的。通过该算法找到了完全搜索的最优匹配点，实验结果证明了它可以大大提高处理的效率。     

Adversarial search by evolutionary computation

In this paper, we consider the problem of finding good next moves in two-player games. Traditional search algorithms, such as minimax and alpha-beta pruning, suffer great temporal and spatial expansion when exploring deeply into search trees to find better next moves. The evolution of genetic algorithms with the ability to find global or near global optima in limited time seems promising, but they are inept at finding compound optima, such as the minimax in a game-search tree. We thus propose a new genetic algorithm-based approach that can find a good next move by reserving the board evaluation values of new offspring in a partial game-search tree. Experiments show that solution accuracy and search speed are greatly improved by our algorithm.