An algorithm for solving large capacitated warehouse location problems

In this paper we present a lower bound for the capacitated warehouse location problem based upon lagrangean relaxation of a mixed-integer formulation of the problem. Feasible solution exclusion constraints are used together with problem reduction tests derived from both the original problem and the lagrangean relaxation.By incorporating the lower bound and the reduction tests into a tree search procedure we are able to solve problems involving up to 500 potential warehouse locations and 1000 customers.     

Local networks for computer communications: A. WEST and P. JANSON (Eds.) Proceedings of the IFIP Working Group 6.4, International Workshop on Local Networks,Zürich,Switzerland, August 27–29, 1980, North-Holland,Amsterdam, 1981, xiii + 470 pages,Dfl.125.00

In this paper we present two lower bounds for the p-median problem, the problem of locating p facilities (medians) on a network. These bounds are based on two separate lagrangean relaxations of a zero-one formulation of the problem with subgradient optimisation being used to maximise these bounds. Penalty tests based on these lower bounds and a heuristically determined upper bound to the problem are developed and shown to result in a large reduction in problem size. The incorporation of the lower bounds and the penalty tests into a tree search procedure is described and computational results are given for problems with an arbitrary number of medians and having up to 200 vertices. A comparison is also made between these algorithms and the dual-based algorithm of Erlenkotter.     

A Lagrangian lower bound for the container transshipment problem at a railway hub for a fast branch-and-bound algorithm

In this paper, we consider the container transshipment problem at a railway hub. A simple lower bound known for this problem will be improved by a new Lagrangian relaxation lower bound. Computational tests show that this lower bound outperforms the simple one and decreases substantially the run time of the branch-and-bound algorithm.     

A Branch and Bound Algorithm to Minimize Total Weighted Tardiness on a Single Processor

In this paper, we consider the problem of minimizing the total weighted tardiness of a set of jobs processed on a single processor. First, a lower bound based on a Lagrangian decomposition is presented. The particularity of this decomposition, based on a 0–1 time indexed formulation, is to be sensitive to the domain reduction of jobs which are proposed. A branch and bound strategy including these different components is proposed. The results obtained on problems from the literature can be favourably compared to previously works and seem to prove that a trade-off between a tight lower bound and time consuming in the enumeration process can be a good strategy.     

A decomposed branch-and-price procedure for integrating demand planning in personnel staffing problems

The personnel staffing problem calculates the required workforce size and is determined by constructing a baseline personnel roster that assigns personnel members to duties in order to cover certain staffing requirements. In this research, we incorporate the planning of the duty demand in the staff scheduling problem in order to lower the staffing costs. More specifically, the demand originates from a project scheduling problem with discrete time/resource trade-offs, which embodies additional flexibility as activities can be executed in different modes. In order to tackle this integrated problem, we propose a decomposed branch-and-price procedure. A tight lower and upper bound are calculated using a problem formulation that models the project scheduling constraints and the time-related resource scheduling constraints implicitly in the decision variables. Based upon these bounds, the strategic problem is decomposed into multiple tactical subproblems with a fixed workforce size and an optimal solution is searched for each subproblem via branch-and-price. Fixing the workforce size in a subproblem facilitates the definition of resource capacity cuts, which limit the set of eligible project schedules, decreasing the size of the branching tree. In addition, in order to find the optimal integer solution, we propose a specific search strategy based upon the lower bound and dedicated rules to branch upon the workload generated by a project schedule. The computational results show that applying the proposed search space decomposition and the inclusion of resource capacity cuts lead to a well-performing procedure outperforming different other heuristic and exact methodologies.     

On the resolution of the single product capacitated machine siting problem

The single product capacitated machine siting problem (SPCMSP) is an extension of the simple plant location problem, in which plant production depends on installing capacitated machines. In this paper we compare, both theoretically and computationally, three heuristic algorithms for the SPCMSP based upon Lagrangean relaxation and reduction tests of a mixed-integer formulation of the problem, which is NP-hard. We test the performance of the algorithms with examples involving up to 100 potential plants, 1000 customers and six potential machines per plant, which we obtain encouraging results.     

Second order bounds for Markov Decision Processes

The paper describes a bound on the optimal value of a Markov Decision Process using the iterates of the value iteration algorithm. Previous bounds have depended upon the values of the last two iterations, but here we consider a bound which depends on the last three iterates. We show that in a maximisation problem, this leads to a better lower bound on the optimal value.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

A sequential elimination algorithm for computing bounds on the clique number of a graph

We consider the problem of determining the size of a maximum clique in a graph, also known as the clique number. Given any method that computes an upper bound on the clique number of a graph, we present a sequential elimination algorithm which is guaranteed to improve upon that upper bound. Computational experiments on DIMACS instances show that, on average, this algorithm can reduce the gap between the upper bound and the clique number by about 60%. We also show how to use this sequential elimination algorithm to improve the computation of lower bounds on the clique number of a graph.     

具有学习效应的超前有奖延误受罚的排序问题(英文)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

具有学习效应的超前有奖延误受罚的排序问题(英)

本文考虑具有学习效应和共同交货期的单机排序问题.目标函数是加权超前有奖延误受罚总和.我们的目标是寻找一个最优序使得目标函数的值最小.由于该问题是NP-hard的,我们给出一些特殊情况下多项式时间可解的特例.同时在快速估计下界的基础上给出了分支定界算法来求一般情况下的最有排序.     

Gilmore-Lawler bound of quadratic assignment problem

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.      

A branch and bound algorithm for the robust spanning tree problem with interval data

The robust spanning tree problem is a variation, motivated by telecommunications applications, of the classic minimum spanning tree problem. In the robust spanning tree problem edge costs lie in an interval instead of having a fixed value.Interval numbers model uncertainty about the exact cost values. A robust spanning tree is a spanning tree whose total cost minimizes the maximum deviation from the optimal spanning tree over all realizations of the edge costs. This robustness concept is formalized in mathematical terms and is used to drive optimization.In this paper a branch and bound algorithm for the robust spanning tree problem is proposed. The method embeds the extension of some results previously presented in the literature and some new elements, such as a new lower bound and some new reduction rules, all based on the exploitation of some peculiarities of the branching strategy adopted.Computational results obtained by the algorithm are presented. The technique we propose is up to 210 faster than methods recently appeared in the literature.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

Lower bounds based on linear programming for the quadratic assignment problem

In this paper we prove that the Classical Gilmore-Lawler lower bound for the quadratic assignment problem is equivalent to a solution of a certain linear programming problem. By adding additional constraints to this linear programming problem we derive a lower bound which is at least as good as the Gilmore-Lawler lower bound.Some of this research was done while the author was on sabbatical leave at the Department of Management, The Hong Kong University of Science and Technology, Kowloon, Hong Kong.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

A 3/2-Approximation for the proportionate two-machine flow shop scheduling with minimum delays

We study the two-machine flow shop problem with minimum delays. The problem is known to be strongly NP-hard even in the case of unit processing times and to be approximable within a factor of 2 of the length of an optimal schedule in the general case. The question whether there exists a polynomial-time algorithm with a better approximation ratio has been posed by several researchers but still remains open. In this paper, we improve the above bound to 3/2 for the special case of the problem when both operations of each job have equal processing times (this case of flow shop is known as the proportionate flow shop). Our analysis of the algorithm relies upon a nontrivial generalization of the lower bound established by W. Yu for the case of unit processing times.