Text

Learning in Sequential Bilevel Linear Programming

We consider a framework for sequential bilevel linear programming in which a leader and a follower interact over multiple time periods. In each period, the follower observes the actions taken by the leader and reacts optimally, according to the follower’s own objective function, which is initially unknown to the leader. By observing various forms of information feedback from the follower’s actions, the leader is able to refine the leader’s knowledge about the follower’s objective function and, hence, adjust the leader’s actions at subsequent time periods, which ought to help in maximizing the leader’s cumulative benefit. We show that greedy and robust policies adapted from previous work in the max-min (symmetric) setting might fail to recover the optimal full-information solution to the problem (i.e., a solution implemented by an oracle with complete prior knowledge of the follower’s objective function) in the asymmetric case. In contrast, we present a family of greedy and best-case policies that are able to recover the full-information optimal solution and also provide real-time certificates of optimality. In addition, we show that the proposed policies can be computed by solving a series of linear mixed-integer programs. We test policy performance through exhaustive numerical experiments in the context of asymmetric shortest path interdiction, considering various forms of feedback and several benchmark policies.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION; Vol.4 No.2 Spring 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 174-199

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

LEARNING
ROBUST OPTIMIZATION
ONLINE OPTIMIZATION
BILEVEL PROGRAMMING
INCOMPLETE INFORMATION

Info Detail Spesifik

https://doi.org/10.1287/ijoo.2021.0063

Pernyataan Tanggungjawab

Juan S. Borrero, Oleg A. Prokopyev, Denis Saure

Versi lain/terkait

Lampiran Berkas

Komentar