Query: Heuristic allocation of computational resources

Candidate papers:

abstract: This study considers an actual real world problem encountered by ARM, the world's leading semiconductor intellectual property (IP) supplier, concerning the multi year assignment of weeks long computationally intensive projects (executable pieces of code) across a number of capacity limited clusters. The quality of a projects to cluster assignment is measured in terms of several metrics such as the even utilization of clusters, being able to realize all projects, and spreading projects of different research groups evenly across the clusters. The first (theoretical) contribution of this work is to motivate and formally define this novel application and put it in context with related literature. The second (experimental) contribution of this work is about gaining an understanding about the problem and performing an initial investigation on how different algorithm types (random search, an EMOA, and greedy search) fare on the problem. Our study revealed that the problem has many infeasible solutions and is challenging to optimize especially for long planning horizons (more than 3 years) While the EMOA is able to outperform random and greedy search (and also the current approach used at ARM) in terms of solution quality discovered, greedy search was the computationally most efficient approach and suitable for short term planning horizons (up to 1 year)
author_names: Silviu Tofan

Richard W Allmendinger

Manuela Zanda

Olly Stephens
title: Heuristic allocation of computational resources
venue: GECCO
year: 2017

abstract: In this paper we survey computational models for Grid scheduling problems and their resolution using heuristic and meta heuristic approaches. Scheduling problems are at the heart of any Grid like computational system. Different types of scheduling based on different criteria, such as static versus dynamic environment, multi objectivity, adaptivity, etc. are identified. Then, heuristic and meta heuristic methods for scheduling in Grids are presented. The paper reveals the complexity of the scheduling problem in Computational Grids when compared to scheduling in classical parallel and distributed systems and shows the usefulness of heuristic and meta heuristic approaches for the design of efficient Grid schedulers. We also discuss on requirements for a modular Grid scheduling and its integration with Grid architecture.
author_names: Fatos Xhafa

Ajith Abraham
title: Computational models and heuristic methods for Grid scheduling problems
venue: Future Gener. Comput. Syst.
year: 2010

abstract: The paper studies the problem of finding an optimal subcarrier and power allocation strategy for downlink communication to multiple users in an orthogonal frequency division multiplexing based wireless system. The problem of minimizing total power consumption with constraints on bit error rate and transmission rate for users requiring different classes of service is formulated and simple algorithms with good performance are derived. The problem of joint allocation is divided into two steps. In the first step, the number of subcarriers that each user gets is determined based on the users' average signal to noise ratio. The algorithm is shown to find the distribution of subcarriers that minimizes the total power required when every user experiences a flat fading channel. In the second stage of the algorithm, it finds the best assignment of subcarriers to users. Two different approaches are presented, the rate craving greedy algorithm and the amplitude craving greedy algorithm. A single cell with one base station and many mobile stations is considered. Numerical results demonstrate that the proposed low complexity algorithms offer comparable performance with an existing iterative algorithm.
author_names: Didem Kivanc-Tureli

Guoqing Li

Hui Liu
title: Computationally efficient bandwidth allocation and power control for OFDMA
venue: IEEE Trans. Wirel. Commun.
year: 2003

abstract: Invention is here interpreted broadly as the production of knowledge. From the viewpoint of welfare economics, the determination of optimal resource allocation for invention will depend on the technological characteristics of the invention process and the nature of the market for knowledge.
author_names: Kenneth J Arrow
title: Economic Welfare and the Allocation of Resources for Invention
year: 1962

abstract: The usefulness of Lagrange multipliers for optimization in the presence of constraints is not limited to differentiable functions. They can be applied to problems of maximizing an arbitrary real valued objective function over any set whatever, subject to bounds on the values of any other finite collection of real valued functions denned on the same set. While the use of the Lagrange multipliers does not guarantee that a solution will necessarily be found for all problems, it is "fail safe" in the sense that any solution found by their use is a true solution. Since the method is so simple compared to other available methods it is often worth trying first, and succeeds in a surprising fraction of cases. They are particularly well suited to the solution of problems of allocating limited resources among a set of independent activities.
author_names: Harvey J Everett
title: Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
year: 1963

abstract: Abstract We apply the two player game assumptions of limited search horizon and commitment to moves in constant time, to single agent heuristic search problems. We present a variation of minimax lookahead search, and an analog to alpha beta pruning that significantly improves the efficiency of the algorithm. Paradoxically, the search horizon reachable with this algorithm increases with increasing branching factor. In addition, we present a new algorithm, called Real Time A* for interleaving planning and execution. We prove that the algorithm makes locally optimal decisions and is guaranteed to find a solution. We also present a learning version of this algorithm that improves its performance over successive problem solving trials by learning more accurate heuristic values, and prove that the learned values converge to their exact values along every optimal path. These algorithms effectively solve significantly larger problems than have previously been solvable using heuristic evaluation functions.
author_names: Richard E Korf
title: Real Time Heuristic Search
venue: Artif. Intell.
year: 1990

abstract: In the AIPS98 Planning Contest, the HSP planner showed that heuristic search planners can be competitive with state of the art Graphplan and SAT planners. Heuristic search planners like HSP transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialized problem solvers such as those developed for the 24 Puzzle and Rubik's Cube in that they use a general declarative language for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are based on a simple and general heuristic that assumes that action preconditions are independent. The heuristic is then used in the context of best first and hill climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state of the art planners, and show that the simplest planner based on a pure best first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers. 2001 Elsevier Science B.V. All rights reserved.
author_names: Blai Bonet

Hector Geffner
title: Planning as heuristic search
venue: Artif. Intell.
year: 2001

abstract: As reflected in the amount of controversy, few areas in psychology have undergone such dramatic conceptual changes in the past decade as the emerging science of heuristics. Heuristics are efficient cognitive processes, conscious or unconscious, that ignore part of the information. Because using heuristics saves effort, the classical view has been that heuristic decisions imply greater errors than do "rational" decisions as defined by logic or statistical models. However, for many decisions, the assumptions of rational models are not met, and it is an empirical rather than an a priori issue how well cognitive heuristics function in an uncertain world. To answer both the descriptive question "Which heuristics do people use in which situations?" and the prescriptive question "When should people rely on a given heuristic rather than a complex strategy to make better judgments?" formal models are indispensable. We review research that tests formal models of heuristic inference, including in business organizations, health care, and legal institutions. This research indicates that (a) individuals and organizations often rely on simple heuristics in an adaptive way, and (b) ignoring part of the information can lead to more accurate judgments than weighting and adding all information, for instance for low predictability and small samples. The big future challenge is to develop a systematic theory of the building blocks of heuristics as well as the core capacities and environmental structures these exploit.
author_names: Gerd Gigerenzer

Wolfgang Gaissmaier
title: Heuristic decision making.
venue: Annual review of psychology
year: 2011

abstract: This paper introduces a theoretical framework that describes the importance of affect in guiding judgments and decisions. As used here, 'affect' means the specific quality of 'goodness' or 'badness' (i) experienced as a feeling state (with or without consciousness) and (ii) demarcating a positive or negative quality of a stimulus. Affective responses occur rapidly and automatically note how quickly you sense the feelings associated with the stimulus word 'treasure' or the word 'hate' We argue that reliance on such feelings can be characterized as 'the affect heuristic' In this paper we trace the development of the affect heuristic across a variety of research paths followed by ourselves and many others. We also discuss some of the important practical implications resulting from ways that this heuristic impacts our daily lives. 2002 Cambridge University Press. Published by Elsevier B.V.
author_names: Paul Slovic

Melissa L Finucane

Ellen Peters

Donald G MacGregor
title: The affect heuristic
venue: Eur. J. Oper. Res.
year: 2007

abstract: Abstract This paper describes an implementation of the Lin Kernighan heuristic, one of the most successful methods for generating optimal or near optimal solutions for the symmetric traveling salesman problem (TSP) Computational tests show that the implementation is highly effective. It has found optimal solutions for all solved problem instances we have been able to obtain, including a 13,509 city problem (the largest non trivial problem instance solved to optimality today)
author_names: Keld Helsgaun
title: An effective implementation of the Lin Kernighan traveling salesman heuristic
venue: Eur. J. Oper. Res.
year: 2000