We study the problem of learning good heuristic functions for classical planning tasks with neural networks based on samples represented by states with their cost-to-goal estimates. The heuristic function is learned for a state space and goal condition with the number of samples limited to a fraction of the size of the state space, and must generalize well for all states of the state space with the same goal condition. Our main goal is to better understand the influence of sample generation strategies on the performance of a greedy best-first heuristic search (GBFS) guided by a learned heuristic function. In a set of controlled experiments, we find that two main factors determine the quality of the learned heuristic: the algorithm used to generate the sample set and how close the sample estimates to the perfect cost-to-goal are. These two factors are dependent: having perfect cost-to-goal estimates is insufficient if the samples are not well distributed across the state space. We also study other effects, such as adding samples with high-value estimates. Based on our findings, we propose practical strategies to improve the quality of learned heuristics: three strategies that aim to generate more representative states and two strategies that improve the cost-to-goal estimates. Our practical strategies result in a learned heuristic that, when guiding a GBFS algorithm, increases by more than 30% the mean coverage compared to a baseline learned heuristic.

Offline algorithm configuration methods search for fixed parameter values for a given set of problem instances. For each parameter, such methods perform an equivalent to a constant regression, since the parameter value remains constant for any problem instance. However, optimal parameter values may depend on instance features, such as the instance size. In this paper, we represent parameters by non-constant models, which set the parameter values according to the instance size. Instead of searching for parameter values directly, the configuration process calibrates such models. In particular, we propose a simple yet effective linear model, which approximates linear relations between instance size and optimal parameter values. For modeling nonlinear relations, we propose piecewise and log-log linear models. The evaluation of the proposed methods on four configuration scenarios show good performance gains in comparison to traditional instance-independent algorithm configuration with comparable tuning effort.

Speedy delivery of products is important for customers and the optimization of the last mile has particular challenges. In recent years drone-supported delivery has become increasingly feasible and therefore a topic of intense research. In this paper we address a traveling salesman problem where a truck has to serve customers and can use drones as flying sidekicks for the delivery of parcels. The goal is to assign customers to be either served by the truck or by some drone and schedule all events in order to minimize the total completion time of whole operation. We propose a heuristic for this problem, and introduce several novel components, including a multi-armed bandit selection for partitioning customers, an efficient matching-based heuristic for assigning drones to customers, local searches to improve solutions, and a fast greedy scheduler to estimate solution quality. In computational experiments we show that the combined approach finds better solutions than current methods, in less time.

There has been intensive research on tiebreakers for insertion-based constructive heuristics in the permutation flow shop scheduling problem when the objective is to minimize the makespan. In this paper we analyze the space of all possible tie-breaking rules for the most common insertion orders, and evaluate the efficacy of existing tiebreakers based on this analysis. We find that an optimal tie breaker would produce results that are about 1% better than current best tie breakers. We propose a constructive heuristic based on a truncated cyclic best-first search in the space of all tie breakers and show that it closely approximates the solutions that such an optimal tie breaker can achieve.

Efficiently exploiting thread-level parallelism has been challenging. Many parallel applications are not sufficiently balanced or CPU-bound to take advantage of the increasing number of cores and the highest possible operating frequency. Moreover, many variables may change according to the system (input set, microarchitecture, and number of cores) or during execution, influencing each parallel region in different ways. Therefore, the task of rightly choosing the ideal configuration (number of threads and DVFS) for each parallel region to deliver the best Energy-Delay Product (EDP) is not straightforward. While the significant number of variables prevents the use of exhaustive search methods, the changing nature of the problem precludes offline strategies. Few solutions are online and synergistically consider thread throttling and DVFS. However, they lack transparency (demand changes in the original code) and/or adaptability (do not automatically adjust to applications at run-time). Our proposed Hoder covers all the characteristics above, optimizing at run-time any dynamically linked OpenMP application, without requiring any code transformation or recompilation. We show Hoder's efficiency by comparing it to two exhaustive offline and two online search approaches, three state-of-the-art techniques, and regular OpenMP execution, considering different setups (Intel 44-, 16- and 12-core; AMD 8- and 12-core).

Redistricting problems arise when due to evolving attributes, current districts get increasingly inefficient or even infeasible. A typical example are electoral districts of roughly the same population, which after changes in its distribution, become imbalanced. Since the cost of creating entirely new districts, in general, is too high, redistricting problems have two conflicting objectives: to find an improved or optimal solution while keeping the changes to existing districts small. In this paper we propose an efficient heuristic for redistricting problems, which can consider similarity to existing districts together with several other constraints, such as balance, connectedness, and compactness. In an experimental study, we evaluate the contribution of heuristic strategies, the effect of different attribute modification models, and the effect of different similarity metrics on the quality of the redefined districts.

In this paper we consider districting problems with routing criteria. Such problems arise when clients in a commercial district need to be attended daily and the time to visit them is limited, for example by working hours of retail businesses. Routing costs are modeled by traveling salesman tours starting from predetermined depot locations. Besides having low routing costs, districts must also satisfy balancing (e.g. of total demand or workload) and contiguity constraints, and may also be required to be geographically compact. We propose a general heuristic for solving such problems. It iteratively builds new solutions by a greedy constructive heuristic, and then improves them by a hybrid alternating tabu search strategy. We further propose an efficient scheme for maintaining high-quality routes under small modifications to districts, for example incurred by neighborhood search operators. In extensive computational experiments we study the different components of our method, and show that it is effective in treating a number of problem variants with different constraints.

Assembly lines in sheltered work centers are a strategy for integrating persons with disabilities in the work force. In such centers, the assignment of tasks to workers must consider particularities of each worker and precedences between the tasks, and must be done in a way that maximizes the production rate of the assembly line. In this paper we present an application of genetic programming for evolving task selection rules that are competitive with rules manually created and described in literature. These rules are useful in constructive heuristics for rapidly producing solutions of good quality, and can be embedded into more sophisticated heuristic methods to improve them.

Districting is the problem of grouping basic geographic units into clusters called districts. Districts are typically required to be geometrically compact, contiguous, and evenly balanced with respect to attributes of the basic units. Though most applications share these core criteria, domain-specific constraints and objective functions are common. This leads to a fragmented literature with different approaches for similar domains and hinders comparisons between these approaches. In this paper we study a unified heuristic approach that can handle three of the most common objective functions concerning compactness: diameter, p-center and p-median, as well as a variable number of balancing attributes. We propose a multistart method which iteratively constructs greedy randomized solutions followed by an improvement phase which alternates between optimizing compactness and satisfying balancing constraints through a series of tabu searches. Experiments show that the proposed method is competitive when compared to approaches in the literature which are specific to each objective, improving known upper bounds in some cases.

The automatic design of heuristic search methods has been applied successfully to many optimization problems. In this paper we study the application of automatic algorithm configuration to the permutation flow shop scheduling problem with makespan minimization. Our approach consists in using a grammar to determine how to combine individual algorithmic components into an iterated local search, coupled with a parametric representation for the instantiations of such a grammar. To explore the algorithmic search space we employ a procedure based on racing. The obtained algorithms are evaluated on two well-known benchmarks and compared to state-of-the-art heuristics.

A way of minimizing the opportunity of cheating in exams is to assign different tests to students. The likelihood of cheating then depends on the proximity of the students' desks, and the similarity of the tests. The test-assignment problem is to find an assignment of tests to desks that minimizes that total likelihood of cheating. The problem is a variant of a graph coloring problem and is NP-hard. We propose a new heuristic solution for this problem. Our approach differs from the usual way of designing heuristics in two ways. First, we reduce test-assignment to the more general unconstrained binary quadratic programming. Second, we search for a good heuristic using an automatic algorithm configuration tool that evolves heuristics in a space of algorithms built from known components for binary quadratic programming. The best hybrid heuristics found repeatedly recombine elements of a population of elite solutions and improve them by a tabu search. Computational tests suggest that the resulting algorithms are competitive with existing heuristics that have been designed manually.

For a given state space and admissible heuristic function h there is always a tie-breaking strategy for which A* expands the minimum number of states [Dechter and Pearl, 1985]. We say that these strategies have optimal expansion. Although such a strategy always exists it may depend on the instance, and we currently do not know a tie-breaker that always guarantees optimal expansion. In this paper, we study tie-breaking strategies for A*. We analyze common strategies from the literature and prove that they do not have optimal expansion. We propose a novel tie-breaking strategy using cost adaptation that has always optimal expansion. We experimentally analyze the performance of A* using several tie-breaking strategies on domains from the IPC and zero-cost domains. Our best strategy solves significantly more instances than the standard method in the literature and more than the previous state-of-the-art strategy. Our analysis improves the understanding of how to develop effective tie-breaking strategies and our results also improve the state-of-the-art of tie-breaking strategies for A*.

The goal of the PROTERRA project of the Brazilian National Institute of Colonization and Agrarian reform (INCRA) is to establish settlements of multiple families on land which formerly had a single owner. The main problem which arises in the project is to subdivide the land into lots to be designated to the families. This problem is difficult since several constraints stemming from legal or ethical considerations have to be considered. Among the constraints are respecting natural reserves, balancing access to rivers with the size of the lots, and a fair distribution with respect to soil quality.

The ever-increasing complexity of applications covered by wireless sensor networks (WSNs) demands for increasing memory size, which in turn increases the power drain. It is well known that SRAM power consumption can be reduced by employing a banked structure, where unused banks are switched into the low leakage retention mode. In this work, we propose a new strategy for memory banking, taking advantage of the software properties of WSN, and achieving aggressive power savings. We present a detailed model for the energy saving for equally sized banks with two power management schemes: a best-oracle policy and a simple greedy policy. Thanks to our modeling, at design time the optimum number of banks can be estimated, and the design can reach huge energy savings. The memory content allocation and the power management problem were solved by an integer linear program formulation for two real wireless sensor network application (based on TinyOS and ContikiOS). Experimental results show an energy reduction of up to 77.4% for a partition overhead of 1%.

Pattern databases have been successfully applied to several problems. Their use assumes that the goal state is known, and once the pattern database is built, commonly it can be used by all instances. However, in Sokoban, before solving the puzzle, the goal position of each stone is unknown. Moreover, each Sokoban instance has its own state space search. In this paper we apply pattern databases to Sokoban. The proposed approach uses an instance decomposition, that allows multiple possible goal states to be abstracted into a single state. Thus, an instance dependent pattern database is employed. Experiments with the standard set of instances show that the proposed approach overcomes the current best lower bounds in initial states for several instances. Furthermore, three of these new best lower bounds match exactly with the optimal solution length. Finally, we run experiments of 5 million explored states for each instance. Nine instances were solved with optimality guarantees, while only four instances were solved under the same conditions by previous methods.

In this paper we present a genetic algorithm for solving the gemstone cutting problem. The goal of this problem is to find the largest faceted cut design which fits inside a given rough gemstone. We propose a fast algorithm for finding the largest scaling factor of a faceted cut, once its center and orientation angles are given, as well as a real-valued genetic algorithm for finding the cut having the largest volume. Finally we present experimental results obtained using a set of 50 scanned gemstones and compare the results with similar ones from the literature.

We study the effect of perturbations on the Price of Anarchy for the Traffic Assignment Problem. Adopting the smoothed analysis approach, we randomly perturb the latency functions of the given network and estimate the expected Price of Anarchy on the perturbed instances. We provide both theoretical and experimental results that show that the Smoothed Price of Anarchy is of the same order of magnitude as the original one.

Cellular automata models for traffic movement assume that vehicles are particles without routes. However, if one is interested in analysing microscopic properties, it is necessary to assign a route to each trip. This paper discusses the latest developments in the ITSUMO traffic simulator. These developments aim at modeling more sophisticated drivers’ behaviors such as en-route decision-making. They were tested in two scenarios, one being a real-world traffic network. We extensively discuss the effects of the use of various routing algorithms, as well as ration demand/capacity, control measures, network topologies, and re-planning strategies.

Quaternary logic has shown to be a promising alternative for implementing FPGAs, since voltage mode quaternary circuits can reduce the circuits' cost and at the same time reduce its power consumption. In this paper, we study the implementation of circuits in quaternary logic. To obtain cost-effective implementations of quaternary circuits, we propose a mapping from binary to quaternary circuits based on integer linear programming. Our results show that the expected improvements can be achieved, reducing, in average, the number of transistors by 27% and the number of nets by 19%, compared to a binary implementation.

This paper presents a combination of the BVP-path planner and Monte Carlo localization to assist a robot in the global localization problem in sparse environments. This kind of environment poses a very difficult situation in this problem, since several of its regions do not provide relevant information to permit the robot to recover its pose. This paper proposes a strategy that distributes particles only in relevant parts of the environment using the information about the environment structure. Afterwards, it leads the robot along these regions using the numeric solution of a BVP involving Laplace equation. In the experiments, we also show that the information about robot motion can be used to improve the convergence rate to the correct robot pose. Simulation results are presented to illustrate the potential of the method.

Message-passing is a well known approach for parallelizing programs. The widely used standard MPI (Message passing interface) also defines C++ bindings. Nevertheless, there is a lack of integration of object-oriented concepts. In this paper, we describe our design of TPO++, an object-oriented message-passing library written in C++ on top of MPI. Its key features are easy transmission of objects, type-safety, MPI-conformity and integration of the C++ Standard Template Library.