Combinatorial optimization problems play a major role in tackling applications such as healthcare, transportation, education, etc. Solving these applications usually involves satisfying a set of hard constraints while optimizing one or more objectives. In this context, exact or approximate methods can be used. While exact methods guarantee the optimality of the solution returned, they often come with an exponential running time as opposed to approximate methods that trade the solution’s quality for a better running time cost. In this context, we tackle the Nurse Scheduling Problem (NSP). The NSP consists in assigning nurses to daily shifts in a given planning horizon such that workload constraints are satisfied while hospital’s costs and nurses’ preferences are optimized. To solve the NSP, we propose implicit and explicit approaches. In the implicit solving approach, we rely on Machine Learning (ML) methods based on Association Rules Mining (ARM) and classification algorithms using historical data (past scheduling solutions) to learn and generate new solutions through the implicitly learned constraints and objectives that may be embedded in the learned patterns (e.g., Association Rules, trained ML models, etc). To quantify the quality of using our implicit approach in capturing the embedded constraints and objectives in historical data, we rely on the Frobenius Norm (FN). The latter is a quality measure used to compute the average error between the generated solutions and historical data. To compensate for the uncertainty related to the implicit approach given that the constraints and objectives may not be concretely visible in the produced solutions, we propose an alternative explicit approach where we first model the NSP using the Constraint Satisfaction Problem (CSP) framework. Then we develop Stochastic Local Search (SLS) methods and a new Branch and Bound (B&B) algorithm enhanced with constraint propagation techniques and variables/values ordering heuristics. Considering that our proposed implicit approach may not guarantee the feasibility and/or optimality of the generated solution since the constraints and objectives are represented through the learned patterns from the data, we propose a data-driven approach to passively learn the NSP as a constraint network from historical data. The learned constraint network, formulated as a CSP, will then be solved using the methods we listed earlier.