Polynomial algorithms for linear programming over the algebraic numbers

We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.This research was founded by the National Science Foundation under Grant DMS88-10192.     

Symbolic decision procedure for termination of linear programs

Tiwari proved that the termination of a class of linear programs is decidable in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The decision procedure proposed therein depends on the computation of Jordan forms. Thus, people may draw a wrong conclusion from this procedure, if they simply apply floating-point computation to compute Jordan forms. In this paper, we first use an example to explain this problem, and then present a symbolic implementation of the decision procedure. Thus, the rounding error problem is therefore avoided. Moreover, we also show that the symbolic decision procedure is as efficient as the numerical one given in Tiwari (Proceedings of CAV’04. Lecture notes in computer science, vol 3114, pp 70–82, 2004). The complexity of former is max{O(n ⁶), O(n ^m+3)}, while that of the latter is O(n ^m+3), where n is the number of variables of the program and m is the number of its Boolean conditions. In addition, for the case when the characteristic polynomial of the assignment matrix is irreducible, we design a more efficient symbolic algorithm whose complexity is max(O(n ⁶), O(mn ³)).     

The alternation hierarchy for sublogarithmic space is infinite

The alternation hierarchy for Turing machines with a space bound between loglog and log is infinite. That applies to all common concepts, especially a) to two-way machines with weak space-bounds, b) to two-way machines with strong space-bounds, and c) to one-way machines with weak space-bounds. In all of these cases the _k -and II _k -classes are not comparable fork>-2. Furthermore the _k -classes are not closed under intersection and the II _k -classes are not closed under union. Thus these classes are not closed under complementation. The hierarchy results also apply to classes determined by an alternation depth which is a function depending on the input rather than on a constant.     

A new version of the Improved Primal Simplex for degenerate linear programs

The Improved Primal Simplex (IPS) algorithm [Elhallaoui I, Metrane A, Desaulniers G, Soumis F. An Improved Primal Simplex algorithm for degenerate linear programs. SIAM Journal of Optimization, submitted for publication] is a dynamic constraint reduction method particularly effective on degenerate linear programs. It is able to achieve a reduction in CPU time of over a factor of three on some problems compared to the commercial implementation of the simplex method CPLEX. We present a number of further improvements and effective parameter choices for IPS. On certain types of degenerate problems, our improvements yield CPU times lower than those of CPLEX by a factor of 12.     

Novel linear programming approach for building a piecewise nonlinear binary classifier with a priori accuracy

This paper describes a novel approach to build a piecewise (non)linear surface that separates individuals from two classes with an a priori classification accuracy. In particular, total classification with a good generalization level can be obtained, provided no individual belongs to both classes. The method is iterative: at each iteration a new piece of the surface is found via the solution of a Linear Programming model. Theoretically, the larger the number of iterations, the better the classification accuracy in the training set; numerically, we also found that the generalization ability does not deteriorate on the cases tested. Nonetheless, we have included a procedure that computes a lower bound to the number of errors that will be generated in any given validation set. If needed, an early stopping criterion is provided. We also showed that each piece of the discriminating surface is equivalent to a neuron of a feed forward neural network (FFNN); so as a byproduct we are providing a novel training scheme for FFNNs that avoids the minimization of non convex functions which, in general, present many local minima.We compare this algorithm with a new linear SVM that needs no pre tuning and has an excellent performance on standard and synthetic data. Highly encouraging numerical results are reported on synthetic examples, on the Japanese Bank dataset, and on medium and small datasets from the Irvine repository of machine learning databases.     

On implementing a computation

To clarify the notion of computation and its role in cognitive science, we need an account of implementation, the nexus between abstract computations and physical systems. I provide such an account, based on the idea that a physical system implements a computation if the causal structure of the system mirrors the formal structure of the computation. The account is developed for the class of combinatorial-state automata, but is sufficiently general to cover all other discrete computational formalisms. The implementation relation is non-vacuous, so that criticisms by Searle and others fail. This account of computation can be extended to justify the foundational role of computation in artificial intelligence and cognitive science.     

On an optimal linear pattern classification procedure

The problem of Optimal Linear Discrimination for 3-class pattern recognition is attacked. The Linear Discrimination Rule, under those circumstances, is devised according to the following optimality criterion: maximize the probability of correct classification into any one of the three classes, while keeping the other two such probabilities fixed.An explicit solution of the problem is given, and a search technique is implemented greatly reducing the problem complexity.     

Leveraging technological knowledge transfer by using fuzzy linear programming technique for multiattribute group decision making with fuzzy decision variables

Despite the importance of knowledge transfer for firms involved in foreign direct investment activities, this area has not received appropriate attention from the perspectives of both the knowledge transferor (i.e., MNC parent) and the knowledge recipient. To fill in the gap in the current literature we propose a model to understand the links between criteria complicating the transfer of knowledge and preferences that the company has to focus. This model is based on both the existing literature as well as views of company representatives and provides a useful methodology for identifying decision making problems on the transfer of knowledge. In this paper, we investigate the fuzzy linear programming technique (FLP) to analyze these links and for multiple attribute group decision making (MAGDM) problems with preference information on criteria. To reflect the decision maker’s subjective preference information and to determine the weight vector of attributes, the technique for order preference by similarity to ideal solution (TOPSIS) developed by Hwang and Yoon (1995) and the linear programming technique for multidimensional analysis of preference (LINMAP) developed by Sirinivasan and Shocker (Psychometrica 38:337–369, 1973) are used.     

A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems

In this paper we formulate necessary and sufficient conditions for an arbitrary polyhedral set to be a positively invariant set of a linear discrete-time system. Polyhedral cones and linear subspaces are included in the analysis. A linear programming algorithm is presented that enables practical application of the results stated in this paper.     

On bilevel multi-follower decision making: General framework and solutions

Within the framework of any bilevel decision problem, a leader’s decision is influenced by the reaction of his or her follower. When multiple followers who may have had a share in decision variables, objectives and constraints are involved in a bilevel decision problem, the leader’s decision will be affected, not only by the reactions of these followers, but also by the relationships among these followers. This paper firstly identifies nine different kinds of relationships (S₁ to S₉) amongst followers by establishing a general framework for bilevel multi-follower decision problems. For each of the nine a corresponding bilevel multi-follower decision model is then developed. Also, this paper particularly proposes related theories focusing on an uncooperative decision problem (i.e., S₁ model), as this model is the most basic one for bilevel multi-follower decision problems over the nine kinds of relationships. Moreover, this paper extends the Kuhn-Tucker approach for driving an optimal solution from the uncooperative decision model. Finally, a real case study of a road network problem illustrates the application of the uncooperative bilevel decision model and the proposed extended Kuhn-Tucker approach.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations.The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

On combined phase 1-phase 2 projective methods for linear programming

We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.This research was partially supported by NSF Grant DMS-8904406 and by ONR Contract N00004-87-K0212. The computations were carried out in the Cornell Computational Optimization Laboratory with support from NSF Grant DMS-8706133.     

Modelling a nationwide crop planning problem using a multiple criteria decision making tool

Multiple criteria decision making (MCDM) tools have been used in recent years to solve a wide variety of problems. In this paper we consider a nation-wide crop-planning problem and show how an MCDM tool can be used efficiently and effectively for these types of problems. A crop-planning problem is usually formulated as a single objective linear programming model. The objective is either the maximization of return from cultivated land or the minimization of cost of cultivation. This type of problem, however, normally involves more than one goal. We thus formulate a crop-planning problem as a goal program (an MCDM tool) and discuss the importance of three different goals for a case problem. We solve the goal program with a real world data set, and compare the solution with that of linear program. We argue that the goal program provides better insights to the problem and thus allows better decision support.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS-15361.     

Space bounds for a game on graphs

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph withn vertices and maximum in-degreed, there is a pebbling strategy which requires at mostc(d) n/logn pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/logn) bound.Research partially supported by DAAD (German Academic Exchange Service) Grant No. 430/402/563/5 (W.J.P.)Research partially supported by National Science Foundation grant MCS75-22870 and Office of Naval Research contract N0014-76-C-0688 (R.E.T. and J.R.C.).Reproduction in whole or in part is permitted for any purpose of the United States Government.     

Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

We prove an O(t(n) ^d (t(n)) ^? / log t(n)) time bound for the sim-ulation of t(n) steps of a Turing machine using several one-dimensional work tapes on a Turing machine using one d-dimensional work tape, . We prove a matching lower bound which holds for the problem of recognizing languages on machines with a separate one-way input tape. Received: March 1995.