Linear 0–1 programming: A comparison of implicit enumeration algorithms

This paper compares the following implicit enumeration algorithms for solving a linear zero-one programming (LZOP) problem: Balas' additive algorithm, Hammer-Rudeanu's algorithm, Peterson's algorithm, Zionts' generalized additive algorithm, Geoffrion's improved implicit enumeration algorithm and Zionts' generalized additive algorithm with surrogate constraints. The computational efficiency of these algorithms is compared in terms of computer time and the number of iterations required to solve unstructured problems. Some guidelines for selecting an appropriate algorithm for a given problem size are given.     

Increasing tree search efficiency for constraint satisfaction problems

In this paper we explore the number of tree search operations required to solve binary constraint satisfaction problems. We show analytically and experimentally that the two principles of first trying the places most likely to fail and remembering what has been done to avoid repeating the same mistake twice improve the standard backtracking search. We experimentally show that a lookahead procedure called forward checking (to anticipate the future) which employs the most likely to fail principle performs better than standard backtracking, Ullman's, Waltz's, Mackworth's, and Haralick's discrete relaxation in all cases tested, and better than Gaschnig's backmarking in the larger problems.     

Substitution of semi-AFL's

S.A. Greibach proved in “Chains of full AFL's” a very useful property concerning substitution of full semi-AFL's.S. Ginsburg raises the question whether the property remains true when the families under considerations are supposed only to be semi-AFL's.We give here a negative answer to this question.     

Non deterministic polynomial optimization problems and their approximations

A unified and general framework for the study of nondeterministic polynomial optimization problems (NPOP) is presented and some properties of NPOP's are investigated. A characterization of NPOP's with regard to their approximability properties is given by proving necessary and sufficient conditions for two approximability schemes. Known approximability results are shown to fit within the general frame developed in the paper. Finally NPOP's are classified and studied with regard to the possibility or impossibility of ‘reducing’ certain types of NPOP's to other types in a sense specified in the text.     

On data dependency structures of relational databases

The properties of the set of all functional dependencies (which is defined to be FD sub-structure), derivable from a given set of functional dependencies (FD's) and multivalued dependencies (MVD's) for a relational database, are studied. A necessary and sufficient condition that a set of FD's is a cover for the FD sub-structure is proved, which can be tested for validity by an efficient algorithm. An algorithm of generating a cover for the FD substructure is presented. It can be shown, however, that in at least one instance, the number of FD's in the cover may actually increase more than exponentially as the number of MVD's increases.     

Algorithmes relatifs a la decomposition des polynomes

Améliorations et remarques sur un algorithme dû à H. Zassenhaus, qui fournit la factorisation d'un polynôme à coeffecients entiers. Puis un algorithme très rapide et très simple qui donne des informations utiles sur la décomposition d'un polynôme modulo p. Applications: tests modulo p d'irréductibilité, de décomposition en facteurs linéaires d'un polynôme, de décomposition d'un idéal en O (log p) opérations.     

The end of the virus problem

Do you remember what it was like before viruses came along? You could get a disk, and just bung it in, no worries. Someone gave you a program, you'd just run it, no sweat. Someone sent you a document, you'd just read it on your word processor, you didn't have to take it to MIS to get it virus checked first. Do you remember those days? A lot of people do, but viruses have been around so long now, that a lot of people don't go back that far.     

Hoare's logic and Peano's arithmetic

We develop the proof theory of Hoare's logic for the partial correctness of while- programs applied to arithmetic as it is defined by Peano's axioms. By representing the strongest postcondition calculus in Peano arithmetic PA, we are able to show that Hoare's logic over PA is equivalent to PA itself.     

A note on three-dimensional finite automata

This paper investigates the relationships between the accepting powers of three-dimensional six-way finite automata (3-FA's) and three-dimensional five-way Turing machines (5WTM's), where the input tapes of these automata are restricted to cubic ones. A 3-FA (5WTM) can be considered as a natural extension of the two-dimensional four-way finite automaton (two-dimensional three-way Turing machine) to three dimensions. The main results are: (1) n²logn (n³) space is necessary and sufficient for deterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's; (2) n² (n²) space is necessary and sufficient for nondeterministic 5WTM's to simulate deterministic (nondeterministic) 3-FA's.     

Discrete hill's equations

In the work, based on the formulas of discrete mechanics in a rotating frame, a discretization of classical Hill's equations of the moon motion is worked out. It is proved that the proposed discretization conserves Jacobi's constant of motion. For computational purposes an algorithm to the solution of obtained discrete Hill's equations is given.     

Modified approach to trigg and leach's adaptive response rate model

Trigg and Leach's model is simple to implement in an industrial environment and has been found to be well suited for producing routine short-term forecasts of a large number of items. In this paper two modifications to Trigg and Leach's model are proposed with a view to improving its performance under a variety of demand situations. Both the modifications are done on the basis of a comparison between the current and past period's forecast errors. While the first modification suggests as to how to choose the value of the smoothing constant to be used for forecasting, the second one suggests how to update its value from one period to another.Both the proposed modified model and the original Trigg and Leach's model have been tested on a number of demand situations. Using the criterion of mean error variance, it has been shown that the performance of the modified model is consistently better compared to that of the original Trigg and Leach's model. It is, therefore, believed that better forecasts are likely to result if Trigg and Leach's model incorporating the proposed two modifications, is used in place of their original model.     

An exercise in program synthesis: algorithms for computing the transitive closure of a relation

This paper contains the synthesis of several transitive closure algorithms (including Warshall's) from one common high level definition.For deriving recursion equations Burstall's and Darlington's unfolding-and folding-technique is used. A special effort is made to treat the first step of the syntheses (i.e. finding appropriate recursion arguments) systematically.     

Different ways to find the thermodynamic functions describing the formation of binary alloys: part 1 comparison between models and experimental data

The thermodynamic functions describing the formation of binary alloys are known for only a small part of all the systems. Models are in many cases the only way to find thermodynamic data. Two models, MIEDEMA's on the one hand and BENNETT's and WATSON's on the other hand are compared with new experimental data to characterize their accuracy and reliability, in regard of the experimental difficulties.     

A FARES baseline analysis case study

After a one-month hiatus we're back to work on FARES, the Forensic Analysis of Risks in Enterprise Systems. We've seen in previous months how the FARES process works and what it comprises. This month we'll wrap up this topic with a case study of a FARES baseline analysis for a mid-sized financial services company. We begin with a very brief review of the FARES process.     

On the use of the quadratic functional and its derived principles in structural mechanics

In this paper the varied form of the quadratic functional is used to derive several principles. Some of them, such as Alambert's, Jourdain's and Gauss' principles are being used currently. The corresponding approximate methods of solution are obtained by employing suitable trial functions and are illustrated by solving two problems. These methods are applicable to linear and nonlinear problems as well as to nonconservative ones.     

A non-conforming finite element method for solving a least-square formulation of tricomi's problem

The purpose of this work is to solve in the plane Tricomi's equation of mixed type by means of global least-square formulation. The resolution is obtained with Zienkiewicz's finite element which verifies the patch test, and the incomplete Cholesky conjugate gradient algorithm (ICCG) yields very fast convergence. The least-square formulation is still applicable when a non-linear term is introduced, and the solution is searched for by Newton's method.     

Congress growing frustrated over US crypto policies

Bipartisan frustration with the Clinton administration's current policies on encryption were evident as Representative Bob Goodlatte's “Security and Freedom Through Encryption Act” (the “SAFE” Act — House Resolution 850) made its way through hearings in the House International Relations Committee's Subcommittee on International Economic Policy and Trade.     

On the work theorems for finite and incremental elastic deformations with discontinuous fields: A unified treatment of different versions

Starting from the statical and kinematical relations in three different versions characterized by the use of Piola's, Kirchhoff's or Biot's (Jaumann's) stresses respectively and the corresponding deformation quantities a unified abstract formulation of the basic equations is given. Because of certain properties of the statical and geometrical operators various material independent work theorems follow including the (generalized and modified) principles of virtual displacements and virtual forces. For a hyperelastic body under conservative loading these are transformed into generalized variational principles and strengthened to complementary extremum principles. Finally the abstract formulation is applied to the incremental equations. The admissible functions are allowed to have relaxed continuity properties. Therefore the presented work theorems may be used as a basis for a consistent finite element approximation according to the mixed version or to the classical displacement formulation.     

Mixed finite elements based upon marguerre theory for the study of geometrically nonlinear behavior of thin shells

Simple triangular and quadrangular finite elements based on Marguerre's theory are proposed and are shown to greatly improve the solution over plane shell elements for a small additional computation cost.Several features of the developments are worth noting, namely: The presentation of a dual approach for the derivation of Marguerre's theory of shallow shells with moderate rotations, based on Fraeijs de Veubeke's variational principle, with a precise statement of hypotheses and applicability; the choice of hybrid connectors for solving the compatibility problem generated by Kirchhoff's hypothesis; a treatment of pressure loading, body forces and inextensional bending modes which employs a ‘static approach’ for the membrane; and discussion about the performance of some algorithms used to solve elastic stability problems. Numerical studies indicate that accurate results may be obtained by the approach advocated.     

Simulation validation with sparse random data

A simulation validation technique based on Theil's inequality coefficient (TIC) is developed for handling correlated random time-series having only sparse data sets. Specifically, a new TIC estimate containing unbiased system and model component variance estimates is derived. Comparisons with this new estimate for serially correlated data indicate that Theil's original inequality coefficient is quite robust with respect to the assumption of utilizing only independent data points. Initially, Theil's inequality coefficient is related to familiar error variance concepts. Thereafter, the new TIC estimate for sparse correlated data sets is derived, and the corresponding continuous formulas for component variance estimates are identified. A grouping procedure is then used to determine confidence intervals in these sparse data cases. Several examples are provided througout to illustrate the special utility of Theil's inequality coefficient for simulation validation.