Online linear programming : algorithm design and analysis
- 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.
|Type of resource
|electronic resource; remote; computer; online resource
|1 online resource.
|Glynn, Peter W
|Degree committee member
|Glynn, Peter W
|Stanford University, Department of Management Science and Engineering
|Statement of responsibility
|Submitted to the Department of Management Science and Engineering.
|Thesis Ph.D. Stanford University 2020.
- © 2020 by Xiaocheng Li
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...