A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

Little laws for utility processes and waiting times in queues

Little's law for queueing systems isL=W: the average queue length equals the average arrival rate times the average waiting time in the system. This study gives further insights into techniques for establishing such laws (i.e. establishing the existence of the terms as limiting averages or expectations) and it presents several basic laws for systems with special structures. The main results concern (1) general necessary and sufficient conditions for Little laws for utility processes as well as queueing systems, (2) Little laws for systems that empty out periodically or, more generally, have regular departures and (3) Little laws tailored to regenerative, Markovian and stationary systems.This research was supported in part by the Air Force Office of Scientific Research under contract 91-0013 and NSF grant DDM-9224520.     

Conditions for finite moments of waiting times inG/G/1 queues

We find conditions for E(W ) to be finite whereW is the stationary waiting time random variable in a stableG/G/1 queue with dependent service and inter-arrival times.Supported in part by KBN under grant 640/2/9, and at the Center for Stochastic Processes, Department of Statistics at the University of North Carolina Chapel Hill by the Air Force Office of Scientific Research Grant No. 91-0030 and the Army Research Office Grant No. DAAL09-92-G-0008.     

Method of dual matrices for function minimization

In this paper, the method of dual matrices for the minimization of functions is introduced. The method, which is developed on the model of a quadratic function, is characterized by two matrices at each iteration. One matrix is such that a linearly independent set of directions can be generated, regardless of the stepsize employed. The other matrix is such that, at the point where the first matrix fails to yield a gradient linearly independent of all the previous gradients, it generates a displacement leading to the minimal point. Thus, the one-dimensional search is bypassed. For a quadratic function, it is proved that the minimal point is obtained in at mostn + 1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn + 2.Three algorithms of the method are presented. A reverse algorithm, which permits the use of only one matrix, is also given. Considerations pertaining to the applications of this method to the minimization of a quadratic function and a nonquadratic function are given. It is believed that, since the one-dimensional search can be bypassed, a considerable amount of computational saving can be achieved.This paper, supported by the National Science Foundation, Grant No. GP-32453, is based on Ref. 1.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

The role of repair strategy in warranty cost minimization: An investigation via quasi-renewal processes

Most companies seek efficient rectification strategies to keep their warranty related costs under control. This study develops and investigates different repair strategies for one- and two-dimensional warranties with the objective of minimizing manufacturer’s expected warranty cost. Static, improved and dynamic repair strategies are proposed and analyzed under different warranty structures. Numerical experimentation with representative cost functions indicates that performance of the policies depend on various factors such as product reliability, structure of the cost function and type of the warranty contract.     

New variants of the generalized level method for minimization of convex nondifferentiable functions taking infinite values

New variants of the generalized level method for minimization of convex Lipschitz functions on a compact set with a nonempty interior are proposed. These variants include the well-known generalized and classical level methods. For the new variants, an estimate of the convergence rate is found, including the variants in which the auxiliary problems are solved approximately.     

Estimation and decomposition of cost efficiency in the health care food service sector: an extended stochastic frontier approach

K. M. Matawie School of Computing and Mathematics, University of Western Sydney, Locked Bag 1797, Penrith South DC NSW 1797, Australia Email: a.assaf{at}uws.edu.au Corresponding author. Email: k.matawie{at}uws.edu.au Received on 11 February 2007. Accepted on 14 September 2007. This paper introduces and implements an extended stochasticfrontier model to estimate and decompose cost efficiency (CE)in the health care foodservice sector. The interesting featureof this model is that it allows differentiation between thethree different types of efficiency: technical efficiency (TE),allocative efficiency (AE) and their associated CE. A completeillustration of these efficiencies is presented using a cross-sectionalsample of 101 hospital foodservice operations. Results showedthat the model and all its parameter coefficients were plausible,significant and satisfy all theoretical requirements. It wasalso clear that the average efficiency scores were lower forTE (80%) than AE (88%), indicating that TE is the main sourceof CE and requires further attention.     

An improved version of the original leap-frog dynamic method for unconstrained minimization: LFOP1(b)

A modified version of the author's original dynamic algorithm for unconstrained minimization is proposed. It employs time step selection procedure which results in a more efficient utilization of the original dynamic algorithm. The performance of the new algorithm is compared with that of a well established conjugate gradient algorithm when applied to three different extended test functions. Based on a comparison of the respective CPU times required for convergence, the new algorithm appears to be competitive.     

Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

Solutions of learning problems by Empirical Risk Minimization (ERM) – and almost-ERM when the minimizer does not exist – need to be consistent, so that they may be predictive. They also need to be well-posed in the sense of being stable, so that they might be used robustly. We propose a statistical form of stability, defined as leave-one-out (LOO) stability. We prove that for bounded loss classes LOO stability is (a) sufficient for generalization, that is convergence in probability of the empirical error to the expected error, for any algorithm satisfying it and, (b) necessary and sufficient for consistency of ERM. Thus LOO stability is a weak form of stability that represents a sufficient condition for generalization for symmetric learning algorithms while subsuming the classical conditions for consistency of ERM. In particular, we conclude that a certain form of well-posedness and consistency are equivalent for ERM. Dedicated to Charles A. Micchelli on his 60th birthday Mathematics subject classifications (2000) 68T05, 68T10, 68Q32, 62M20. Tomaso Poggio: Corresponding author.     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

Zeros in tables of characters for the groups Sn and An

In the representation theory of symmetric groups, for each partition of a natural number n, the partition h() of n is defined so as to obtain a certain set of zeros in the table of characters for S_n. Namely, h() is the greatest (under the lexicographic ordering ) partition among P(n) such that (g) 0. Here, is an irreducible character of S_n, indexed by a partition , and g is a conjugacy class of elements in S_n, indexed by a partition . We point out an extra set of zeros in the table that we are dealing with. For every non self-associated partition P(n), the partition f() of n is defined so that f() is greatest among the partitions of n which are opposite in sign to h() and are such that (g) 0 (Thm. 1). Also, for any self-associated partition of n > 1, we construct a partition () P(n) such that () is greatest among the partitions of n which are distinct from h() and are such that (g) 0 (Thm. 2).Supported by RFBR grant No. 04-01-00463 and by RFBR-BRFBR grant No. 04-01-81001.Translated from Algebra i Logika, Vol. 44, No. 1, pp. 24–43, January–February, 2005.     

A conjugate gradient method for the unconstrained minimization of strictly convex quadratic splines

In this paper, we show that an analogue of the classical conjugate gradient method converges linearly when applied to solving the problem of unconstrained minimization of a strictly convex quadratic spline. Since a strictly convex quadratic program with simple bound constraints can be reformulated as unconstrained minimization of a strictly convex quadratic spline, the conjugate gradient method is used to solve the unconstrained reformulation and find the solution of the original quadratic program. In particular, if the solution of the original quadratic program is nondegenerate, then the conjugate gradient method finds the solution in a finite number of iterations. This author's research is partially supported by the NASA/Langley Research Center under grant NCC-1-68 Supplement-15.     

The time path of the marginal cost of oil: The turning point and the subsequent upward drift

The gradual exhaustion of existing deposits of a depletable non-renewable resource such as oil tends to shift the supply price curve of the resource upwards, increasing its marginal cost. Advances in technologies for exploration and production act as a brake on such upward shifts. Thus, there is a tug-of-war between the gradual exhaustion of existing deposits and technological progress. Using a recently developed constrained least-squares regression technique, we demonstrate that technological progress was the dominant force of the two during the first part of this century, causing a secular drop in marginal costs, but that this situation eventually was reversed, and that the gradual exhaustion of deposits gained the upper hand, causing marginal costs to increase. The turning point occurred around 1971–72. We also discuss the forecasting of the possible current upward drift of marginal costs.     

An approximation procedure for solutions to Mayer problems with cost functional not of classC

We consider here control problems in the Mayer form, with a cost functional which is continuous, but not necessarily of classC ¹. The usual necessary conditions for such problems cannot be applied, since they require that the cost functional beC ¹. We describe a convergence procedure, based upon approximations to the cost functional, that will yield an optimal trajectory to such control systems. Criteria are given which justify that this approximation procedure will yield a trajectory and control, satisfying certain prescribed conditions, which minimize the above cost functional within a specified class of such pairs. Examples are presented.