Chaotic simulated annealing (CSA) has recently been proposed and successfully used in solving combinatorial optimization problems by Chen and Aihara. In comparison with the Hopfield-Tank approach, CSA significantly improves the network's ability to find solutions of good quality and even global minima. However, CSA still uses a penalty term to enforce solution validity like the Hopfield-Tank approach. There exists a conflict between solution quality and solution validity in the penalty approach. In addition, the relative magnitude of the penalty term often needs to be determined by trial-and-error. In this paper we incorporate augmented Lagrange multipliers into CSA, obtaining a method that we call augmented Lagrange chaotic simulated annealing (AL-CSA), which eliminates the need of the penalty term and guarantees solution validity, and at the same time maintains CSA's solution quality. We demonstrate this method with the 10-city Traveling Salesman Problem.