Online Linear Programming with Batching

Haoran Xu; Peter W. Glynn; Yinyu Ye

cs.LGAug 1, 2024

Online Linear Programming with Batching

Authors: Haoran Xu, Peter W. Glynn, Yinyu Ye

Organizations: Department of Management Science and Engineering, Stanford University

Abstract

We study Online Linear Programming (OLP) with batching. The planning horizon is cut into $K$ batches, and decisions on orders can be delayed to the end of their associated batch. The ability to delay decisions improves operational performance, as measured by regret. We study two questions: (1) What is a lower bound on the regret as a function of $K$ and the length of the planning horizon? (2) Which algorithms can achieve this regret lower bound? This paper analyzes these questions when the distribution of the reward has a continuous support. We provide an $Ω(\log K)$ regret lower bound in the single-resource case, and we provide pricing algorithms having an $O(\log K)$ regret in the setting with Poisson arrivals and multiple types of resources. All the algorithms update the prices at most $K$ times and only delay orders of the first and the last batches. All the regret bounds are independent of the length of the planning horizon. Finally, we study a more realistic large support setting where the number of distinct order types is finite but scales with the total number of orders. We prove that our $Θ(\log K)$ bounds still hold for the batching operation of a multisecretary problem with discretized uniform rewards in this large support setting, provided the support grows fast enough. This suggests that the continuous support setting that is the paper's focus serves as a useful theoretical surrogate for the more realistic large finite support setting.

Figures & tables

p_{j+1}=\arg\min_{p\geq 0}{\frac{{b_{j}}^{T}p}{n-j}}+\frac{1}{j}\sum_{t=1}^{j}(\Delta_{j}(p))^{+}.

Algorithm 0 Action-History-Dependent Learning Algorithm (AhdLA)

Figure 1: Regret of $\pi_{1}$ and $\tilde{\pi}_{1}$

Figure 2: Regret of $\pi_{2}$ and Modified $\tilde{\pi}_{2}$

Figure 3: Finite support with large support: Regret of Algorithm 3.4

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	$K=2$	$K=8$	$K=32$	$K=64$	$K=128$
$m=1,\;n=1280$	12.02	18.80	23.19	25.74	27.67
$m=1,\;n=6400$	12.12	18.01	23.70	25.86	28.91
$m=1,\;n=32000$	11.57	18.67	24.29	26.75	29.56
$m=1,\;n=64000$	11.49	17.88	23.78	26.22	29.13
$m=1,\;n=128000$	11.82	17.40	24.11	26.85	29.60
$m=4,\;n=1280$	67.37	99.04	112.49	115.75	118.95

Appendix

Table 1: Regret of

\pi_{1}

	$K=2$	$K=8$	$K=32$	$K=64$	$K=128$
$m=1,\;n=1280$	7.91	20.12	25.55	27.9	30.39
$m=1,\;n=6400$	7.80	19.70	25.59	28.12	31.10
$m=1,\;n=32000$	7.78	19.12	24.56	27.57	30.31
$m=1,\;n=64000$	7.72	19.37	25.10	27.87	30.65
$m=1,\;n=128000$	7.85	19.39	24.85	28.10	30.94
$m=4,\;n=1280$	34.24	107.24	120.60	123.18	124.95

Appendix

Table 2: Regret of

\tilde{\pi}_{1}

	$K=2$	$K=8$	$K=32$	$K=64$	$K=128$
$\lambda=10,\;T=128$	9.51	20.94	40.64	47.48	51.19
$\lambda=10,\;T=512$	9.46	31.37	42.92	46.02	53.31
$\lambda=10,\;T=1024$	9.31	32.00	42.04	46.27	52.66
$\lambda=50,\;T=128$	9.64	32.14	40.79	47.72	52.20
$\lambda=50,\;T=512$	9.29	30.43	41.19	45.84	51.28
$\lambda=50,\;T=1024$	9.71	30.60	40.74	46.78	51.96

Appendix

Table 3: Regret of

\pi_{2}

	$K=2$	$K=8$	$K=32$	$K=64$	$K=128$
$\lambda=10,\;T=128$	9.66	19.75	28.39	34.18	36.76
$\lambda=10,\;T=512$	9.82	20.42	29.81	33.45	38.96
$\lambda=10,\;T=1024$	9.44	20.13	30.03	33.10	38.61
$\lambda=50,\;T=128$	9.62	20.17	28.67	33.57	38.66
$\lambda=50,\;T=512$	9.43	19.71	29.17	34.02	37.46
$\lambda=50,\;T=1024$	10.26	19.32	29.06	33.54	37.99

Appendix

Table 4: Regret of Modified

\tilde{\pi}_{2}

	$K$
$n$	2	8	32	64	128
$\alpha=0$
1280	$0.66$	$2.23$	$4.25$	$5.06$	$5.90$
6400	$0.00$	$0.35$	$1.77$	$2.64$	$3.73$
32000	$0.00$	$0.00$	$0.22$	$0.67$	$1.48$
64000	$0.00$	$0.00$	$0.00$	$0.18$	$0.61$

Appendix

Table 5: Regret of Algorithm 3.4

Explore similar work

Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangLinear Programming \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret
School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China
Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving
Sep 23, 2026Jiameng LyuLinear Programming Learning-Augmented Algorithms
Department of Management Science, School of Management, Fudan University, Shanghai 200433, China
Online Packet Scheduling with Deadlines and Learning
May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetDeadlines Knapsack Constraint
Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team

Aug 1, 2024, cs.DSJ/K move · Enter open · S save

Infrequent Resolving Algorithm for Online Linear Programming

Guokai Li, Zizhuo Wang, Jingwei Zhang

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, 518172, P.R. China

Linear Programming \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Free

Open paper AskPDF arXiv

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only

O(\log\log T)

times over the time horizon

T

. Moreover, when we are allowed to solve LPs only

M

times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly

O\left(T^{(1/2)^{M-1}}\right)

regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

Abstract

Explore similar work

Infrequent Resolving Algorithm for Online Linear Programming

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

Online Packet Scheduling with Deadlines and Learning