A o(n logn) algorithm for LP knapsacks with GUB constraints

A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0–1 Multiple Choice integer programming problems. We provide computational bounds for our method of o(n logn), wheren is the total number of problem variables. These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem (due to Witzgall) and provide connections to computational bounds for the ordinary knapsack problem.We further provide a variant of our method which has only slightly inferior worst case bounds, yet which is ideally suited to solving integer multiple choice problems due to its ability to post-optimize while retaining variables otherwise weeded out by convex dominance criteria.     

On tightening cover induced inequalities

Here we describe computationally efficient procedures for tightening cover induced inequalities by using 0–1 knapsack constraints and, if available, cliques whose variables are included in the cover. An interesting application is the case where the cover is implied by the knapsack constraint. The tightening is achieved by increasing the coefficients of the cover inequality. The new constraint is 0–1 equivalent to and LP tighter than the original one. The computational complexity of the procedures is O(n log n), where n is the number of variables in the cover.     

On Maximizing Discrimination in Multiple Criteria Decision Making

We examine an LP/DEA-based technique for establishing an overall ranking of alternatives that are ranked on multiple criteria, which themselves are ranked. This two-stage process involves one LP in the first stage, and N LPs in the second stage to rank N alternatives. We find that the information from N + 1 LPs can be obtained by solving two LPs. In many cases, the solution of one LP, which can be done by inspection, is almost as informative as the two-stage procedure. We also indicate when the second stage would be redundant. If maximum technical discrimination between the alternatives is sought, we consider how this might be achieved by aggressive cross-evaluation via N LPs. We also show how to identify a subset of the alternatives that would be ranked in the first place under any ordering of the criteria, and thus play an important role in the evaluation procedure.     

Algorithms for approximate calculation of the minimum of a convex function from its values

The paper deals with a numerical minimization problem for a convex function defined on a convexn-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity asn is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved fromCn ⁷ ln²(n+1) [4] toCn ² ln(n+1).Translated fromMatematicheskie Zametki, Vol. 59, No. 1, pp. 95–102, January, 1996.     

Laurent–Padé Approximants to Four Kinds of Chebyshev Polynomial Expansions. Part I. Maehly Type Approximants

Laurent Padé–Chebyshev rational approximants, A _m (z,z ^–1)/B _n (z,z ^–1), whose Laurent series expansions match that of a given function f(z,z ^–1) up to as high a degree in z,z ^–1 as possible, were introduced for first kind Chebyshev polynomials by Clenshaw and Lord [2] and, using Laurent series, by Gragg and Johnson [4]. Further real and complex extensions, based mainly on trigonometric expansions, were discussed by Chisholm and Common [1]. All of these methods require knowledge of Chebyshev coefficients of f up to degree m+n. Earlier, Maehly [5] introduced Padé approximants of the same form, which matched expansions between f(z,z ^–1)B _n (z,z ^–1) and A _m (z,z ^–1). The derivation was relatively simple but required knowledge of Chebyshev coefficients of f up to degree m+2n. In the present paper, Padé–Chebyshev approximants are developed not only to first, but also to second, third and fourth kind Chebyshev polynomial series, based throughout on Laurent series representations of the Maehly type. The procedures for developing the Padé–Chebyshev coefficients are similar to that for a traditional Padé approximant based on power series [8] but with essential modifications. By equating series coefficients and combining equations appropriately, a linear system of equations is successfully developed into two sub-systems, one for determining the denominator coefficients only and one for explicitly defining the numerator coefficients in terms of the denominator coefficients. In all cases, a type (m,n) Padé–Chebyshev approximant, of degree m in the numerator and n in the denominator, is matched to the Chebyshev series up to terms of degree m+n, based on knowledge of the Chebyshev coefficients up to degree m+2n. Numerical tests are carried out on all four Padé–Chebyshev approximants, and results are outstanding, with some formidable improvements being achieved over partial sums of Laurent–Chebyshev series on a variety of functions. In part II of this paper [7] Padé–Chebyshev approximants of Clenshaw–Lord type will be developed for the four kinds of Chebyshev series and compared with those of the Maehly type.     

Robust discrete optimization and network flows

We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0–1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0–1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard -approximable 0–1 discrete optimization problem, remains -approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network. The research of the author was partially supported by the Singapore-MIT alliance.The research of the author is supported by a graduate scholarship from the National University of Singapore.Mathematics Subject Classification (2000): 90C10, 90C15     

Global optimal solutions to a class of quadrinomial minimization problems with one quadratic constraint

This paper studies the canonical duality theory for solving a class of quadrinomial minimization problems subject to one general quadratic constraint. It is shown that the nonconvex primal problem in \mathbb Rⁿ{\mathbb {R}^n} can be converted into a concave maximization dual problem over a convex set in \mathbb R²{\mathbb {R}^2}, such that the problem can be solved more efficiently. The existence and uniqueness theorems of global minimizers are provided using the triality theory. Examples are given to illustrate the results obtained.     

Average number of iterations of some polynomial interior-point ——Algorithms for linear programming

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the average number of iterations of these algorithms, coupled with a finite termination technique, is bounded above byO(n ^1.5). The random LP problem is Todd’s probabilistic model with the standard Gauss distribution.     

Projection method for unconstrained optimization

A method of conjugate directions, the projection method, for solving unconstrained minimization problems is presented. Under the assumption of uniform strict convexity, the method is shown to converge to the global minimizer of the unconstrained problem and to have an (n – 1)-step superlinear rate of convergence. With a Lipschitz condition on the second derivatives, the rate of convergence is shown to be a modifiedn-step quadratic one.This research was supported in part by the Army Research Office, Contract No. DAHC 19-69-C-0017, and the Office of Naval Research, Contract No. N00014-71-C-0116(NR-047-099).     

New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

Busy period analysis of queue: Lattice path approach

In this paper, we find the busy period density of queues in explicit computational form, through lattice path (LP) approach. Both the arrival and service time distributions are approximated by 2-phase Cox distribution C₂, which has a Markovian property enabling us to use LP combinatorics. Since any distribution with rational Laplace–Stieltjes transform (LST) and square coefficient of variation (CV²) lying in [1/2,∞) can be approximated by a C₂([M. Agarwal, K. Sen, B. Borkakaty, Busy period density of queueing system C₃/M/1, Journal of Combinatorics, Information and Systems Sciences 31 (1–4) (2006) 127–161]), the results obtained would be applicable to a very wide class of distributions occurring in real life.     

Strongly essential coalitions and the nucleolus of peer group games

Most of the known efficient algorithms designed to compute the nucleolus for special classes of balanced games are based on two facts: (i) in any balanced game, the coalitions which actually determine the nucleolus are essential; and (ii) all essential coalitions in any of the games in the class belong to a prespecified collection of size polynomial in the number of players. We consider a subclass of essential coalitions, called strongly essential coalitions, and show that in any game, the collection of strongly essential coalitions contains all the coalitions which actually determine the core, and in case the core is not empty, the nucleolus and the kernelcore. As an application, we consider peer group games, and show that they admit at most 2n−1 strongly essential coalitions, whereas the number of essential coalitions could be as much as 2ⁿ⁻¹. We propose an algorithm that computes the nucleolus of an n-player peer group game in time directly from the data of the underlying peer group situation.Research supported in part by OTKA grant T030945. The authors thank a referee and the editor for their suggestions on how to improve the presentation     

Pointwise estimation of comonotone approximation

We prove that, for a continuous functionf(x) defined on the interval [–1,1] and having finitely many intervals where it is either nonincreasing or nondecreasing, one can always find a sequence of polynomialsP _n (x) with the same local properties of monotonicity as the functionf(x) and such that ¦f(x)–P _n (x) ¦C₂(f;n^–2+n ^–11–x ²), whereC is a constant that depends on the length of the smallest interval.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 11, pp. 1467–1472, November, 1994.The author is grateful to Prof. I. A. Shevchuk for his permanent attention to the work.     

Geometric convergence to e−z by rational functions with real poles

Summary In this paper, we show that there exists a sequence of rational functions of the formR _n(z)=p_n–1(z)/(1+z/n)ⁿ,n=1, 2, ..., with degp _n–1n–1, which converges geometrically toe ^–z in the uniform norm on [0, +), as well as on some infinite sector symmetric about the positive real axis. We also discuss the usefulness of such rational functions in approximating the solutions of heat-conduction type problems.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2688, and by the University of South Florida Research Council.Research supported in part by the Air Force Office of Scientific Research under Grant AFOSR-74-2729, and by the Energy Research and Development Administration (ERDA) under Grant E(11-1)-2075.     

Aitken acceleration of some alternating series

Aitken's ²-process is applied to a convergent sequence {s _n }, wheres _n =u ₁ –u ₂+...+(–1) ^n–1 u _n . The improvement in the rate of convergence of {s _n } is measured in terms of the functionu and its derivatives and numerical examples are given. The paper concludes with a theorem showing that the Aitken process is well-conditioned in such problems and this theorem is shown to have wider applications.     

On-line algorithms for networks of temporal constraints

We consider a semi-dynamic setting for the Temporal Constraint Satisfaction Problem (TCSP), where we are requested to maintain the path-consistency of a network under a sequence of insertions of new (further) constraints between pairs of variables. We show how to maintain the path-consistency in O(nR³) amortized time on a sequence of Θ(n²) insertions, where n is the number of vertices of the network and R is its range, defined as the maximum size of the minimum interval containing all the intervals of a single constraint.Furthermore we extend our algorithms to deal with more general temporal networks where variables can be points and/or intervals and constraints can also be defined on pairs of different kinds of variables. For such cases our algorithms maintain their performance. Finally, we adapt our algorithms to also maintain the arc-consistency of such generalized networks in O(R) amortized time for Θ(n²) insertions.     

On an integral transform with generalized associated Legendre functions

We study some new properties of generalized associated Legendre functions of first and second kind P _k ^m,n (z) and Q _k ^m,n (z). Applying these functions, we introduce an integral transform that can be used in solving boundary-value problems of mathematical physics.Translated fromVychislitel'naya i Prikladnaya Matematika, Issue 71, 1990, pp. 33–43.     

Batched dynamic solutions to decomposable searching problems

The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlog^d−1n + k) time using only O(n) space.     

An asymptotically complete class of tests

Summary This paper investigates sequences of asymptotically similar critical regions {S _n >0},n, under the assumption that the test-statisticS _n admits a certain stochastic expansion. It is shown that for such test-sequences, first order efficiency implies second order efficiency (i.e. efficiency up to an error termo(n ^–1/2)). Moreover, the asymptotic power functions of first order efficient test-sequences are determined up to an error termo(n ^–1), and a class of critical regions is specified which is minimal essentially complete up too(n ^–1).The results of this paper rest upon the technique of Edgeworth-expansions and are, therefore, restricted to continuous probability distributions.     

On the nucleolus of NTU-games defined by multiple objective linear programs

In this article we derive a class of cooperative games with non-transferable utility from multiple objective linear programs. This is done in order to introduce the nucleolus, a solution concept from cooperative game theory, as a solution to multiple objective linear problems.We show that the nucleolus of such a game is a singleton, which is characterized by inclusion in the least core and the reduced game property. Furthermore the nucleolus satisfies efficiency, anonymity and strategic equivalence.We also present a polynomially bounded algorithm for computation of the nucleolus. Letn be the number of objective functions. The nucleolus is obtained by solving at most2n linear programs. Initially the ideal point is computed by solvingn linear programs. Then a sequence of at mostn linear programs is solved, and the nucleolus is obtained as the unique solution of the last program.Financial support from Nordic Academy for Advanced Study (NorFA) is gratefully acknowledged. Part of this work was done during autumn 1993 at Institute of Finance and Management Science, Norwegian School of Economics and Business Administration.