Doubly constrained network for combinatorial optimization
In this paper, we propose a neural approach for solving combinatorial optimization problems having two competing sets of constraints. Based on the Lagrange multiplier method, a discrete-time dynamical system is designed so that those constraints are automatically satisfied. We study the convergence and the bifurcation properties. We also show experimental results when applied to traveling salesman problems and quadratic assignment problems. Our approach can obtain better solutions even for relatively large-scale problems than binary or Potts spin approaches.
combinatorial optimization traveling salesman problem deterministic annealing lagrange method hard constraint