Heuristics for feature selection in mathematical programming discriminant analysis models

In developing a classification model for assigning observations of unknown class to one of a number of specified classes using the values of a set of features associated with each observation, it is often desirable to base the classifier on a limited number of features. Mathematical programming discriminant analysis methods for developing classification models can be extended for feature selection. Classification accuracy can be used as the feature selection criterion by using a mixed integer programming (MIP) model in which a binary variable is associated with each training sample observation, but the binary variable requirements limit the size of problems to which this approach can be applied. Heuristic feature selection methods for problems with large numbers of observations are developed in this paper. These heuristic procedures, which are based on the MIP model for maximizing classification accuracy, are then applied to three credit scoring data sets.     

Integer programming methods for normalisation and variable selection in mathematical programming discriminant analysis models

Mathematical programming discriminant analysis models must be normalised to prevent the generation of discriminant functions in which the variable coefficients and the constant term are zero. This normalisation requirement can cause difficulties, and unlike statistical discriminant analysis, variables cannot be selected in a computationally efficient way with mathematical programming discriminant analysis models. Two new integer programming normalisations are proposed in this paper. In the first, binary variables are used to represent the constant term, but with this normalisation functions with a zero constant term cannot be generated and the variable coefficients are not invariant under origin shifts. These limitations are overcome by using integer programming methods to constrain the sum of the absolute values of the variable coefficients to a constant. These new normalisations are extended to allow variable selection with mathematical programming discriminant analysis models. The use of these new applications of integer programming is illustrated using published data.     

Simple but powerful goal programming models for discriminant problems

Conventional statistical analysis includes the capacity to systematically assign individuals to groups. We suggest alternative assignment procedures, utilizing a set of interrelated goal programming formulations. We further demonstrate via simple illustration the potential of these procedures to play a significant part in addressing the discriminant problem, and indicate fundamental ideas that lay the foundation for other more sophisticated approaches.     

Mathematical programming models for some smallest-world problems

Given a weighted graph G, in the minimum-cost-edge-selection problem (MCES), a minimum weighted set of edges is chosen subject to an upper bound on the diameter of graph G. Similarly, in the minimum-diameter-edge-selection problem (MDES), a set of edges is chosen to minimize the diameter subject to an upper bound on their total weight. These problems are shown to be equivalent and proven to be NP-complete. MCES is then formulated as a 0–1 integer programming problem. The problems MCES and MDES provide models for determining smallest-world networks and for measuring the “small-worldness” of graphs.     

A simplex algorithm for piecewise-linear programming III: Computational analysis and applications

The first two parts of this paper have developed a simplex algorithm for minimizing convex separable piecewise-linear functions subject to linear constraints. This concluding part argues that a direct piecewiselinear simplex implementation has inherent advantages over an indirect approach that relies on transformation to a linear program. The advantages are shown to be implicit in relationships between the linear and piecewise-linear algorithms, and to be independent of many details of implementation. Two sets of computational results serve to illustarate these arguments; the piecewise-linear simplex algorithm is observed to run 2–6 times faster than a comparable linear algorithm, not including any additional expense that might be incurred in setting up the equivalent linear program. Further support for the practical value of a good piecewise-linear programming algorithm is provided by a survey of many varied applications.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

A ratio model for discriminant analysis using linear programming

The innovative hybrid model for discriminant analysis via linear programming, was introduced along with the β normalization, which was subsequently replaced by a new normalization. The primary weakness of the β normalization, and the reason for replacing it with the new normalization, is that it distorts solutions and consequently does not always find the best solution. It is shown here, that unfortunately, both normalizations are affected by distance distortion. In addition, whether a model finds the best solution is highly dependent on the criterion or criteria by which “best solution” is defined. A ratio criteria and associated ratio model are proposed, which avoid the problems associated with distance distortion. The nonlinear ratio may be linearized in much the same way that Data Envelopment Analysis is linearized.     

Mathematical programming models for revenue management under customer choice

We study a network airline revenue management problem with discrete customer choice behavior. We discuss a choice model based on the concept of preference orders, in which customers can be grouped according to a list of options in decreasing order of preference. If a customer’s preferred option is not available, the customer moves to the next choice on the list with some probability. If that option is not available, the customer moves to the third choice on the list with some probability, and so forth until either the customer has no other choice but to leave or his/her request is accepted. Using this choice model as an input, we propose some mathematical programs to determine seat allocations. We also propose a post-optimization heuristic to refine the allocation suggested by the optimization model. Simulation results are presented to illustrate the effectiveness of our method, including comparisons with other models.     

A simplex algorithm for piecewise-linear fractional programming problems

Generalizations of the well-known simplex method for linear programming are available to solve the piecewise linear programming problem and the linear fractional programming problem. In this paper we consider a further generalization of the simplex method to solve piecewise linear fractional programming problems unifying the simplex method for linear programs, piecewise linear programs, and the linear fractional programs. Computational results are presented to obtain further insights into the behavior of the algorithm on random test problems.     

Mathematical programming models to determine civil service salaries

Increased criticism has been directed in recent years at the present fixed step salary method used for compensating civil servants. Under this method the relative monetary value of an individual to the department of agency is based only on two factors: civil service grade and the number of years of experience in the particular grade. This paper describes how two mathematical programming methods, linear programming and goal programming, can be applied to determine a civil service salary structure for the New York State Department of Transportation (Region 10). The mathematical salary model employed was developed by J.E. Bruno.     

An additive utility mixed integer programming model for nonlinear discriminant analysis

Mathematical programming (MP) discriminant analysis models can be used to develop classification models for assigning observations of unknown class membership to one of a number of specified classes using values of a set of features associated with each observation. Since most MP discriminant analysis models generate linear discriminant functions, these MP models are generally used to develop linear classification models. Nonlinear classifiers may, however, have better classification performance than linear classifiers. In this paper, a mixed integer programming model is developed to generate nonlinear discriminant functions composed of monotone piecewise-linear marginal utility functions for each feature and the cut-off value for class membership. It is also shown that this model can be extended for feature selection. The performance of this new MP model for two-group discriminant analysis is compared with statistical discriminant analysis and other MP discriminant analysis models using a real problem and a number of simulated problem sets.     

Mathematical programming models and algorithms for a class–faculty assignment problem

This paper presents mathematical programming models for assigning faculty members to classes including, among typical academic class scheduling issues, certain specialized central policies at Kuwait University. The time-slots for classes are initially assumed to be given and an integer programming model (CFAM) is constructed to solve the resulting problem, which aims to minimize the individual and collective dissatisfaction of faculty members in a fair fashion, where dissatisfaction is measured by a function of the assignment of faculty members to time-slots and specific classes. In order to enhance the quality of results obtained in practice, the model is modified (ECFAM) so that the time-slots for the classes can be changed, however, with restrictions related to efficient facility utilization and permitting an administratively regulated maximum number of changes. Gender-based modeling considerations are also introduced in order to maintain desirable class offering patterns. Computational results are presented based on solving the models directly by the CPLEX-MIP (version 7.5) package and also using a specialized LP-based heuristic. The faculty schedules generated via the proposed approach based on a number of case studies related to the Department of Mathematics and Computer Science at Kuwait University reveal that this approach yields improved schedules in terms of fairness and enhanced satisfaction levels among faculty members.     

A simplex algorithm for piecewise-linear programming I: Derivation and proof

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. This three-part paper develops and analyzes a general, computationally practical simplex algorithm for piecewiselinear programming.Part I derives and justifies the essential steps of the algorithm, by extension from the simplex method for linear programming in bounded variables. The proof employs familiar finite-termination arguments and established piecewise-linear duality theory.Part II considers the relaxation of technical assumptions pertaining to finiteness, feasibility and nondegeneracy of piecewise-linear programs. Degeneracy is found to have broader consequences than in the linear case, and the standard techniques for prevention of cycling are extended accordingly.Part III analyzes the computational requirements of piecewise-linear programming. The direct approach embodied in the piecewise-linear simplex algorithm is shown to be inherently more efficient than indirect approaches that rely on transformation of piecewise-linear programs to equivalent linear programs. A concluding section surveys the many applications of piecewise-linear programming in linear programming,l ₁ estimation, goal programming, interval programming, and nonlinear optimization.This research has been supported in part by the National Science Foundation under grant MCS-8217261.     

Learning the optimal kernel for Fisher discriminant analysis via second order cone programming

Kernel Fisher discriminant analysis (KFDA) is a popular classification technique which requires the user to predefine an appropriate kernel. Since the performance of KFDA depends on the choice of the kernel, the problem of kernel selection becomes very important. In this paper we treat the kernel selection problem as an optimization problem over the convex set of finitely many basic kernels, and formulate it as a second order cone programming (SOCP) problem. This formulation seems to be promising because the resulting SOCP can be efficiently solved by employing interior point methods. The efficacy of the optimal kernel, selected from a given convex set of basic kernels, is demonstrated on UCI machine learning benchmark datasets.     

Classification accuracy in discriminant analysis: a mixed integer programming approach

Classification models can be developed by statistical or mathematical programming discriminant analysis techniques. Variable selection extensions of these techniques allow the development of classification models with a limited number of variables. Although stepwise statistical variable selection methods are widely used, the performance of the resultant classification models may not be optimal because of the stepwise selection protocol and the nature of the group separation criterion. A mixed integer programming approach for selecting variables for maximum classification accuracy is developed in this paper and the performance of this approach, measured by the leave-one-out hit rate, is compared with the published results from a statistical approach in which all possible variable subsets were considered. Although this mixed integer programming approach can only be applied to problems with a relatively small number of observations, it may be of great value where classification decisions must be based on a limited number of observations.     

A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis

We will propose a new cutting plane algorithm for solving a class of semi-definite programming problems (SDP) with a small number of variables and a large number of constraints. Problems of this type appear when we try to classify a large number of multi-dimensional data into two groups by a hyper-ellipsoidal surface. Among such examples are cancer diagnosis, failure discrimination of enterprises. Also, a certain class of option pricing problems can be formulated as this type of problem. We will show that the cutting plane algorithm is much more efficient than the standard interior point algorithms for solving SDP.     

Mathematical analysis of coral reef models

It is acknowledged that coral reefs are globally threatened. P.J. Mumby et al. [10] constructed a mathematical model with ordinary differential equations to investigate the dynamics of coral reefs. In this paper, we first provide a detailed global analysis of the coral reef ODE model in [10]. Next we incorporate the inherent time delay to obtain a mathematical model with delay differential equations. We consider the grazing intensity and the time delay as focused parameters and perform local stability analysis for the coral reef DDE model. If the time delay is sufficiently small, the stability results remain the same. However, if the time delay is large enough, macroalgae only state and coral only state are both unstable, while they are both stable in the ODE model. Meanwhile, if the grazing intensity and the time delay are endowed some suitable values, the DDE model possesses a nontrivial periodic solution, whereas the ODE model has no nontrivial periodic solutions for any grazing rate. We study the existence and property of the Hopf bifurcation points and the corresponding stability switching directions.     

A computational analysis of multidimensional piecewise-linear models with applications to oil production optimization

Production optimization of gas-lifted oil wells under facility, routing and pressure constraints is a challenging problem, which has attracted the interest of operations engineers aiming to drive economic gains and scientists for its inherent complexity. The hardness of this problem rests on the non-linear characteristics of the multidimensional well-production and pressure-drop functions, as well as the discrete routing decisions. To this end, this work develops several formulations in Mixed-Integer Linear Programming (MILP) using multidimensional piecewise-linear models to approximate the non-linear functions with domains spliced in hypercubes and simplexes. Computational and simulation analyses were performed considering a synthetic but realistic oil field modeled with a multiphase-flow simulator. The purpose of the analyses was to assess the relative performance of the MILP formulations and their impact on the simulated oil production.     

A simplex algorithm for piecewise-linear programming II: Finiteness,feasibility and degeneracy

The simplex method for linear programming can be extended to permit the minimization of any convex separable piecewise-linear objective, subject to linear constraints. Part I of this paper has developed a general and direct simplex algorithm for piecewise-linear programming, under convenient assumptions that guarantee a finite number of basic solutions, existence of basic feasible solutions, and nondegeneracy of all such solutions. Part II now shows how these assumptions can be weakened so that they pose no obstacle to effective use of the piecewise-linear simplex algorithm. The theory of piecewise-linear programming is thereby extended, and numerous features of linear programming are generalized or are seen in a new light. An analysis of the algorithm's computational requirements and a survey of applications will be presented in Part III.This research has been supported in part by the National Science Foundation under grant DMS-8217261.     

MATHEMATICAL ANALYSIS OF SOME NEURAL NETWORKS FOR SOLVING LINEAR AND QUADRATIC PROGRAMMING

ＺＨＡＮＧＸＩＡＮＧＳＵＮ（章祥荪）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃｈｉｎａ）ＲｅｃｅｉｖｅｄＪｕｎｅ１８，１９９４．Ｔｈｉｓｗｏｒｋｉ...     

Mathematical programming for network revenue management revisited

Mathematical programming models for airline seat inventory control provide booking limits and bid-prices for all itineraries and fare classes. E.L. Williamson [Airline network seat inventory control: methodologies and revenue impacts, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 1992] finds that simple deterministic approximation methods based on average demand often outperform more advanced probabilistic heuristics. We argue that this phenomenon is due to a booking process that includes nesting of the fare classes, which is ignored in the modeling phase. The differences in the performance between these approximations are studied using a stochastic programming model that includes the deterministic model as a special case. Our study carefully examines the trade-off between computation time and the aggregation level of demand uncertainty with examples of a multi-leg flight and a single-hub network.