Convergence of the cyclical relaxation method for linear inequalities

The relaxation method for linear inequalities is studied and new bounds on convergence obtained. An asymptotically tight estimate is given for the case when the inequalities are processed in a cyclical order. An improvement of the estimate by an order of magnitude takes place if strong underrelaxation is used. Bounds on convergence usually involve the so-called condition number of a system of linear inequalities, which we estimate in terms of their coefficient matrix. Paper presented at the XI. International Symposium on Mathematical Programming, Bonn, August 23–27, 1982.     

Bounds for the optimal critical claim size of a bonus system

The optimal critical claim size of a bonus system determines whether to file a claim with the insurance company after having an accident. The aim of this paper is to demonstrate, within the framework of a simple model, how bounds for the optimal critical claim size can be constructed when only incomplete information on the claim amount distribution is available.     

Paired-Domination in <Emphasis Type="Italic">P</Emphasis><Subscript>5</Subscript>-Free Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. In [1], the authors gave tight bounds for paired-dominating sets of generalized claw-free graphs. Yet, the critical cases are not claws but subdivided stars. We here give a bound for graphs containing no induced P ₅, which seems to be the critical case.     

Rigorous Bounds on the Torsional Rigidity of Composite Shafts with Imperfect Interfaces

We derive upper and lower bounds for the torsional rigidity of cylindrical shafts with arbitrary cross-section containing a number of fibers with circular cross-section. Each fiber may have different constituent materials with different radius. At the interfaces between the fibers and the host matrix two kinds of imperfect interfaces are considered: one which models a thin interphase of low shear modulus and one which models a thin interphase of high shear modulus. Both types of interface will be characterized by an interface parameter which measures the stiffness of the interface. The exact expressions for the upper and lower bounds of the composite shaft depend on the constituent shear moduli, the absolute sizes and locations of the fibers, interface parameters, and the cross-sectional shape of the host shaft. Simplified expressions are also deduced for shafts with perfect bonding interfaces and for shafts with circular cross-section. The effects of the imperfect bonding are illustrated for a circular shaft containing a non-centered fiber. We find that when an additional constraint between the constituent properties of the phases is fulfilled for circular shafts, the upper and lower bounds will coincide. In the latter situation, the fibers are neutral inclusions under torsion and the bounds recover the previously known exact torsional rigidity.      

An implementation of the simplex method for linear programming problems with variable upper bounds

Special methods for dealing with constraints of the formx _j x _k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constraints and show how it can be implemented using triangular basis factorizations.This research was partially supported by National Science Foundation Grant ECS-7921279 and by a Guggenheim fellowship.     

Implicit representation of generalized variable upper bounds using the elimination form of the inverse on secondary storage

A constraint of a linear program is called a generalized variable upper bound (GVUB) constraint, if the right-hand is nonnegative and each variable with a positive coefficient in the constraint does not have a nonzero coefficient in any other GVUB constraint. Schrage has shown how to handle GVUB constraints implicitly in the simplex-method. It is demonstrated in this paper that the Forrest-Tomlin data structure may be used for the inverse of the working basis, and it is discussed how to update this representation from iteration to iteration.     

Bounds for the additional cost of near-optimal controls

Near-optimal controls are considered for singular problems with a constrained control. These controls result in a higher cost than the optimal cost. Bounds for the additional cost are derived for problems with fixed terminal time or free terminal time and for minimal time problems. An illustrative example is solved of an optimal evasive control of an aircraft against a homing missile.     

On estimates for integral solutions of linear inequalities

Recently, Bombieri and Vaaler obtained an interesting adelic formulation of the first and the second theorems of Minkowski in the Geometry of Numbers and derived an effective formulation of the well-known “Siegel’s lemma” on the size of integral solutions of linear equations. In a similar context involving linearinequalities, this paper is concerned with an analogue of a theorem of Khintchine on integral solutions for inequalities arising from systems of linear forms and also with an analogue of a Kronecker-type theorem with regard to euclidean frames of integral vectors. The proof of the former theorem invokes Bombieri-Vaaler’s adelic formulation of Minkowski’s theorem.     

Aggregation and discretization in multistage stochastic programming

Multistage stochastic programs have applications in many areas and support policy makers in finding rational decisions that hedge against unforeseen negative events. In order to ensure computational tractability, continuous-state stochastic programs are usually discretized; and frequently, the curse of dimensionality dictates that decision stages must be aggregated. In this article we construct two discrete, stage-aggregated stochastic programs which provide upper and lower bounds on the optimal value of the original problem. The approximate problems involve finitely many decisions and constraints, thus principally allowing for numerical solution.