Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range...
详细信息
ISBN:
(纸本)9783030300487
Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range of applications in low-power devices. In this paper, we investigate a model-based approach to training BNNs using constraintprogramming (CP), mixed-integer programming (MIP), and CP/MIP hybrids. We formulate the training problem as finding a set of weights that correctly classify the training set instances while optimizing objective functions that have been proposed in the literature as proxies for generalizability. Our experimental results on the MNIST digit recognition dataset suggest that-when training data is limited-the BNNs found by our hybrid approach generalize better than those obtained from a state-of-the-art gradient descent method. More broadly, this work enables the analysis of neural network performance based on the availability of optimal solutions and optimality bounds.
HPC systems are increasingly being used for big data analytics and predictive model building that employ many short jobs. In these application scenarios, HPC job dispatchers need to process large numbers of short jobs...
详细信息
ISBN:
(纸本)9783030300487
HPC systems are increasingly being used for big data analytics and predictive model building that employ many short jobs. In these application scenarios, HPC job dispatchers need to process large numbers of short jobs quickly and make decisions on-line while ensuring high Quality-of-Service (QoS) levels and meet demanding timing requirements. constraintprogramming (CP) is an effective approach for tackling job dispatching problems. Yet, the state-of-the-art CP-based job dispatchers are unable to satisfy the challenges of on-line dispatching and take advantage of job duration predictions. these limitations jeopardize achieving high QoS levels, and consequently impede the adoption of CP-based dispatchers in HPC systems. We propose a class of CP-based dispatchers that are more suitable for HPC systems running modern applications. the new dispatchers are able to reduce the time required for generating on-line dispatching decisions significantly, and are able to make effective use of job duration predictions to decrease waiting times and job slowdowns, especially for workloads dominated by short jobs.
Multi-agent path finding (MAPF) is the problem of planning a set of non-colliding paths for a set of agents so that each agent reaches its individual goal location following its path. A mutex from classical planning i...
详细信息
In this paper, we present and evaluate a new parallel propositional model counter, called gpusat2, which is based on dynamic programming (DP) on tree decompositions using log-counters. gpusat2 extends its predecessor ...
详细信息
ISBN:
(纸本)9783030300487
In this paper, we present and evaluate a new parallel propositional model counter, called gpusat2, which is based on dynamic programming (DP) on tree decompositions using log-counters. gpusat2 extends its predecessor by a novel architecture for DP that includes using customized tree decompositions, storing solutions to parts of the input instance during the computation variably in arrays or binary search trees, and compressing solution parts. In addition, we avoid data transfer between the RAM and the VRAM whenever possible and employ extended preprocessing by means of state-of-the-art preprocessors for propositional model counting. Our novel architecture allows gpusat2 to be competitive with modern model counters when we also take preprocessing into consideration. As a side result, we observe that state-of-the-art preprocessors allow to produce tree decompositions of significantly smaller width.
Augmenting a base constraint model with additional constraints can strengthen the inferences made by a solver and therefore reduce search effort. We focus on the automatic addition of streamliner constraints, which tr...
详细信息
ISBN:
(纸本)9783030300487
Augmenting a base constraint model with additional constraints can strengthen the inferences made by a solver and therefore reduce search effort. We focus on the automatic addition of streamliner constraints, which trade completeness for potentially very significant reduction in search. Recently an automated approach has been proposed, which produces streamliners via a set of streamliner generation rules. this existing automated approach to streamliner generation has two key limitations. First, it outputs a single streamlined model. Second, the approach is limited to satisfaction problems. We remove both limitations by providing a method to produce automatically a portfolio of streamliners, each representing a different balance between three criteria: how aggressively the search space is reduced, the proportion of training instances for which the streamliner admitted at least one solution, and the average reduction in quality of the objective value versus the unstreamlined model. In support of our new method, we present an automated approach to training and test instance generation, and provide several approaches to the selection and application of the streamliners from the portfolio. Empirical results demonstrate drastic improvements both to the time required to find good solutions early and to prove optimality on three problem classes.
We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning...
详细信息
ISBN:
(纸本)9783030300487
We propose joinwidth, a new complexity parameter for the constraint Satisfaction Problem (CSP). the definition of joinwidth is based on the arrangement of basic operations on relations (joins, projections, and pruning), which inherently reflects the steps required to solve the instance. We use joinwidth to obtain polynomial-time algorithms (if a corresponding decomposition is provided in the input) as well as fixed-parameter algorithms (if no such decomposition is provided) for solving the CSP. Joinwidth is a hybrid parameter, as it takes boththe graphical structure as well as the constraint relations that appear in the instance into account. It has, therefore, the potential to capture larger classes of tractable instances than purely structural parameters like hypertree width and the more general fractional hypertree width (fhtw). Indeed, we show that any class of instances of bounded fhtw also has bounded joinwidth, and that there exist classes of instances of bounded joinwidth and unbounded fhtw, so bounded joinwidth properly generalizes bounded fhtw. We further show that bounded joinwidth also properly generalizes several other known hybrid restrictions, such as fhtw with degree constraints and functional dependencies. In this sense, bounded joinwidth can be seen as a unifying principle that explains the tractability of several seemingly unrelated classes of CSP instances.
In this paper, we consider a multi-robot deployment problem involving a set of robots which must realize observation tasks at different locations and navigate through a shared network of waypoints. To solve this probl...
详细信息
ISBN:
(纸本)9783030300487
In this paper, we consider a multi-robot deployment problem involving a set of robots which must realize observation tasks at different locations and navigate through a shared network of waypoints. To solve this problem, we develop a two-level approach which alternates between (a) quickly obtaining high-level schedules based on a coarse grain CP model which approximates navigation tasks as setup times between observations, and (b) generating more accurate schedules based on a fine grain CP model which takes into account all resource usage conflicts during traversals of the shared network. the low-level layer also contains an explanation module able to generate constraints holding on high-level decision variables. these constraints (or cuts) account for interferences found in the low-level solutions and which the high-level scheduler should take into account to minimize the makespan. the proposed variants of the cut generation strategy are incomplete, the aim being to obtain good quality solutions in a short time, and they differ in the way they allow to diversify search. Experiments show the efficiency of this approach and the complementarity of the cut generation schemes proposed.
Submodular function maximization is a classic problem in optimization, with many real world applications, like sensor coverage, location problems and feature selection, among others. Back in the 809;s, Nemhauser an...
详细信息
ISBN:
(纸本)9783030192129;9783030192112
Submodular function maximization is a classic problem in optimization, with many real world applications, like sensor coverage, location problems and feature selection, among others. Back in the 80's, Nemhauser and Wolsey proposed an integer programming formulation for the general submodular function maximization. Being the number of constraints in the formulation exponential in the size of the ground set, a constraint generation technique was proposed. Since then, the method was not developed further. Given the renewed interest in recent years in submodular function maximization, the constraint generation method has been used as reference to evaluate both exact and heuristic approaches. However, the outcome of those experiments was that the method is utterly slow in practice, even for small instances. In this paper we propose several algorithmic enhancements to the constraint generation method. Preliminary computational results show that a proper implementation, while still not scalable to big instances, can be significantly faster than the obvious implementation by the book. A comparison with direct mixed integer linear programming formulations on some classes of models that admit one also show that the submodular framework, in its generality, is clearly slower than dedicated formulations, so it should be used only when those approaches are not viable.
the recent improvements in solving Maximum Satisfiability (MaxSAT) problems has allowed the usage of MaxSAT in several application domains. However, it has been observed that finding an optimal solution in a reasonabl...
详细信息
ISBN:
(纸本)9783030300487
the recent improvements in solving Maximum Satisfiability (MaxSAT) problems has allowed the usage of MaxSAT in several application domains. However, it has been observed that finding an optimal solution in a reasonable amount of time remains a challenge. Moreover, in many applications it is enough to provide a good approximation of the optimum. Recently, new local search algorithms have been shown to be successful in approximating the optimum in MaxSAT problems. Nevertheless, these local search algorithms fail in finding feasible solutions to highly constrained instances. In this paper, we propose two constraint-based techniques for improving local search MaxSAT solvers. Firstly, an unsatisfiability-based algorithm is used to guide the local search solver into the feasible region of the search space. Secondly, given a partial assignment, we perform Minimal Correction Subsets (MCS) enumeration in order to improve upon the best solution found by the local search solver. Experimental results using a large set of instances from the MaxSAT evaluation 2018 show the effectiveness of our approach.
Shared mobility is revolutionizing urban transportation and has sparked interest in optimizing the joint schedule of passengers using public transit and last-mile services. Scheduling systems must anticipate future re...
详细信息
ISBN:
(纸本)9783030192129;9783030192112
Shared mobility is revolutionizing urban transportation and has sparked interest in optimizing the joint schedule of passengers using public transit and last-mile services. Scheduling systems must anticipate future requests and provision flexibility in order to be adopted in practice. In this work, we consider a two-stage stochastic programming formulation for scheduling a set of known passengers and uncertain passengers that are realized from a finite set of scenarios. We present an optimization approach based on decision diagrams. We obtain, in minutes, schedules for 1,000 known passengers that are robust and optimized with respect to scenarios involving up to 100 additional uncertain passengers.
暂无评论