Revisiting Branch and Bound Search Strategies for Machine Scheduling Problems

In the design of exact methods for NP-hard machine scheduling problems, branch and bound algorithms have always been widely considered. In this work we revisit the classic search strategies for branch and bound schemes. We consider a systematic application of the well known dynamic programming dominance property for machine scheduling problems. Several conditions concerning the application of the proposed property with respect to best first, depth first, breadth first search strategies and problem characteristics are presented. Computational testing on single machine and flow shop problems validate in practice the efficiency of the considered approach and suggest that the traditional choice of depth first search with respect to best first and breadth first is strongly questionable.     

基于Visual C++的0-1背包问题的分枝限界算法

0-1背包问题是经典的NP问题。本文对0-1背包问题的分枝限界算法进行了分析,用Visual C++实现该算法。     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

基于遗传分枝定界算法的Flow-shop调度问题

Flow shop调度问题属于NP难题,传统的方法很难求出精确最优解,提出了一种遗传分枝定界算法,即在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序,求解3机Flow shop调度问题,该算法与常用的遗传局部算法和遗传动态规划算法类似,用随机方法测试例子,与目前著名的Taillard的禁忌搜索算法和Reeves的遗传算法两种改进算法进行比较,大量的数据实验证实了遗传分枝定界算法的有效性。     

Bound sets for biobjective combinatorial optimization problems

In this paper we introduce the concept of bound sets for multiobjective discrete optimization. We prove general results on lower and upper bound sets for combinatorial optimization problems with multiple objectives. We present general algorithms for constructing lower and upper bound sets for biobjective problems and provide numerical results on five different problem types.     

Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison

In this paper we describe and compare two frameworks for constraint solving where classical CSPs, fuzzy CSPs, weighted CSPs, partial constraint satisfaction, and others can be easily cast. One is based on a semiring, and the other one on a totally ordered commutative monoid. While comparing the two approaches, we show how to pass from one to the other one, and we discuss when this is possible. The two frameworks have been independently introduced in ijcai95,jacm and schiex-ijcai95.     

基于约束传播的HFS调度研究

将约束传播技术同分枝定界法相结合求解优化目标为最小最大完工时间的混合流水车间调度问题。算法核心是根据资源松弛度确定关键阶段,通过在分枝定界算法中嵌入动态可调的开工时间窗口,用顺序传播、资源传播、上下游工序传播,动态修改每个操作的开工时间窗上下界,并在算法特点基础上给出相应的剪枝下界,以减小搜索空间,提高分枝定界法的优化能力。实验结果证明了算法的有效性。     

A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field

A linear (q,δ,,m(n))-locally decodable code (LDC) C : Fn → Fm(n) is a linear transformation from the vector space Fn to the space Fm(n) for which each message symbol xi can be recovered with probability at least 1/(|F|) +∈ from C(x) by a randomized algorithm that queries only q positions of C(x),even if up to δm(n) positions of C(x) are corrupted.In a recent work of Dvir,the author shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits.He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures.Our main result is an m(n) = Ω (n2) lower bound for linear 3-query LDCs over any,possibly infinite,field.The constant in the Ω (·) depends only on ε and δ.This is the first lower bound better than the trivial m(n) = Ω (n) for arbitrary fields and more than two queries.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

Branch and Bound Algorithms for Single Machine Scheduling with Batching to Minimize the Number of Late Jobs

This paper considers the problem of scheduling a single machine to minimize the number of late jobs in the presence of sequence-independent family set-up times. The jobs are partitioned into families, and a set-up time is required at the start of each batch, where a batch is a maximal set of jobs in the same family that are processed consecutively. We design branch and bound algorithms that have several alternative features. Lower bounds can be derived by relaxing either the set-up times or the due dates. A first branching scheme uses a forward branching rule with a depth-first search strategy. Dominance criteria, which determine the order of the early jobs within each family and the order of the batches containing early jobs, can be fully exploited in this scheme. A second scheme uses a ternary branching rule in which the next job is fixed to be early and starting a batch, to be early and not starting a batch, or to be late. The different features are compared on a large set of test problems, where the number of jobs ranges from 30 to 50 and the number of families ranges from 4 to 10.     

多状态网络可靠度下界的矩阵分解算法

为减少计算多状态网络可靠度精确值的复杂性,提出基于分解计算多状态网络不可靠度精确值的思想,在此基础上提出一个求解多状态网络不可靠度动态上界(对应于可靠度动态下界)的算法.算法先通过分解运算去除某些边引起的d-最小割集之间的相关性,将网络不可靠度转化为多个互斥事件的概率之和,再应用MESP界求取这些事件的概率,计算网络不可靠度上界,对应得到可靠度下界,并计算了得到的可靠度下界与精确值间的绝对误差界.通过定义d-最小割集矩阵,利用矩阵分解实现算法,结构清晰、便于编程计算.相关引理的证明及算例分析表明随着分解的深入,算法能够得到满足精度要求的可靠度下界.     

Complete Bound Consistency for the Global Cardinality Constraint

We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n′) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n′ is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.Partially supported by DFG grant SA 933/1-1.Partially supported by the EU IST Programme, IST-1999-14186 (ALCOM-FT).     

一种基于下界估计的动态表调度算法

调度是高层次综合的核心步骤之一。该文分析了常用的调度算法,并提出一种基于下界估计的动态表调度算法,实验数据表明该方法可以有效地实现多目标的优化。     

分枝定界算法用于有机混合物的分析

分枝定界算法用于多组分同时定量性分析,只需解析一份试样测得的数据,即可同时得到待测样品中所含组分的种类,数目及含量。应用4个判据,解决了最佳子集难判断的问题,使最优回归子集的选择更加准确、真实、可靠。     

测试用例自动生成中等式约束处理算法

为了解决测试用例自动生成中等式约束的求解问题,提出一种加入等式处理策略的分支限界搜索算法.首先将线性代数中判定线性方程组是否有解的方法引入分支限界测试用例生成框架之中;然后在已有算法模型的基础上提出集成等式处理分支限界搜索算法,以支持多种变量类型的等式处理;最后将等式约束分为等式无解、等式多解和等式唯一解三大类进行处理,包含了等式约束求解问题的所有情况.实验结果表明,文中算法可以实现对一部分不可达路径的检测,在很大程度上减少测试用例生成的时间并提高覆盖率;对大工程的测试以及同开源约束求解工具Choco的对比实验,也证明了该算法可以提升测试效率.     

具有约束条件的单机JIT调度问题

具有约束条件的单机ＪＩＴ调度问题齐向彤陈秋双涂生（南开大学计算机与系统科学系天津３０００７１）关键词Ｅ／Ｔ调度,优化,分支定界法．１）国家“八六三”ＣＩＭＳ主题和国家自然科学基金资助课题．收稿日期１９９５－０９－１８１引言近年来,随着Ｊｕｓｔ－ｉｎ...     

路径和下界公式及其在调度问题中的应用

主要是研究以makespan为目标的多机器置换flow shop调度问题.由于它NP-困难,无法用多项式时间算法求解.而路径和关键路径是研究该问题的一个有力工具,对其进行深入分析可以帮助进一步理解问题最基本的特?挖掘其在更多优化算法中的应用,增加该算法的效率.在研究了原有的关键路径基础上,借助于有向栅格图和重新定义的路径及关键路径公式,直观地给出了对工件排列进行插入移动后的新排列的下界公式.另外,在遗传算法和禁忌搜索之外,还给出了下界公式在NEH启发式算法中的应用,并通过实验验证了它在排除没有希望的排列、减少有效搜索空间的强大能力.