Optimization Online


Binary Decision Rules for Multistage Adaptive Mixed-Integer Optimization

Dimitris Bertsimas(dbertsim***at***mit.edu)
Angelos Georghiou(angelosg***at***control.ee.ethz.ch)

Abstract: Decision rules provide a flexible toolbox for solving the computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability, and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameterised binary decision rule structure and derive the exact reformulation of the decision rule problem. In the cases where the resulting optimization problem grows exponentially with respect to the problem data, we provide a systematic methodology that trades-off scalability and optimality, resulting to practical binary decision rules. We also apply the proposed binary decision rules to the class of problems with random-recourse and show that they share similar complexity as the fixed-recourse problems. Our numerical results demonstrate the effectiveness of the proposed binary decision rules and show that they are (i) highly scalable and (ii) provide high quality solutions.

Keywords: Adaptive Optimization, Binary Decision Rules, Mixed-integer optimization.

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences

Category 3: Integer Programming

Citation: Dimitris Berstimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, USA. Angelos Georghiou: Automatic Control Laboratory, Swiss Federal Institute of Technology, Zurich, Switzerland. August 2014

Download: [PDF]

Entry Submitted: 08/20/2014
Entry Accepted: 08/20/2014
Entry Last Modified: 08/20/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society