A method is developed, assessed, and demonstrated for addressing objective functions and constraints within the context of combinatorial optimization problems. The penalty-free method developed, referred to as constraint annealing, eliminates the use of traditional constraint penalty factors by treating the objective functions and constraints as separate and concurrently solved minimization problems within a global optimization search framework. The basis of the constraint annealing algorithm is a highly scalable method based on the method of parallel simulated annealing with mixing of states. Unique to constraint annealing is a novel approach that employs both global solution acceptance and local objective function and constraint statistics in the calculation of adaptive cooling temperatures that are specific to each objective function and constraint. The constraint annealing method is assessed against a traditional penalty-factor approach for a realistic core loading pattern design problem and shown to be robust with respect to elimination of arbitrary weighting factors on constraint values. In addition, the constraint annealing method is demonstrated to be robust with respect to parallel scaling as well as improved optimization performance on high-performance-computing systems.