Computational Comparison of Metaheuristics
Handbook of MetaheuristicsJohn Silberholz, Bruce Golden, Swati Gupta, Xingyin Wang
2018
Metaheuristics are truly diverse in nature—under the overarching theme of performing operations to escape local optima, algorithms as different as ant colony optimization, tabu search, harmony search, and genetic algorithms have emerged. Due to the unique functionality of each type of metaheuristic, the computational comparison of metaheuristics is in many ways more difficult than other algorithmic comparisons. In this chapter, we discuss techniques for the meaningful computational comparison of metaheuristics. We discuss how to create and classify instances in a new testbed and how to make sure other researchers have access to these test instances for future metaheuristic comparisons. In addition, we discuss the disadvantages of large parameter sets and how to measure complicated parameter interactions in a metaheuristic’s parameter space. Finally, we explain how to compare metaheuristics in terms of both solution quality and runtime and how to compare parallel metaheuristics.
View more
Solving combinatorial games using products, projections and lexicographically optimal bases
arXiv PreprintSwati Gupta, Michel Goemans, Patrick Jaillet
2016
In order to find Nash-equilibria for two-player zero-sum games where each player plays combinatorial objects like spanning trees, matchings etc, we consider two online learning algorithms: the online mirror descent (OMD) algorithm and the multiplicative weights update (MWU) algorithm. The OMD algorithm requires the computation of a certain Bregman projection, that has closed form solutions for simple convex sets like the Euclidean ball or the simplex. However, for general polyhedra one often needs to exploit the general machinery of convex optimization. We give a novel primal-style algorithm for computing Bregman projections on the base polytopes of polymatroids. Next, in the case of the MWU algorithm, although it scales logarithmically in the number of pure strategies or experts in terms of regret, the algorithm takes time polynomial in ; this especially becomes a problem when learning combinatorial objects. We give a general recipe to simulate the multiplicative weights update algorithm in time polynomial in their natural dimension. This is useful whenever there exists a polynomial time generalized counting oracle (even if approximate) over these objects. Finally, using the combinatorial structure of symmetric Nash-equilibria (SNE) when both players play bases of matroids, we show that these can be found with a single projection or convex minimization (without using online learning).
View more
What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
Informs Journal on ComputingIain Dunning, Swati Gupta, John Silberholz
2015
Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary optimization (QUBO) heuristics papers, we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners.
View more
A 4/3-approximation for TSP on cubic 3-edge-connected graphs
arXiv PreprintNishita Aggarwal, Naveen Garg, Swati Gupta
2011
We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.
View more
SPAN: a unified framework and toolkit for querying heterogeneous access policies
Proceedings of the 4th USENIX conference on Hot topics in securitys Swati Gupta, Kristen LeFevre, Atul Prakash
2009
Incorrect policy configurations are a major cause of security failures in large-scale systems. Policy analyzers and testing tools can help with this, but often the tools are specific to one type of policy (eg, firewalls). In contrast, the most insidious security problems often require understanding the interactions of policies across systems (eg, firewalls, SSH, file systems, etc.). Currently, much of this analysis must be done manually. In this paper, we propose a common framework called SPAN (Security Policy Analyzer) to help analyze policies from heterogeneous systems. On the front-end, SPAN presents administrators with a simple, unified, abstraction and flexible query language. Internally, policies and queries are implemented compactly and efficiently using decision diagrams.
View more
