Simple and Fast Algorithm for Binary Integer and Online Linear Programming
share
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, stochastic input model and random permutation model, with minimal assumptions on the input of the LP. The algorithm achieves O(m^2 √(n)) expected regret under the stochastic input model and O((m^2+log n)√(n)) 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. Furthermore, the algorithm is generalized to a multi-dimensional LP setting which covers a wider range of applications and features for the same performance guarantee. Numerical experiments illustrate the general applicability and the performance of the algorithms.
READ FULL TEXT