687. Enhancing Decision Tree Analysis via Mixed-Integer Linear Programming and Polyhedral Analysis
Invited abstract in session MD-33: Algorithms in Decision Modelling, stream Decision Analysis.
Monday, 14:30-16:00Room: Maurice Keyworth 1.31
Authors (first author is the speaker)
| 1. | Mahdi Doostmohammadi
|
| Management Science, University of Strathclyde | |
| 2. | Jitamitra Desai
|
| Decision Sciences, Indian Institute of Management Bangalore |
Abstract
This study presents a novel mathematical programming approach to decision tree analysis, addressing the limitations of traditional methods such as stochastic dynamic programming. We model decision trees as path-based polynomial programmes and reformulate them into mixed-integer linear programs (MILP), solvable with standard optimization techniques. In order to strengthen the MILP formulation, we apply polyhedral analysis to derive families of strong valid inequalities for the feasible region of the MILP model. These valid inequalities (cutting planes) are integrated into a branch-and-cut framework to solve medium- to large-scale decision tree instances. Preliminary computational results demonstrate the effectiveness of this exact approach in solving decision tree problems.
Keywords
- Decision Analysis
- Mathematical Programming
- Branch and Cut
Status: accepted
Back to the list of papers