A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

命令式动态规划类算法程序推导及机械化验证

动态规划是一种递归求解问题最优解的方法,主要通过求解子问题的解并组合这些解来求解原问题.由于其子问题之间存在大量依赖关系和约束条件,所以验证过程繁琐,尤其对命令式动态规划类算法程序正确性验证是一个难点.基于动态规划类算法Isabelle/HOL函数式建模与验证,通过证明命令式动态规划类算法程序与其的等价性,避免证明正确性时处理复杂的依赖关系和约束条件,提出命令式动态规划类算法程序设计框架及其机械化验证.首先,根据动态规划类算法的优化方法(备忘录方法)和性质(最优子结构性质和子问题重叠性质)描述问题规约、归纳递推关系式和形式化构造出循环不变式,并且基于递推关系式生成IMP (Minimalistic Imperative Programming Language)代码;其次,将问题规约、循环不变式和生成的IMP代码输入VCG (Verification Condition Generator),自动生成正确性的验证条件;然后,在Isabelle/HOL定理证明器中对验证条件进行机械化验证.算法首先设计为命令式动态规划类算法的一般形式,并进一步实例化得到具体算法.最后,例证了所提框架的有效性,为动态规划类算法的自动化推导和验证提供参考价值.     

Benders decomposition with integer subproblem

The application of Benders decomposition method to a problem might result in a subproblem including integer variables. In this case, it is not able to apply the classical Benders algorithm. In this study we present a Branch-and-Cut algorithm, which introduces the notion of “Local Cuts” as well as “Global Cuts”. The integrality constraints of the subproblem are relaxed and the relaxed problem is solved in a branch-and-bound framework, where in each node, the Benders algorithm is applied between the master problem and the relaxed subproblem. Benders cuts generated in a node of the branch-and bound tree are proved to be valid for all its descendants, but they are not necessarily valid for the non-descendant nodes. These cuts, referred to as local cuts, can be used to warm start the master problem of each descendant node, thus leading to better initial bounds. Furthermore, a novel way is presented for defining the local cuts in a general form. This general form is in fact a function of the subproblems’ variables and enables us to reuse the generated (local) cuts in the whole tree by updating some values of the function. The performance of the proposed algorithm is tested on the classical Capacitated Fixed Charge Multiple Knapsack Problem (CFCMKP).     

Scheduling a hybrid flowshop with batch production at the last stage

In this paper, we address the problem of scheduling n$n$ jobs in an s$s$-stage hybrid flowshop with batch production at the last stage with the objective of minimizing a given criterion with respect to the completion time. The batch production at stage s$s$ is referred to as serial batches by Hopp and Spearman where the processing time of a batch is equal to the sum of the processing times of all jobs included in it. This paper establishes an integer programming model and proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem is decomposed based on a batch, unlike the commonly used job decoupling, so that it can be decomposed into batch-level subproblems, each for a specific batch. An improved forward dynamic programming algorithm is then designed for solving these subproblems where all operations within a batch form an in-tree structure and the precedence relations exist not only between the operations of a job but between the jobs in this batch at the last stage. A computational comparison is provided for the developed algorithm and the commonly used Lagrangian relaxation algorithm which, after capacity constraints and precedence relations within a batch are relaxed, decomposes the relaxed problem into job-level subproblems and solves the subproblems by using dynamic programming. Numerical results show that the designed Lagrangian relaxation method provides much better schedules and converges faster for small to medium sized problems, especially for larger sized problems.     

A cross entropy algorithm for the Knapsack problem with setups

In this article we propose a new metaheuristic-based algorithm for the Integer Knapsack Problem with Setups. This problem is a generalization of the standard Integer Knapsack Problem, complicated by the presence of setup costs in the objective function as well as in the constraints. We propose a cross entropy based algorithm, where the metaheuristic scheme allows to relax the original problem to a series of well chosen standard Knapsack problems, solved through a dynamic programming algorithm. To increase the computational effectiveness of the proposed algorithm, we use a turnpike theorem, which sensibly reduces the number of iterations of the dynamic algorithm. Finally, to testify the robustness of the proposed scheme, we present extensive computational results. First, we illustrate the step-by-step behavior of the algorithm on a smaller, yet difficult, problem. Subsequently, to test the solution quality of the algorithm, we compare the results obtained on very large scale instances with the output of a branch and bound scheme. We conclude that the proposed algorithm is effective in terms of solution quality as well as computational time.     

Determining the K-best solutions of knapsack problems

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K.     

Temporally Consistent Tone Mapping of Images and Video Using Optimal <Emphasis Type="Italic">K</Emphasis>-means Clustering

The field of high dynamic range imaging addresses the problem of capturing and displaying the large range of luminance levels found in the world, using devices with limited dynamic range. In this paper we present a novel tone mapping algorithm that is based on K-means clustering. Using dynamic programming we are able to not only solve the clustering problem efficiently, but also find the global optimum. Our algorithm runs in \(\hbox {O}(N^2K)\) for an image with N input luminance levels and K output levels. We show that our algorithm gives comparable results to state-of-the-art tone mapping algorithms, but with the additional large benefit of a minimum of parameters. We show how to extend the method to handle video input. We test our algorithm on a number of standard high dynamic range images and video sequences and give qualitative and quantitative comparisons to a number of state-of-the-art tone mapping algorithms.     

Toward a Model for Backtracking and Dynamic Programming

We propose a model called priority branching trees (pBT) for backtracking and dynamic programming algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as Interval Scheduling, Knapsack and Satisfiability.     

PCB贴装中供料器分配问题的动态规划改进算法

供料器分配问题是贴片机工艺优化问题中的一个关键问题,直接影响PCB贴装效率的高低;针对多头拱架型贴片机,首先根据取贴循环数,把问题分解为相互联系的子问题,然后针对每个取贴循环分别建立动态规划模型,并为了提高多阶段决策动态规划问题的搜索效率,提出了一种动态规划改进算法;当所有的子问题都获得解决后,整个供料器分配问题就获得解决;实验证明,所提算法能有效提高贴片机贴片效率,减少贴片时间。     

Dynamic programming algorithms for the Zero-One Knapsack Problem

New dynamic programming algorithms for the solution of the Zero-One Knapsack Problem are developed. Original recursive procedures for the computation of the Knapsack Function are presented and the utilization of bounds to eliminate states not leading to optimal solutions is analyzed. The proposed algorithms, according to the nature of the problem to be solved, automatically determine the most suitable procedure to be employed. Extensive computational results showing the efficiency of the new and the most commonly utilized algorithms are given. The results indicate that, for difficult problems, the algorithms proposed are superior to the best branch and bound and dynamic programming methods.     

An O(n) algorithm for the linear multiple choice knapsack problem and related problems

We present an O(n) algorithm for the Linear Multiple Choice Knapsack Problem and its d-dimensional generalization which is based on Megiddo's (1982) algorithm for linear programming. We also consider a certain type of convex programming problems which are common in geometric location models. An application of the linear case is an O(n) algorithm for finding a least distance hyperplane in R^d according to the rectilinear norm. The best previously available algorithm for this problem was an O(n log²n) algorithm for the two-dimensional case. A simple application of the nonlinear case is an O(n) algorithm for finding the point at which a ‘pursuer’ minimizes its distance from the furthest among n ‘targets’, when the trajectories involved are straight lines in R^d.     

An efficient coarse-grain multicomputer algorithm for the minimum cost parenthesizing problem

Several problems modeled by dynamic programming have been solved using a coarse-grain multicomputer parallel model (CGM for short). These problems use either polyadic dynamic programming or monadic non-serial dynamic programming. In this paper, we address the general case: we propose a parallel algorithm in the CGM model with p processors for the Optimal String Parenthesizing Problem or Minimum Cost Parenthesizing Problem, which is a typical polyadic non-serial dynamic programming problem. The algorithm we obtain requires ?(2p)^1/2? communication rounds and, at most, O(n ³/p) time-steps on p processors. This new CGM algorithm performs better than the previously most efficient solution, which uses p communication rounds.     

A problem reduction based approach to discrete optimization algorithm design

The paper presents a novel approach to formal algorithm design for a typical class of discrete optimization problems. Using a concise set of program calculation rules, our approach reduces a problem into subproblems with less complexity based on function decompositions, constructs the problem reduction graph that describes the recurrence relations between the problem and subproblems, from which a provably correct algorithm can be mechanically derived. Our approach covers a large variety of algorithms and bridges the relationship between conventional methods for designing efficient algorithms (including dynamic programming and greedy) and some effective methods for coping with intractability (including approximation and parameterization).     

Hybrid full-/half-duplex cellular networks: user admission and power control

We consider a single-cell network with a hybrid full-/half-duplex base station. For the practical scenario with N channels, K uplink users, and M downlink users (max{K,M} ≤ N ≤ K + M), we tackle the issue of user admission and power control to simultaneously maximize the user admission number and minimize the total transmit power when guaranteeing the quality-of-service requirement of individual users. We formulate a 0–1 integer programming problem for the joint-user admission and power allocation problem. Because finding the optimal solution of this problem is NP-hard in general, a low-complexity algorithm is proposed by introducing the novel concept of adding dummy users. Simulation results show that the proposed algorithm achieves performance similar to that of branch and bound algorithm and significantly outperforms the random pairing algorithm.     

A hypercube algorithm for the 0/1 Knapsack problem

Many combinatorial optimization problems are known to be NP-complete. A common point of view is that finding fast algorithms for such problems using polynomial number of processors is unlikely. However, facts of this kind usually are established for “worst” case situations and in practice many instances of NP-complete problems are successfully solved in polynomial time by such traditional combinatorial optimization techniques as dynamic programming and branch-and-bound. New opportunities for effective solution of combinatorial problems emerged with the advent of parallel machines. In this paper we describe an algorithm which generates an optimal solution for the 0/1 integer Knapsack problem on the NCUBE hypercube computer. It is also demonstrated that the same algorithm can be applied for the two-dimensional 0/1 Knapsack problem. Experimental data which support the theoretical claims are provided for large instances of the one- and two-dimensional Knapsack problems.     

An efficient parallel algorithm for solving the Knapsack problem on hypercubes

We present in this paper an efficient algorithm for solving the integral Knapsack problem on hypercube. The main idea is to represent the computations of the dynamic programming formulation as a precedence graph (which has the structure of an irregular mesh). Then, we propose a time optimal scheduling algorithm for computing the irregular meshes on hypercube.     

On the depth complexity of formulas

The problem of minimizing the depth of formulas by equivalence preserving transformations is formalized in a general algebraic setting. For a particular algebraic system ∑₀ specific methods of a dynamic programming nature are developed for proving lower bounds on depth. Such lower bounds for ∑₀ automatically imply the same results for the systems of (i) arithmetic computations with addition and multiplication only, and (ii) computations over finite languages using union and concatenation. The specific lower bounds obtained are (i) depth 2n?o(n) for the permanent, (ii) depth (0.25+o(1))log² n for the symmetric polynomials and (iii) depth 1.16logn for a problem of formula sizen.     

Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness

In this paper, we address a new Lagrangian relaxation (LR) method for solving the hybrid flowshop scheduling problem to minimize the total weighted tardiness. For the conventional LR, the problem relaxing machine capacity constraints can be decomposed into individual job-level subproblems which can be solved by dynamic programming. The Lagrangian dual problem is solved by the subgradient method. In this paper, a Lagrangian relaxation with cut generation is proposed to improve the Lagrangian bounds for the conventional LR. The lower bound is strengthened by imposing additional constraints for the relaxed problem. The state space reductions for dynamic programming for subproblems are also incorporated. Computational results demonstrate that the proposed method outperforms the conventional LR method without significantly increasing the total computing time.     

Optimizing server placement in distributed systems in the presence of competition

Although the problem of data server placement in parallel and distributed systems has been studied extensively, most of the existing work assumes there is no competition between servers. Hence, their goal is to minimize read, update and storage cost. In this paper, we study the server placement problem in which a new server has to compete with existing servers for user requests. Therefore, in addition to minimizing cost, we also need to maximize the benefit of building a new server.Our major results include three parts. First, for tree-structured systems, we propose an O(|V|³k) time dynamic programming algorithm to find the optimal placement of k extra servers that maximizes the benefit in a tree with |V| nodes. We also propose an O(|V|³) time dynamic programming algorithm to find the optimal placement of extra servers that maximizes the benefit, without any constraint on the number of extra servers. Second, for general connected graphs, we prove that the server placement problems are NP-complete, and present three greedy heuristic algorithms, called Greedy Add, Greedy Remove and Greedy Add-Remove, to solve them. Third, we show that if the number of requests a server can handle (i.e., server capacity) is bounded, the server placement problem is NP-complete even for tree networks. We then derive a variation of the same set of greedy heuristic algorithms, with consideration of server capacity constraint, to solve the problem.Our experiment results demonstrate that the greedy algorithms achieve good results, when compared with the upper bounds found by a linear programming algorithm. Greedy Add performs best in the unconstrained model, yielding a benefit within 12% difference from the theoretical upper bound in average. For the constrained model, Greedy Remove performs best for smaller network sizes, while Greedy Add-Remove performs best for larger network sizes. On average, the heuristic algorithms yield a benefit within 13% difference from the theoretical upper bound in the constrained model.     

A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming

In this paper we describe a branch and bound algorithm for solving the unconstrained quadratic 0–1 programming problem. The salient features of it are the use of quadratic programming heuristics in the transformation of subproblems and exploiting some classes of facets of the polytope related to the quadratic problem in deriving upper bounds on the objective function. We develop facet selection procedures that form a basis of the bound computation algorithm. We present computational experience on four series of randomly generated problems and 14 real instances of a quadratic problem arising in design automation. We remark that the same ideas can also be applied to some other combinatorial optimization problems.