Online linear programming : algorithm design and analysis
Abstract/Contents
- Abstract
- We discuss the problem of online linear programming (LP) in which the objective function and constraints are observed sequentially and not known a priori. We consider (i) stochastic input model where the columns of the constraint matrix along with the corresponding coefficients in the objective function are generated i.i.d. from an unknown distribution and revealed sequentially over time and (ii) random permutation model where the constraint matrix and the corresponding coefficients arrive in a randomly permuted order. Under the stochastic input model, we first establish convergence properties on the dual optimal solution to a large-scale LP problem and develop an adaptive learning algorithm that improves the previous algorithm performances by taking into account the past input data as well as decisions/actions already made. In the end, we present a fast algorithm for approximately solving a class of large-scale binary integer LPs. The algorithm is free of matrix multiplication and requires only one single pass over the inputs of the integer LP.
Description
Type of resource | text |
---|---|
Form | electronic resource; remote; computer; online resource |
Extent | 1 online resource. |
Place | California |
Place | [Stanford, California] |
Publisher | [Stanford University] |
Copyright date | 2020; ©2020 |
Publication date | 2020; 2020 |
Issuance | monographic |
Language | English |
Creators/Contributors
Author | Li, Xiaocheng |
---|---|
Degree supervisor | Giesecke, Kay |
Degree supervisor | Pelger, Markus |
Thesis advisor | Giesecke, Kay |
Thesis advisor | Pelger, Markus |
Thesis advisor | Glynn, Peter W |
Degree committee member | Glynn, Peter W |
Associated with | Stanford University, Department of Management Science and Engineering |
Subjects
Genre | Theses |
---|---|
Genre | Text |
Bibliographic information
Statement of responsibility | Xiaocheng Li. |
---|---|
Note | Submitted to the Department of Management Science and Engineering. |
Thesis | Thesis Ph.D. Stanford University 2020. |
Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Xiaocheng Li
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...