Solving Influence Diagrams: Efficient Mixed-Integer Programming Formulation and Heuristic

Abstract

In this paper, we propose novel mixed-integer linear programming (MIP) formulations to model decision problems posed as influence diagrams. We also present a novel heuristic that can be employed to warm start the MIP solver, as well as provide heuristic solutions to more computationally challenging problems. We provide computational results showcasing the superior performance of these improved formulations as well as the performance of the proposed heuristic. Lastly, we describe a novel case study showcasing decision programming as an alternative framework for modelling multi-stage stochastic dynamic programming problems.

Helmi Hankimaa

Doctoral Researcher

Helmi Hankimaa is a doctoral researcher at the department of Mathematics and Systems Analysis at Aalto University.

Olli Herrala

Doctoral Researcher

Olli Herrala is a Doctoral Candidate in the Systems Analysis Laboratory in Aalto University.

Fabricio Oliveira

Associate Professor of Operations Research

Fabricio Oliveira is an Associate Professor of Operations Research at DTU Management. He also holds a position of Adjunct Professor in the Department of Mathematics and Systems Analysis at Aalto University

Jaan Tollander de Balsch

Research Assistant

Jaan Tollander de Balsch is a computer scientist with a background in applied mathematics.