Abstract: The paper analyses different techniques that might be employed in order to solve various problems of combinatorial optimization and argues that the best results can be achieved by the use of software, running on a general-purpose computer, together with an FPGA-based reconfigurable co-processor. It suggests architecture of combinatorial co-processor, which is based on hardware templates and consists of reconfigurable functional and control units. Finally the paper demonstrates how to utilize the co-processor for two practical applications formulated over discrete matrices that are satisfiability and covering problems.