Tabu search approaches for solving the two-group classification problem

The two-group classification problem consists in constructing a classifier that can distinguish between the two groups. In this paper, we consider the two-group classification problem which consists in determining a hyperplane that minimizes the number of misclassified points. We assume that the data set is numeric and with no missing data. We develop a tabu search (TS) heuristic for solving this NP-hard problem. The TS approach is based on a more convenient equivalent formulation of the classification problem. We also propose supplementary new intensification phases based on surrogate constraints. The results of the conducted computational experiments show that our TS algorithms produce solutions very close to the optimum and require significantly lower computational effort, so it is a valuable alternative to the MIP approaches. Moreover the tabu search procedures showed in this paper can be extended in a natural way to the general classification problem, which consists of generating more than one separating hyperplanes.     

Examining the effect of second-order terms in mathematical programming approaches to the classification problem

Research on mathematical programming approaches to the classification problem has focused almost exclusively on linear discriminant functions with only first-order terms. While many of these first-order models have displayed excellent classificatory performance when compared to Fisher's linear discriminant method, they cannot compete with Smith's quadratic discriminant method on certain data sets. In this paper, we investigate the appropriateness of including second-order terms in mathematical programming models. Various issues are addressed, such as performance of models with small to moderate sample size, need for crossproduct terms, and loss of power by the mathematical programming models under conditions ideal for the parametric procedures. A simulation study is conducted to assess the relative performance of first-order and second-order mathematical programming models to the parametric procedures. The simulation study indicates that mathematical programming models using polynomial functions may be prone to overfitting on the training samples which in turn may cause rather poor fits on the validation samples. The simulation study also indicates that inclusion of cross-product terms may hurt a polynomial model's accuracy on the validation samples, although omission of them means that the model is not invariant to nonsingular transformations of the data.     

Minimizing deviations from the group mean: A new linear programming approach for the two-group classification problem

This paper proposes a new linear programming approach to solve the two-group classification problem in discriminant analysis. This new approach is based on an idea from cluster analysis that objects within the same group should be more similar than objects between groups. Consequently, it is desirable for the classification score of an object to be nearer to its mean classification score, but further from the mean classification score of the other group. This objective is accomplished by minimizing the total deviation of the classification scores of the objects from their group mean scores in a linear programming approach. When applied to an actual managerial problem and simulated data, the proposed linear programming approach performs well both in groups separation and group-membership predictions of new objects. Moreover, this new approach has an advantage of obtaining more stable classification function across different samples than most of the existing linear programming approaches.     

A comparative study of approaches to dynamic location problems

We compare the performance of seven approximate methods for locating new capacity over time to minimize the total discounted costs of meeting growing demands at several locations. Comparisons are based on results for two industrial planning problems from India, and are given for both discrete-time and continuous-time frameworks. We also discuss strategies for combining different methods into possibly more effective hybrid approaches.     

A comparative study of modeling and solution approaches for the coordinated lot-size problem with dynamic demand

In the coordinated lot-size problem, a major setup cost is incurred when at least one member of a product family is produced and a minor setup cost for each different item produced. This research consolidates the various modeling and algorithmic approaches reported in the literature for the coordinated replenishment problem with deterministic dynamic demand. For the two most effective approaches, we conducted extensive computational experiments investigating the quality of the lower bound associated with the model’s linear programming relaxation and the computational efficiency of the algorithmic approaches when used to find heuristic and optimal solutions. Our findings indicate the superiority of the plant location type problem formulation over the traditional approach that views the problem as multiple single-item Wagner and Whitin problems that are coupled by major setup costs. Broader implications of the research suggest that other classes of deterministic dynamic demand lot-size problems may also be more effectively modeled and solved by adapting plant location type models and algorithms.     

A combinatorial approach to the classification problem

We study the two-group classification problem which involves classifying an observation into one of two groups based on its attributes. The classification rule is a hyperplane which misclassifies the fewest number of observations in the training sample. Exact and heuristic algorithms for solving the problem are presented. Computational results confirm the efficiency of this approach.     

A classical approach to the analyticity problem of center manifolds

One of the fundamental properties of center manifolds is that the study of a nonlinear differential equation near a stationary state can be reduced to the corresponding study of an equation on a center manifold. For center manifolds associated with a purely imaginary pair of eigenvalues the following is shown by classical means: although center manifolds may be nonanalytic the corresponding equations on center manifolds may be treated as if they were analytic.

---

Zusammenfassung Eine der grundlegenden Eigenschaften von Zentrumsmannigfaltigkeiten besagt, daß man eine nichtlineare Differentialgleichung in der Nähe einer Ruhelage an Hand der zugehörigen Gleichung auf einer Zentrumsmannigfaltigkeit untersuchen kann. Für Zentrumsmannigfaltigkeiten, die zu einem rein imaginären Paar von Eigenwerten gehören, wird mittels klassischer Methoden folgendes gezeigt: obwohl Zentrumsmannigfaltigkeiten im allgemeinen nichtanalytisch sind kann man die zugehörigen Gleichungen auf Zentrumsmannigfaltigkeiten behandeln als wären sie analytisch.

---

---

Supported by the Volkswagenwerk foundation.     

A variant of the classical Ramsey problem

For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK _p K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK _p subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK _n . We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erds and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414.     

A comparative study of some discrete descent approaches in stratified sampling

Summary For discrete stratification and allocation problems several procedures based on the concept of feasible directions are proposed. A comparison of the procedures using an example from literature shows that surprisingly the variant affording the lowest computational effort produces the best results. It should be stressed that stratification and allocation techniques are of great practical importance e.g. within the context of stocktaking.

---

Zusammenfassung Für diskrete Schichtungs- und Aufteilungsprobleme werden verschiedene Verfahren, basierend auf dem Konzept zulässiger Richtungen, vorgeschlagen. Ein Vergleich der Verfahren mit Hilfe eines Beispiels aus der Literatur zeigt, daß erstaunlicherweise diejenige Variante die besten Ergebnisse liefert, welche den geringsten Rechenaufwand benötigt. Es ist darauf hinzuweisen, daß Schichtungs- und Aufteilungs-Techniken von großer praktischer Bedeutung, z.B. im Rahmen der Inventur, sind.

     

A note on computational approaches for the antibandwidth problem

Central European Journal of Operations Research - In this note, we consider the antibandwidth problem, also known as dual bandwidth problem, separation problem and maximum differential coloring...     

A Bayesian approach to the triage problem with imperfect classification

A collection of jobs (or customers, or patients) wait impatiently for service. Each has a random lifetime during which it is available for service. Should this lifetime expire before its service starts then it leaves unserved. Limited resources mean that it is only possible to serve one job at a time. We wish to schedule the jobs for service to maximise the total number served. In support of this objective all jobs are subject to an initial triage, namely an assessment of both their urgency and of their service requirement. This assessment is subject to error. We take a Bayesian approach to the uncertainty generated by error prone triage and discuss the design of heuristic policies for scheduling jobs for service to maximise the Bayes’ return (mean number of jobs served). We identify problem features for which a high price is paid in number of services lost for poor initial triage and for which improvements in initial job assessment yield significant improvements in service outcomes. An analytical upper bound for the cost of imperfect classification is developed for exponentially distributed lifetime cases.     

The two-group heuristic to solve the multi-product,economic lot sizing and scheduling problem in flow shops

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

A computational study of hybrid approaches of metaheuristic algorithms for the cell formation problem

In this paper we solve the 0–1 cell formation problem where the number of cells is fixed a priori and where the objective is to maximize the overall efficiency of a production system by grouping together machines providing service to similar parts into a subsystem (denoted cell). Three different methods are introduced and compared numerically. The first local search method is an implementation of simulated annealing (SA) where the definition of the neighbourhood is specific to the application and requires using a diversification and intensification strategies. The second local search method is an adaptive simulated annealing method where the neighbourhood is selected randomly at each iteration. The procedure is adaptive in the sense that the probability of selecting a neighbourhood is updated during the process. The third method is a hybrid method (HM) of a population-based method and a local search method. To improve the solution obtained with HM, we apply a SA method afterward. The best variants are very efficient to solve the 35 benchmark problems commonly used in the literature.     

An algorithmic study of the Maximum Flow problem: A comparative statistical analysis

In this paper, we show the results of an experimental study about the most important algorithms proposed to solve the Maximum Flow problem. The appropriate statistical analysis not only allows us to justify comparisons between the different procedures but also to obtain classifications of their practical efficiency. Furthermore, an empirical experiment allows us to identify the influence of several parameters that are not included in a theoretical study.     

A computational study of solution approaches for the resource constrained elementary shortest path problem

We present the results of a computational investigation of solution approaches for the resource constrained elementary shortest path problem ( $\mathcal{RCESPP}$ ). In particular, the best known algorithms are tested on several problem instances taken from literature. The main aims are to provide a detailed state of the art and to evaluate methods that turn out to be the most promising for solving the problem under investigation. This work represents the first attempt to computationally compare solution approaches for the $\mathcal{RCESPP}$ .     

Lower-dimensional linear complementarity problem approaches to the solution of a bi-obstacle problem

A globally convergent Broyden-like method for solving a bi-obstacle problem is proposed based on its equivalent lower-dimensional linear complementarity problem. A suitable line search technique is introduced here. The global and superlinear convergence of the method is verified under appropriate assumptions.     

A survey on the global optimization problem: General theory and computational approaches

Several different approaches have been suggested for the numerical solution of the global optimization problem: space covering methods, trajectory methods, random sampling, random search and methods based on a stochastic model of the objective function are considered in this paper and their relative computational effectiveness is discussed. A closer analysis is performed of random sampling methods along with cluster analysis of sampled data and of Bayesian nonparametric stopping rules.