Chaotic simulated annealing (CSA) proposed by Chen and Aihara has been successfully used to solve a variety of combinatorial optimization problems. CSA uses a penalty term to enforce solution validity as in the original Hopfield–Tank approach. There exists a conflict between solution quality and solution validity in the penalty approach. It is often difficult to adjust the relative magnitude of the penalty term, so as to achieve a high quality solution which is at the same time valid. To overcome this, we incorporate augmented Lagrange multipliers into CSA, obtaining a method that we call augmented Lagrange chaotic simulated annealing (AL-CSA). Simulation results on two constrained optimization benchmarks derived from the Hopfield–Tank formulation of the traveling salesman problem show that AL-CSA can maintain CSA’s good solution quality while avoiding the potential difficulties associated with penalty terms. Furthermore, AL-CSA’s convergence time is shorter and choice of system parameters is easier compared to CSA.