Local search (optimization) | EPFL Graph Search

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed. Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics. Examples of local search algorithms are WalkSAT, the 2-opt algorithm for the Traveling Salesman Problem and the Metropolis–Hastings algorithm. While it is sometimes possible to substitute gradient descent for a local search algorithm, gradient descent is not in the same family: although it is an iterative method for local optimization, it relies on an objective function’s gradient rather than an explicit exploration of the solution space. Some problems where local search has been applied are: The vertex cover problem, in which a solution is a vertex cover of a graph, and the target is to find a solution with a minimal number of nodes The traveling salesman problem, in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle The boolean satisfiability problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment; in this case, the final solution is of use only if it satisfies all clauses The nurse scheduling problem where a solution is an assignment of nurses to shifts which satisfies all established constraints The k-medoid clustering problem and other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective The Hopfield Neural Networks problem for which finding stable configurations in Hopfield network.

Optimal Control Combining Emulation and Imitation to Acquire Physical Assistance Skills

Sylvain Calinon, Amirreza Razmjoo Fard, Teguh Santoso Lembono

paper studies exploiting action-level learning (imitation) in the optimal control problem context. Cost functions defined by the optimal control methods are similar to the goal-level learning (emulation) in animals. However, imitating the robot's or others' (e.g. human's) previous experiences (demonstrations) could help the system to improve its performances. We propose to use demonstrations more efficiently by predicting an initialization for the optimal control problems (OCPs) and adding an imitation term to the cost functions. While the predicted initial guess initializes the OCPs close to their local optima, the imitation term guides the optimization, resulting in a faster convergence rate. We test our algorithm in a physical assistive task where a robot should help a human perform a sit-to-stand (STS) task. We define this task as two optimal control problems. The first OCP predicts the human's desired assistance and the other one controls the robot. We have tested our method on different experiments with different conditions for the human in which the robot should quickly solve the two optimization problems exploiting some demonstrations of how it can perform the task. Our proposed method reduced the number of iterations by more than 90% and 70% for the human assistance prediction and the robot controller, respectively, compared to the standard problem which does not take the demonstrations into account.

IEEE2021

A note on the integrality gap of the configuration LP for restricted Santa Claus

Klaus Jansen, Lars Rohwedder

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to players that desire them. The quality of a solution is measured by the least happy player, i.e., the lowest sum of resource values. This value should be maximized. The local search algorithm by Asadpour et al. [1] and its connection to the configuration LP has proved itself to be a very influential technique for this and related problems. Asadpour et al. used a local search to obtain a bound of 4 for the ratio of the fractional to the integral optimum of the configuration LP (the integrality gap). This bound is non-constructive, since the local search has not been shown to terminate in polynomial time. On the negative side, the worst instance known has an integrality gap of 2. Although much progress was made in this area, neither bound has been improved since. We present a better analysis that shows the integrality gap is not worse than 3 + 5/6 approximate to 3.8333. (C) 2020 Elsevier B.V. All rights reserved.

ELSEVIER2020

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Jian Li, Lingxiao Huang

We study the problem of constructing epsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An epsilon-coreset is a weighted subset S subset of X with weight function w : S -> R->= 0, such that for any k-subset C is an element of X, it holds that Sigma(x is an element of S) w(x).d(z) (x, C) is an element of (1 +/- epsilon) . Sigma(x is an element of X) d(z) (x, C). We present an efficient algorithm that constructs an epsilon-coreset for the (k, z)-clustering problem in M(X, d), where the size of the coreset only depends on the parameters k, z, epsilon and the doubling dimension ddim(M). To the best of our knowledge, this is the first efficient epsilon-coreset construction of size independent of vertical bar X vertical bar for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of M(X, d) and the shattering dimension (or VC-dimension) of the range space induced by the distance d. Such a relation is not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small (1 +/- epsilon)-distortion of the distance function d (the distorted distance is called the smoothed distance function), the shattering dimension can be upper bounded by O(epsilon(-O(ddim(M)))). For the purpose of coreset construction, the above bound does not suffice as it only works for unweighted spaces. Therefore, we introduce the notion of tau-error probabilistic shattering dimension, and prove a (drastically better) upper bound of O(ddim(M).log(1/epsilon)+log log 1/tau) for the probabilistic shattering dimension for weighted doubling metrics. As it turns out, an upper bound for the probabilistic shattering dimension is enough for constructing a small coreset. We believe the new relation between doubling and shattering dimensions is of independent interest and may find other applications. Furthermore, we study robust coresets for (k, z)-clustering with outliers in a doubling metric. We show an improved connection between alpha-approximation and robust coresets. This also leads to improvement upon the previous best known bound of the size of robust coreset for Euclidean space [Feldman and Langberg, STOC 11]. The new bound entails a few new results in clustering and property testing. As another application, we show constant-sized (epsilon, k, z)-centroid sets in doubling metrics can be constructed by extending our coreset construction. Prior to our result, constant-sized centroid sets for general clustering problems were only known for Euclidean spaces. We can apply our centroid set to accelerate the local search algorithm (studied in [Friggstad et al., FOCS 2016]) for the (k, z)-clustering problem in doubling metrics.

IEEE COMPUTER SOC2018

epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

Jian Li, Lingxiao Huang

IEEE COMPUTER SOC2018