Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

Exact Algorithm for Concave Knapsack Problems: Linear Underestimation and Partition Method

Integer programming problems with a concave cost function are often encountered in optimization models involving economics of scale. In this paper, we propose an efficient exact algorithm for solving concave knapsack problems. The algorithm consists of an iterative process between finding lower and upper bounds by linearly underestimating the objective function and performing domain cut and partition by exploring the special structure of the problem. The lower bound is improved iteratively via cutting and partitioning the domain. This iteration process converges to the optimality in a finite number of steps. Promising computational results are reported for large-scale concave knapsack problems with up to 1200 integer variables. Comparison results with other existing methods in the literature are also presented. *Research supported by the National Natural Science Foundation of China under Grants 79970107 and 10271073,and the Research Grants Council of Hong Kong under Grant CUHK 4214/01E.     

Complexity Results for Some Global Optimization Problems

We discuss the complexity of a class of highly structured global optimization problems, namely the maximization of separable functions, with each one-dimensional component convex and nondecreasing, over polytopes defined by a 0-1 constraint matrix with at most two variables involved in each constraint. In particular, we prove some inapproximability and approximability results.     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Complexity Results for Flow-Shop and Open-Shop Scheduling Problems with Transportation Delays

We consider shop problems with transportation delays where not only the jobs on the machines have to be scheduled, but also transportation of the jobs between the machines has to be taken into account. Jobs consisting of a given number of operations have to be processed on machines in such a way that each machine processes at most one operation at a time and a job is not processed by more than one machine simultaneously. Transportation delays occur if a job changes from one machine to another. The objective is to find a feasible schedule which minimizes some objective function. A survey of known complexity results for flow-shop and open-shop environments is given and some new complexity results are derived.     

Variable Fixing Algorithms for the Continuous Quadratic Knapsack Problem

We study several variations of the Bitran–Hax variable fixing method for the continuous quadratic knapsack problem. We close the gaps in the convergence analysis of several existing methods and provide more efficient versions. We report encouraging computational results for large-scale problems.     

On Linear-Time Algorithms for the Continuous Quadratic Knapsack Problem

We give a linear time algorithm for the continuous quadratic knapsack problem which is simpler than existing methods and competitive in practice. Encouraging computational results are presented for large-scale problems. The author thanks the Associate Editor and an anonymous referee for their helpful comments.     

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Let S be a set of n points in reals ³ . Let opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n ⁵ ) -time algorithm for computing opt , which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n ^2+δ ) -time algorithm, for any δ>0 , that computes a cylindrical shell of width at most 56opt containing S . Received May 31, 2000, and in revised form October 25, 2000. Online publication August 29, 2001.     

一类P-函数非线性互补问题的宽邻域路径跟踪算法及其计算复杂性

对一致P-函数非线性互补问题,提出了一种新的宽邻域(N-∞(β))路径跟踪算法,并讨论了该算法的收敛性及计算复杂性.分析结果表明,所给方法是一多项式时间算法.     

Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems

The quadratic knapsack problem (QKP) maximizes a quadratic objective function subject to a binary and linear capacity constraint. Due to its simple structure and challenging difficulty, it has been studied intensively during the last two decades. This paper first presents some global optimality conditions for (QKP), which include necessary conditions and sufficient conditions. Then a local optimization method for (QKP) is developed using the necessary global optimality condition. Finally a global optimization method for (QKP) is proposed based on the sufficient global optimality condition, the local optimization method and an auxiliary function. Several numerical examples are given to illustrate the efficiency of the presented optimization methods.     

Some Complexity Results for Polynomial Ideals

In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the rationals. For instance, a polynomial ideal membership problem is a (w+ 1)-tupleP= (f,g₁,g₂, …g_wwherefand theg_iare multivariate polynomials, and the problem is to determine whetherfis in the ideal generated by theg_i. For polynomials over the integers or rationals, this problem is known to be exponential space complete. We discuss further complexity results for problems related to polynomial ideals, like the word and subword problems for commutative semigroups, a quantitative version of Hilbert's Nullstellensatz in a complexity theoretic version, and problems concerning the computation of reduced polynomials and Gröbner bases.     

Exact Simulation Problems for Jump-Diffusions

Exact simulation of SDEs is a very important and challenging problem. In this paper we discuss exact simulation problems for jump-diffusion processes. Motivated by statistical applications, our main contribution is to propose an algorithm that performs exact simulation of a class of jump-diffusion bridges. We also present and discuss the existing methods for forward simulation and propose an extension of one of them to account for unbounded jump rate. Finally, the exact algorithms are compared to competing non-exact ones in some simulated examples.     

Algorithms for Sat and Upper Bounds on Their Complexity

We survey recent algorithms for the propositional satisfiability problem. In particular, we consider algorithms having the best current worst-case upper bounds on their complexity. We also discuss some related issues: a derandomization of the algorithm of Paturi, Pudlák, Saks, and Zane, the Valiant–Vazirani lemma, and random walk algorithms with the back button. Bibliography: 47 titles.     

On the Complexity of Exclusion Algorithms for Optimization

Exclusion algorithms are a well-known tool in the area of interval analysis for finding all solutions of a system of nonlinear equations or for finding the global minimum of a function over a compact domain. The present paper discusses a new class of tests for such algorithms in the context of global optimization and presents complexity results concerning the resulting algorithms.     

The Complexity and Effectiveness of Prediction Algorithms

The problem of predicting an arbitrary sequence x₁x₂x₃ · · · is considered with x_{t + 1} being predicted from an analysis of the word x₁x₂ · · · x_t. There are no presumptions concerning the probability structure on this process. The relation between prediction effectiveness and Kolmogorov complexity is established. Then the Hausdorff dimension of sets of sequences for which effective methods of prediction exist is estimated. The prediction method which is asymptotically superior to other arbitrary ones realized by finite automata is constructed.