In this paper, we develop a simple and fast online algorithm for solving a general class of binary integer linear programs (LPs)  . The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs  projected stochastic subgradient descent in the dual space. We analyze the algorithm in two different models, the stochastic input model and the random permutationmodel , with minimal  assumptions on the input of the LP . The algorithm achieves O\left(m n\right) expected regret under the stochastic input model and O\left((m+\log n)n\right) expected regret under the random permutation model, and it achieves O(m n) expected constraint violation under both models, where n is the number of decision variables and m is the number of constraints. The algorithm enjoys the same performance guarantee when generalized to a multi-dimensional LP setting which covers a wider range of applications. To complete the discussion , we employ the notion of permutational Rademacher complexity and analyze the regret of two online LP algorithms in the literature under the random permutation model . Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and the performance of the algorithms.
In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem . The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm in two different models, stochastic input and random permutation , with minimal technical assumptions on the input data . The algorithm achieves O\left(m n\right) expected regret under the stochastic input model and O\left((m+\log n)n\right) expected regret under the random permutation model, and it achieves O(m n) expected constraint violation under both models, where n is the number of decision variables and m is the number of constraints. The algorithm enjoys the same performance guarantee when generalized to a multi-dimensional LP setting which covers a wider range of applications. In addition , we employ the notion of permutational Rademacher complexity and derive regret bounds for two earlier online LP algorithms for comparison. Both algorithms improve the regret bound with a factor of \sqrt{m . Furthermore, we demonstrate how to convert the possibly infeasible solution to a feasible one through a randomized procedure. Numerical experiments illustrate the general applicability and effectiveness of the algorithms.
D
general
A
arisen in general resource allocation problem
A
(one-pass)
R
the stochastic input model and the random permutationmodel
stochastic input and random permutation
A
technical
R
of the LP
data
R
To complete the discussion
In addition
R
analyze the regret of two
derive regret bounds for two earlier
R
in the literature under the random permutation model
for comparison. Both algorithms improve the regret bound with a factor of \sqrt{m
R
the performance
effectiveness