Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

Daniel Kuhn, Napat Rujeerapaiboon, Kilian Schindler, Wolfram Wiesemann
2019
Article

Résumé

Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to high quality solutions for the MILP. We prove that these solutions are optimal in the MILP if a cluster separation condition holds. To our best knowledge, we propose the first tractable solution scheme for the joint outlier-detection and clustering problem with optimality guarantees.

Official source

https://infoscience.epfl.ch/record/228322?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Kilian Schindler

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are intractable, and numerical solutions necessitate approximations. The mainstream approach for making a stochastic optimization model amenable to numerical solution is to discretize the probability distribution of the uncertain problem parameters. However, both the accuracy of the approximation as well as the computational burden of solving the approximate problem scale with the number of scenarios of the approximate distribution. An effective means to ease the computational burden is to use scenario reduction, which replaces an accurate initial distribution accommodating many scenarios with a simpler distribution supported on only few scenarios that is close to the initial distribution with respect to a probability metric. Using the Wasserstein distance as measure of proximity between distributions, we provide new insights into the fundamental limitations of scenario reduction, and we propose the first polynomial-time constant-factor approximations for a popular scenario reduction problem from the literature. As scenario reduction is equivalent to clustering, it suffers from two well-known shortcomings. Namely, it suffers from outlier sensitivity and may produce highly unbalanced clusters. To mitigate both shortcomings, we formulate a joint outlier detection and clustering problem, where the clusters must satisfy certain cardinality constraints. We cast this problem as a mixed-integer linear program (MILP) that admits tractable semidefinite and linear programming relaxations. We propose deterministic rounding schemes that transform the relaxed solutions to feasible solutions for the MILP. We also prove that these solutions are optimal in the MILP if a cluster separation condition holds. Finally, we develop a highly efficient scenario reduction method for a large-scale hydro scheduling problem. Specifically, we study the optimal operation of a fleet of interconnected hydropower plants that sell energy on both the spot and the reserve markets, and we propose a two-layer stochastic programming framework for its solution. The outer layer problem (the planner's problem) optimizes the end-of-day reservoir filling levels over one year, whereas the inner layer problem (the trader's problem) selects optimal hourly market bids within each day. We prove that the trader's problem admits a scenario reduction that dramatically reduces its complexity without loss of optimality, which in turn facilitates an efficient approximation of the planner's problem.

EPFL2020

Chargement

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Programming (LP) relaxations. An optimal solution to such a relaxation provides a bound on the objective value of the optimal integral solution, to which we compare the integral solution we return. In this context, when studying a specific problem, two natural questions often arise: What is a strong LP relaxation for this problem, and how can we exploit it? Over the course of the past few decades, a significant amount of effort has been expended by the research community in order to answer these questions for a variety of interesting intractable problems. Although there exist multiple problems for which we have designed LP relaxations that achieve best-possible guarantees, there still exist numerous problems for which we either have no strong LP relaxations, or do not know how to use them. The main focus of this thesis is extending our understanding of such strong relaxations. We focus on designing good approximation algorithms for certain allocation problems, by employing a class of strong LP relaxations, called configuration-LPs. For many such allocation problems, the best-known results are derived by using simple and natural LP relaxations, whereas configuration-LPs have been used successfully on several occasions in order to break pre-existing barriers set by weaker relaxations. However, our understanding of configuration-LPs is far from complete for many problems. Therefore, understanding and using these relaxations to the farthest extent possible is a quite intriguing question. Answering this question could result in improved approximation algorithms for a wide variety of allocation problems. The first problem we address in this thesis is the restricted max-min fair allocation problem. Prior to our work, the best known result provided an

\Omega(1)

-approximation that ran in polynomial time. Also, it was known how to estimate the value of an optimal solution to the problem within a factor of

1/(4+c)

, for any

c>0

, by solving the corresponding configuration-LP. Our first contribution in this thesis is the design of a

1/13

-approximation algorithm for the problem, using the configuration-LP. Specifically, although our algorithm is fully combinatorial, it consists of a local-search procedure that is guaranteed to succeed only when the configuration-LP is feasible. In order to establish the correctness and running time of the algorithm, it is crucial to use the configuration-LP in our analysis. The second problem we study is the scheduling of jobs on unrelated machines in order to minimize the sum of weighted completion times. For this problem, the best known approximation algorithm achieves a ratio of

3/2-r

, for some small

r>0

. Our second contribution in this thesis is the improvement of this ratio to

(1+\sqrt{2})/2+c

, for any

c>0

, for the special case of the problem where the jobs have uniform Smith ratios. To achieve this ratio, we design a randomized rounding algorithm that rounds solutions to the corresponding configuration-LP. Through a careful examination of the distribution this randomized algorithm outputs, we identify the one that maximizes the approximation ratio, and we then upper bound the ratio this worst-case distribution exhibits by

(1+\sqrt{2})/2+c

EPFL2017

Chargement

Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

David Schindl

The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set problem, and provide some new graph classes, where it can be solved in polynomial time. Those classes are hereditary, i.e. characterized by a list of forbidden induced subgraphs. The algorithms proposed are purely combinatorial. The second chapter is devoted to the study of a problem linked to security purposes in mobile telecommunication networks. The particularity is that there is no central authority guaranteeing security, but it is actually managed by the users themselves. The network is modelled by an oriented graph, whose vertices represent the users, and whose arcs represent public key certificates. The problem is to associate to each vertex a subgraph with some requirements on the size of the subgraphs, the number of times a vertex is taken in a subgraph and the connectivity between any two users as they put their subgraphs together. Constructive heuristics are proposed, bounds on the optimal solution and a tabu search are described and tested. The third chapter is on the problem of reconstructing an image, given its projections in terms of the number of occurrences of each color in each row and each column. The case of two colors is known to be polynomially solvable, it is NP-complete with four or more colors, and the complexity status of the problem with three colors is open. An intermediate case between two and three colors is shown to be solvable in polynomial time. The last two chapters are about graph (vertex-)coloring. In the fourth, we prove a result which brings a large collection of NP-hard subcases, characterized by forbidden induced subgraphs. In the fifth chapter, we approach the problem with the use of linear programming. Links between different formulations are pointed out, and some families of facets are characterized. In the last section, we study a branch and bound algorithm, whose lower bounds are given by the optimal value of the linear relaxation of one of the exposed formulations. A preprocessing procedure is proposed and tested.

EPFL2004

Chargement