A military decision maker is typically confronted by the task of determining optimal course of action under some constraints in complex uncertain situation. Thus, a new class of Combinational Constraint Optimization Problem (CCOP) is formalized, that is utilized to solve this complex Operation Optimization Problem. The object function of CCOP is modeled by Influence net, and the constraints of CCOP relate to resource and collaboration. These constraints are expressed by Pseudo-Boolean and Boolean constraints. Thus CCOP holds a complex mathematical configuration, which is expressed as a 0 1 integer optimization problem with compositional constraints and unobvious optimal object function. A novel method of Genetic Algorithm (GA) combination of Boolean Constraint Programming (BCP) is proposed to solve CCOP. The constraints of CCOP can be easily reduced and transformed into Disjunctive Normal Form (DNF) by BCP. The DNF representation then can be used to drive GA so as to solve CCOP. Finally, a numerical experiment is given to demonstrate the effectiveness of above method.