解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

A branch and bound method for the solution of multiparametric mixed integer linear programming problems

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the mp-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.     

Symbolic integration of logic in MILP branch and bound methods for the synthesis of process networks

This paper deals with the branch and bound solution of process synthesis problems that are modelled as mixed-integer linear programming (MILP) problems. The symbolic integration of logic relations between potential units in a process network is proposed in the LP based branch and bound method to expedite the search for the optimal solution. The objective of this integration is to reduce the number of nodes that must be enumerated by using the logic to decide on the branching of variables and to determine by symbolic inference whether additional variables can be fixed at each node. The important feature of this approach is that it does not require additional constraints in the MILP and the logic can be systematically generated for process networks. Strategies for performing the integration are proposed that use the disjunctive and conjunctive normal form representations of the logic, respectively. Computational results will be presented to illustrate that substantial savings can be achieved.     

BBPH: Using progressive hedging within branch and bound to solve multi-stage stochastic mixed integer programs

Progressive hedging, though an effective heuristic for solving stochastic mixed integer programs (SMIPs), is not guaranteed to converge in this case. Here, we describe BBPH, a branch and bound algorithm that uses PH at each node in the search tree such that, given sufficient time, it will always converge to a globally optimal solution. In addition to providing a theoretically convergent “wrapper” for PH applied to SMIPs, computational results demonstrate that for some difficult problem instances branch and bound can find improved solutions after exploring only a few nodes.     

A new branch and bound algorithm for cell formation problem

Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems.     

可靠性网络中费用最小化问题的一种新的分枝定界算法

本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.     

A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems

The k-center problem arises in many applications such as facility location and data clustering. Typically, it is solved using a branch and bound tree traversed using the depth first strategy. The reason is its linear space requirement compared to the exponential space requirement of the breadth first strategy. Although the depth first strategy gains useful information fast by reaching some leaves early and therefore assists in pruning the tree, it may lead to exploring too many subtrees before reaching the optimal solution, resulting in a large search cost. To speed up the arrival to the optimal solution, a mixed breadth-depth traversing strategy is proposed. The main idea is to cycle through the nodes of the same level and recursively explore along their first promising paths until reaching their leaf nodes (solutions). Thus many solutions with diverse structures are obtained and a good upper bound of the optimal solution can be achieved by selecting the minimum among them. In addition, we employ inexpensive lower and upper bounds of the enclosing balls, and this often relieves us from calling the computationally expensive exact minimum enclosing ball algorithm. Experimental work shows that the proposed strategy is significantly faster than the naked branch and bound approach, especially as the number of centers and/or the required accuracy increases.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm

In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming problems, at each node, are not solved to optimality, rather one iteration step is taken at each node and then branching is applied. A Sequential Cutting Plane (SCP) algorithm is used for solving the nonlinear programming problems by solving a sequence of linear programming problems. The proposed algorithm generates explicit lower bounds for the nodes in the branch and bound tree, which is a significant improvement over previous algorithms based on QP techniques. Initial numerical results indicate that the described algorithm is a competitive alternative to other existing algorithms for these types of problems.     

A Branch and Bound Algorithm for a Class of Asymmetrical Vehicle Routeing Problems

This paper describes a branch and bound algorithm for a general class of asymmetrical vehicle routeing problems. Vehicle routes start and end at a central depot. Visits are made to nodes grouped into clusters: every cluster must receive a minimum number of visits. But not all nodes must be visited: there are specified nodes and non-specified nodes. Vehicle routes are also constrained by capacity and distance restrictions. The problem is formulated as an integer linear program. It is then solved by a branch and bound algorithm which exploits the unimodular structure of the subproblems. Computational results are reported.     

Parallel branch and bound for multidimensional scaling with city-block distances

Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non-differentiability. Recently a branch and bound algorithm for multidimensional scaling with city-block distances has been proposed for solution of medium-size problems exactly. The algorithm exploits piecewise quadratic structure of the objective function. In this paper a parallel version of the branch and bound algorithm for multidimensional scaling with city-block distances has been proposed and investigated. Parallel computing enabled solution of larger problems what was not feasible with the sequential version.     

A Branch and Bound Algorithm for Separable Concave Programming

In this paper, we propose a new branch and bound algorithm for the solution of large scale separable concave programming problems. The largest distance bisection (LDB) technique is proposed to divide rectangle into sub-rectangles when one problem is branched into two subproblems. It is proved that the LDB method is a normal rectangle subdivision(NRS). Numerical tests on problems with dimensions from 100 to 10000 show that the proposed branch and bound algorithm is efficient for solving large scale separable concave programming problems, and convergence rate is faster than ω-subdivision method.     

Cluster based branching for the asymmetric traveling salesman problem

This paper presents a new branching scheme for the asymmetric traveling salesman problem (ATSP) based on clusters. A cluster is defined as a node set with the characteristic that there exists an optimal solution in which the nodes in the node set are visited consecutively. The paper considers identification of clusters, implementation of a cluster based branching scheme, and cluster based dominance tests. The new approach is implemented in a branch and bound algorithm using a well-known additive bounding procedure. Considerable savings in computing time are obtained compared to previously published assignment based branch and bound algorithms for the ATSP.     

A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems

We examine a branch and bound algorithm for solving nonlinear (convex) integer programming problems. In this note we generalize previous results for the quadratic case. The variables are branched in such a way that the number of branch and bound nodes checked in the process is small. Numerical results confirm the efficiency.     

An Exact Least Trimmed Squares Algorithm for a Range of Coverage Values

A new algorithm to solve exact least trimmed squares (LTS) regression is presented. The adding row algorithm (ARA) extends existing methods that compute the LTS estimator for a given coverage. It employs a tree-based strategy to compute a set of LTS regressors for a range of coverage values. Thus, prior knowledge of the optimal coverage is not required. New nodes in the regression tree are generated by updating the QR decomposition of the data matrix after adding one observation to the regression model. The ARA is enhanced by employing a branch and bound strategy. The branch and bound algorithm is an exhaustive algorithm that uses a cutting test to prune nonoptimal subtrees. It significantly improves over the ARA in computational performance. Observation preordering throughout the traversal of the regression tree is investigated. A computationally efficient and numerically stable calculation of the bounds using Givens rotations is designed around the QR decomposition, avoiding the need to explicitly update the triangular factor when an observation is added. This reduces the overall computational load of the preordering device by approximately half. A solution is proposed to allow preordering when the model is underdetermined. It employs pseudo-orthogonal rotations to downdate the QR decomposition. The strategies are illustrated by example. Experimental results confirm the computational efficiency of the proposed algorithms. Supplemental materials (R package and formal proofs) are available online.     

Branch and bound crossed with GA to solve hybrid flowshops

This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.     

An improved branching rule for the symmetric travelling salesman problem

This paper presents an improvement to an existing branch and bound algorithm for solving the symmetric travelling salesman problem. The lower bound used is the standard one obtained from the sequence of minimal spanning 1-trees computed via subgradient optimization, but the branching rule is new. Rather than selecting for inclusion or exclusion those edges which violate the tour constraints in the final 1-tree of the sequence, we consider edges which are present in roughly half of the final few 1-trees. This results in a decision tree whose number of nodes grows by powers of two rather than three, hence significantly reducing the total number of decision nodes required to solve the problem.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

Job shop scheduling with beam search

Beam Search is a heuristic method for solving optimization problems. It is an adaptation of the branch and bound method in which only some nodes are evaluated in the search tree. At any level, only the promising nodes are kept for further branching and remaining nodes are pruned off permanently. In this paper, we develop a beam search based scheduling algorithm for the job shop problem. Both the makespan and mean tardiness are used as the performance measures. The proposed algorithm is also compared with other well known search methods and dispatching rules for a wide variety of problems. The results indicate that the beam search technique is a very competitive and promising tool which deserves further research in the scheduling literature.     

具有机器适用限制的分布式置换流水车间问题的模型与算法

考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性.