Accelerating combinatorial filter reduction through constraints
Reduction of combinatorial filters involves compressing state representations that robots use. Such optimization arises in automating the construction of minimalist robots. But exact combinatorial filter reduction is an NP-complete problem and all current techniques are either inexact or formalized with exponentially many constraints. This paper proposes a new formalization needing only a polynomial number of constraints, and characterizes these constraints in three different forms: nonlinear, linear, and conjunctive normal form. Empirical results show that constraints in conjunctive normal form capture the problem most effectively, leading to a method that outperforms the others. Further examination indicates that a substantial proportion of constraints remain inactive during iterative filter reduction. To leverage this observation, we introduce just-in-time generation of such constraints, which yields improvements in efficiency and has the potential to minimize large filters.
Code (0)
등록된 구현이 없습니다.
Tasks
FormSimilar Papers 제목 키워드 기반
DBP: Discrimination Based Block-Level Pruning for Deep Model Acceleration
Neural network pruning is one of the most popular methods of accelerating the inference of deep convolutional neural networks (CNNs). The dominant pruning methods, filter-level pruning methods, evaluate their performance…
Network PruningAutomatic Rank Selection for High-Speed Convolutional Neural Network
Low-rank decomposition plays a central role in accelerating convolutional neural network (CNN), and the rank of decomposed kernel-tensor is a key parameter that determines the complexity and accuracy of a neural network.…
Combinatorial OptimizationVocal Bursts Intensity PredictionAccelerating Evolutionary Construction Tree Extraction via Graph Partitioning
Extracting a Construction Tree from potentially noisy point clouds is an important aspect of Reverse Engineering tasks in Computer Aided Design. Solutions based on algorithmic geometry impose constraints on usable model …
Combinatorial Optimizationgraph partitioningFast Swap-Based Element Selection for Multiplication-Free Dimension Reduction
In this paper, we propose a fast algorithm for element selection, a multiplication-free form of dimension reduction that produces a dimension-reduced vector by simply selecting a subset of elements from the input. Dimens…
Localized Load Reduction Market Development Considering Network Constraints
With the development of the smart grid concept and the increasing expansion of advanced communication and measurement equipment, consumers can actively participate in the power system operation. The intelligent use of th…