Novel Algorithms Automatically Generated for Optimization Problems A difficult task in computer science is designing algorithms. This task is particularly complex when efficient algorithms must be constructed for computationally difficult optimization problems. Two fundamental problems in both combinatorial optimization and machine learning are the maximum independent set problem and the automatic data clustering. The best specific algorithms for both problems are heuristic and have been constructed by combining primary heuristics. However, the possible combinations explored so far are a minimum number of the entire combinatorial space. The automatic exploration of such space would, therefore, allow finding more efficient algorithmic combinations. This article reports new algorithms for both problems constructed by the automatic generation of algorithms, an emerging field that allows to automatically produce an adequate algorithm for a specific set of instances of the problem. The best algorithms generated after the computational experimentation are reported and compared with existing heuristics, demonstrating that the new algorithms are competitive.

A Binary Linear ProgrammingBased KMeans Approach for the Capacitated Centered Clustering Problem The kmeans algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a variant of the kmeans algorithm that can account for complex side constraints. The key idea is to use binary linear programming for assigning objects to clusters. Unlike existing extensions of the kmeans algorithm that are designed for accommodating specific types of constraints, our approach can be applied to a wide range of constrained clustering problems with minor modifications. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it to a stateoftheart algorithm on a test set that comprises 18 instances of the capacitated centered clustering problem. The proposed approach performed particularly well on largesized instances with more than 100 clusters. It even found new bestknown solutions for the four largest instances in the test set.