Online linear programming : algorithm design and analysis

Placeholder Show Content

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...