Combinatorial decision problems lie at the intersection of Operations Research (OR) and Artificial Intelligence (AI), encompassing structured optimization tasks such as submodular selection, dynamic programming, planning, and scheduling. These problems exhibit exponential growth in decision complexity, driven by interdependent choices coupled through logical, temporal, and resource constraints. Classical optimization frameworks—including integer programming, submodular optimization, and dynamic programming—offer rigorous theoretical foundations but often struggle to scale in high-dimensional, uncertain, or dynamic environments.
This survey provides a unified overview of classical and learning-augmented approaches for combinatorial decision optimization. It reviews fundamental mathematical models and algorithmic paradigms, spanning submodular minimization and maximization, sequential and stochastic dynamic programming, and temporal and resource-constrained scheduling. The survey further examines how Machine Learning (ML) and Reinforcement Learning (RL) enhance these frameworks by learning heuristic policies, approximating value functions, and guiding branching or rollout decisions. Hybrid ML/RL–optimization methods are highlighted as a means to extend the reach of traditional solvers to adaptive, data-driven, and large-scale decision spaces.
By integrating classical combinatorial structures with learning-based inference, this survey underscores the emergence of ML-assisted decision solvers as a new paradigm for scalable planning and optimization. The resulting hybrid frameworks fuse the interpretability and rigor of optimization theory with the adaptability and generalization power of modern AI, offering a consolidated perspective on the convergence of OR and AI in decision optimization.