A tabu search with an oscillation strategy for the discriminant analysis problem

This article proposes a tabu search approach to solve a mathematical programming formulation of the linear classification problem, which consists of determining an hyperplane that separates two groups of points as well as possible in ?^m. The tabu search approach proposed is based on a non-standard formulation using linear system infeasibility. The search space is the set of bases defined on the matrix that describes the linear system. The moves are performed by pivoting on a specified row and column. On real machine learning databases, our approach compares favorably with implementations based on parametric programming and irreducible infeasible constraint sets. Additional computational results for randomly generated instances confirm that our method provides a suitable alternative to the mixed integer programming formulation that is solved by a commercial code when the number of attributes m increases.     

Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

Connecting the 3D DGS Calques3D with the CAS Maple

Many (2D) Dynamic Geometry Systems (DGSs) are able to export numeric coordinates and equations with numeric coefficients to Computer Algebra Systems (CASs). Moreover, different approaches and systems that link (2D) DGSs with CASs, so that symbolic coordinates and equations with symbolic coefficients can be exported from the DGS to the CAS, already exist. Although the 3D DGS Calques3D can export numeric coordinates and equations with numeric coefficients to Maple and Mathematica, it cannot export symbolic coordinates and equations with symbolic coefficients. A connection between the 3D DGS Calques3D and the CAS Maple, that can handle symbolic coordinates and equations with symbolic coefficients, is presented here. Its main interest is to provide a convenient time-saving way to explore problems and directly obtain both algebraic and numeric data when dealing with a 3D extension of “ruler and compass geometry”. This link has not only educational purposes but mathematical ones, like mechanical theorem proving in geometry, geometric discovery (hypotheses completion), geometric loci finding… As far as we know, there is no comparable “symbolic” link in the 3D case, except the prototype 3D-LD (restricted to determining algebraic surfaces as geometric loci).     

Monte Carlo techniques for phrase-based translation

Recent advances in statistical machine translation have used approximate beam search for NP-complete inference within probabilistic translation models. We present an alternative approach of sampling from the posterior distribution defined by a translation model. We define a novel Gibbs sampler for sampling translations given a source sentence and show that it effectively explores this posterior distribution. In doing so we overcome the limitations of heuristic beam search and obtain theoretically sound solutions to inference problems such as finding the maximum probability translation and minimum risk training and decoding.     

Online collaboration: Collaborative behavior patterns and factors affecting globally distributed team performance

Studying the collaborative behavior of online learning teams and how this behavior is related to communication mode and task type is a complex process. Research about small group learning suggests that a higher percentage of social interactions occur in synchronous rather than asynchronous mode, and that students spend more time in task-oriented interaction in asynchronous discussions than in synchronous mode. This study analyzed the collaborative interaction patterns of global software development learning teams composed of students from Turkey, US, and Panama. Data collected from students’ chat histories and forum discussions from three global software development projects were collected and compared. Both qualitative and quantitative analysis methods were used to determine the differences between a group’s communication patterns in asynchronous versus synchronous communication mode. K-means clustering with the Ward method was used to investigate the patterns of behaviors in distributed teams. The results show that communication patterns are related to communication mode, the nature of the task, and the experience level of the leader. The paper also includes recommendations for building effective online collaborative teams and describes future research possibilities.     

Project scheduling under resource constraints: Application of the cumulative global constraint in a decision support framework

This paper concerns project scheduling under resource constraints. Traditionally, the objective is to find a unique solution that minimizes the project makespan, while respecting the precedence constraints and the resource constraints. This work focuses on developing a model and a decision support framework for industrial application of the cumulative global constraint. For a given project scheduling, the proposed approach allows the generation of different optimal solutions relative to the alternate availability of outsourcing and resources. The objective is to provide a decision-maker an assistance to construct, choose, and define the appropriate scheduling program taking into account the possible capacity resources. The industrial problem under consideration is modeled as a constraint satisfaction problem (CSP). It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the tasks realized on each resource, as well as the curves with the profile of the total consumption of resources on time.     

A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB.     

Rain or Snow Detection in Image Sequences Through Use of a Histogram of Orientation of Streaks

The detection of bad weather conditions is crucial for meteorological centers, specially with demand for air, sea and ground traffic management. In this article, a system based on computer vision is presented which detects the presence of rain or snow. To separate the foreground from the background in image sequences, a classical Gaussian Mixture Model is used. The foreground model serves to detect rain and snow, since these are dynamic weather phenomena. Selection rules based on photometry and size are proposed in order to select the potential rain streaks. Then a Histogram of Orientations of rain or snow Streaks (HOS), estimated with the method of geometric moments, is computed, which is assumed to follow a model of Gaussian-uniform mixture. The Gaussian distribution represents the orientation of the rain or the snow whereas the uniform distribution represents the orientation of the noise. An algorithm of expectation maximization is used to separate these two distributions. Following a goodness-of-fit test, the Gaussian distribution is temporally smoothed and its amplitude allows deciding the presence of rain or snow. When the presence of rain or of snow is detected, the HOS makes it possible to detect the pixels of rain or of snow in the foreground images, and to estimate the intensity of the precipitation of rain or of snow. The applications of the method are numerous and include the detection of critical weather conditions, the observation of weather, the reliability improvement of video-surveillance systems and rain rendering.