This chapter builds on the foundations of Markov chain Monte Carlo methods from the previous chapter, introducing key modifications and enhancements for solving complex discrete optimization problems. The focus is on simulation-based algorithms for combinatorial optimization, with applications to substitution ciphers, the travelling salesman problem, and the knapsack problem. Special attention is given to simulated annealing—particularly for the travelling salesman problem—and to the cross-entropy method for rare event estimation and optimization. The chapter also introduces heuristic methods based on locally informed proposals, which represent a significant advance in efficiently exploring complex state spaces in combinatorial problems. Throughout, practical implementation is emphasized, with algorithmic steps, illustrative examples, and publicly available Python code provided to support hands-on learning. By the end of the chapter, readers will understand how techniques such as simulated annealing, locally informed proposals, and cross-entropy-based algorithms can substantially enhance the effectiveness of stochastic optimization in challenging discrete settings.