Translating statements of symbolic logic into zero-one linear programming

Symbolic logic can be used to translate verbal statements of the optimization problem into an exact mathematical form. There are then three stages in the problem formulation—the verbal stage, the logical stage and the mathematical stage. The purpose of this paper is to translate statements of symbolic logic into the language of zero-one linear programming. Concepts of symbolic logic and zero-one linear programming will be described with examples of translating verbal statements into symbolic logic, and of translating logical statements into a mathematically equivalent form.     

A neural fuzzy control system with structure and parameter learning

A general connectionist model, called neural fuzzy control network (NFCN), is proposed for the realization of a fuzzy logic control system. The proposed NFCN is a feedforward multilayered network which integrates the basic elements and functions of a traditional fuzzy logic controller into a connectionist structure which has distributed learning abilities. The NFCN can be constructed from supervised training examples by machine learning techniques, and the connectionist structure can be trained to develop fuzzy logic rules and find membership functions. Associated with the NFCN is a two-phase hybrid learning algorithm which utilizes unsupervised learning schemes for structure learning and the backpropagation learning scheme for parameter learning. By combining both unsupervised and supervised learning schemes, the learning speed converges much faster than the original backpropagation algorithm. The two-phase hybrid learning algorithm requires exact supervised training data for learning. In some real-time applications, exact training data may be expensive or even impossible to obtain. To solve this problem, a reinforcement neural fuzzy control network (RNFCN) is further proposed. The RNFCN is constructed by integrating two NFCNs, one functioning as a fuzzy predictor and the other as a fuzzy controller. By combining a proposed on-line supervised structure-parameter learning technique, the temporal difference prediction method, and the stochastic exploratory algorithm, a reinforcement learning algorithm is proposed, which can construct a RNFCN automatically and dynamically through a reward-penalty signal (i.e., “good” or “bad” signal). Two examples are presented to illustrate the performance and applicability of the proposed models and learning algorithms.     

Structural filtering: a paradigm for efficient and exact geometric programs

We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called “structural filtering”. Using this filtering technique we gain about 20% when compared to predicate-filtered implementations. Of theoretical interest are some results regarding the robustness of sorting algorithms against erroneous comparisons.

There is software support for the concept of structural filtering in LEDA (Library of Efficient Data Types and Algorithms, http://www.mpi-sb.mpg.de/LEDA/leda.html) and CGAL (Computational Geometry Algorithms Library, http://www.cgal.org).     

Generalizing the modeling of fuzzy logic controllers by parameterized aggregation operators

We describe the type of reasoning used in the typical fuzzy logic controller, the Mamdani reasoning method. We point out the basic assumptions in this model. We discuss the S-OWA operators which provide families of parameterized “andlike” and “orlike” operators. We generalize the Mamdani model by introducing these operators. We introduce a method, which we call Direct Fuzzy Reasoning (DFR), which results from one choice of the parameters. We develop some learning algorithms for the new method. We show how the Takagi-Sugeno-Kang (TSK) method of reasoning is an example of this DFR method.     

Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints

Dynamic Programming is a powerful approach to the optimization of sequential or multistage decision processes, e.g., in planning or in system control. In this paper, we consider both theoretical and algorithmic issues in sequential decision processes under flexible constraints. Such processes must attain a given goal within some tolerance. Tolerances or preferences also apply to the values the decision variables may take or on the action chosen at each step. Such problems boil down to maximin optimization. Unfortunately, this approach suffers from the so-called “drowning effect” (lack of discrimination) and the optimality principle of dynamic programming is not always verified. In this context, we introduce a general framework for refined minimax optimization procedures in order to compare and select preferred alternatives. This framework encompasses already introduced methods such as LexiMin and DiscriMin, but it allows their extension to the comparison of vectors of unequal lengths. We show that these refined comparisons restore compatibility with the optimality principle, and that classical algorithms can be adapted to compute such preferred solutions, by exploiting existing results on idempotent semirings.     

An upper bound for the zero-one knapsack problem and a branch and bound algorithm

A new way of computing the upper bound for the zero-one knapsack problem is presented, substantially improving on Dantzig's approach. A branch and bound algorithm is proposed, based on the above mentioned upper bound and on original backtracking and forward schemes. Extensive computational experiences indicate this new algorithm to be superior to the fastest algorithms known at present.     

Subroutinized tape sorting

The drawbacks of large, general tape sorting programs are pointed out, and a sorting subroutine is suggested as a remedy. The fundamental idea is the separation of the logic in tape sorting from the actual manipulation of external tape units by introduction of the concept of an elementary sorting loop. Examples show how common problems in sorting can be solved using the sorting loop concept. A few considerations in the design and implementation of a sorting subroutine are mentioned, and finally a measure of the efficiency of tape sorting methods is proposed.     

An experimental comparison of four graph drawing algorithms

In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications. The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in “real-life” software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between “aesthetic” properties (e.g., crossings, bends, edge length) and running time.     

Analysis in distribution of two randomized algorithms for finding the maximum in a broadcast communication model

The limit laws of three cost measures are derived of two algorithms for finding the maximum in a single-channel broadcast communication model. Both algorithms use coin flips and comparisons. Besides the ubiquitous normal limit law, the Dickman distribution also appears in a natural way. The method of proof proceeds along the line via the method of moments and the “asymptotic transfers,” which roughly bridges the asymptotics of the “conquering cost of the subproblems” and that of the total cost. Such a general approach has proved very fruitful for a number of problems in the analysis of recursive algorithms.     

Conditional Inference on Tables With Structural Zeros

We develop a set of sequential importance sampling (SIS) strategies for sampling nearly uniformly from two-way zero-one or contingency tables with fixed marginal sums and a given set of structural zeros. The SIS procedure samples tables column by column or cell by cell by using appropriate proposal distributions, and enables us to approximate closely the null distributions of a number of test statistics involved in such tables. When structural zeros are on the diagonal or follow certain patterns, more efficient SIS algorithms are developed which guarantee that every generated table is valid. Examples show that our methods can be applied to make conditional inference on zero-one and contingency tables, and are more efficient than other existing Monte Carlo algorithms.     

Zero-one programming with many variables and few constraints

One of the more successful techniques for solving zero-one integer programs has been the implicit enumeration strategy first introduced by E. Balas. However, experience has shown that the efficiency of these enumerative techniques depends critically upon the bumber of variables. In this paper an algorithm is developed and computational experience provided for solving zero-one integer programs with many variables and few constraints. Sub-problems solved via implicit enumeration are generated from the linear programming relaxation and the variables in these sub-problems correspond to the fractional variables obtained in the linear program. Since the number of fractional variables in the linear program is bounded by the number of constraints in the linear program, the sub-problems will in general contain many fewer variables than the original zero-one integer program.     

The zero-one knapsack problem with equality constraint

The zero-one knapsack problem is a linear zero-one programming problem with a single inequality constraint. This problem has been extensively studied and many applications and efficient algorithms have been published. In this paper we consider a similar problem, one with an equality instead of the inequality constraint. By replacing the equality by two inequalities one of which is placed in the economic function, a Lagrangean relaxation of the problem is obtained. The relation between the relaxed problem and the original problem is examined and it is shown how the optimal value of the relaxed problem varies with increasing values of the Lagrangean multiplier. Using these results an algorithm for solving the problem is proposed.The paper concludes with a discussion of computational experience.     

Convergence of a continuous approach for zero-one programming problems

In this paper a new continuous formulation for the zero-one programming problem is presented, followed by an investigation of the algorithm for it. This paper first reformulates the zero-one programming problem as an equivalent mathematical programs with complementarity constraints, then as a smooth ordinary nonlinear programming problem with the help of the Fischer-Burmeister function. After that the augmented Lagrangian method is introduced to solve the resulting continuous problem, with optimality conditions for the non-smooth augmented Lagrangian problem derived on the basis of approximate smooth variational principle, and with convergence properties established. To our benefit, the sequence of solutions generated converges to feasible solutions of the original problem, which provides a necessary basis for the convergence results.     

Design and analysis of predictive sorting algorithms

The focus of this research is the class of sequential algorithms, called predictive sorting algorithms, for sorting a given set ofn elements using pairwise comparisons. The order in which these pairwise comparisons are made is defined by a fixed sequence of all unordered pairs of distinct integers {1, 2, ...,n} called a sort sequence. A predictive sorting algorithm associated with a sort sequence specifies pairwise comparisons of elements in the input set in the order defined by the sort sequence, except that the comparisons whose outcomes can be inferred from the preceding pairs of comparisons are not performed. In this paper predictive sorting algorithms are obtained, based on known sorting algorithms, and are shown to be required on the averageO(n logn) comparisons.     

The additive multiboxes

We introduce the new notion of additive “multibox” for linear logic proof-nets. Thanks to this notion, we define a cut-elimination procedure which associates with every proof-net of multiplicative and additive linear logic a unique cut-free one.     

An algorithm and efficient data structures for the binary knapsack problem

A branch-and-bound algorithm for the binary knapsack problem is presented which uses a combined stack and deque for storing the tree and the corresponding LP-relaxation. A reduction scheme is used to reduce the problem size. The algorithm was implemented in FORTRAN. Computational experience is based on 600 randomly generated test problems with up to 9000 zero-one variables. The average solution times (excluding an initial sorting step) increase linearly with problem size and compare favorably with other codes designed to solve binary knapsack problems.     

Solving zero-one multiple objective programs through implicit enumeration

Research on algorithms designed to solve zero-one multiple objective linear programs has been rather limited. This paper presents a solution procedure for these problems based on the concept of implicit enumeration. Computational experience is reported and analyzed. Advantages, disadvantages and extensions of the algorithm are discussed.     

Design of fuzzy logic controllers based on generalized T-operators

Since Zadeh first proposed the basic principle of fuzzy logic controllers in 1968, the and operators have been popular in the design of fuzzy logic controllers. In this paper, the general concept of T-operators is introduced into the conventional design methods for fuzzy logic controllers so that a general and flexible methodology for the design of these fuzzy logic controllers is available. Then, by computer simulations, studies are made so as to determine the relations between the various T-operators and the performance of a fuzzy logic controller. It is concluded that the performance of the fuzzy logic controller for a given class of plants very much depends upon the choice of the T-operators.     

A note on solving MINLP’s using formulation space search

In this note we present an approach based on formulation space search to solve mixed-integer nonlinear (zero-one) programming problems. Our approach is an iterative one which adds a single nonlinear inequality constraint of increasing tightness to the original problem. Computational results are presented for our approach on 51 standard benchmark problems taken from MINLPLib. We compare our approach against the Minotaur and minlp_bb nonlinear solvers, as well as against the RECIPE algorithms.     

A Remark on the Computation of Optimum Media Schedules

The media scheduling problem of Ellis is transformed into an integer linear programming problem in zero-one variables. The transformed problem is recognized as the knapsack problem and exact and approximate algorithms are proposed.