Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems

This example involves selecting a set of fixed-route transit lines to operate such that passenger coverage is maximized, while adhering to vehicle capacity constraints and satisfying a budget constraint. By framing this as an assignment-type integer program, we aim to find the optimal solution that balances cost and service efficiency. More specifically, consider a transit system with four stops: $A$, $B$, $C$, and $D$. There are three candidate transit lines: line $1$, which travels from $A$ to $C$ to $D$; line $2$, which travels from $A$ to $B$ to $C$ to $D$; and line $3$, which travels from $C$ to $A$ to $B$ to $D$. These lines cost $20$, $40$, and $30$ respectively to operate. Each transit line operates a bus with a capacity of $2$ passengers. This capacity applies uniformly at all points along the route. We have six passengers: passengers $1$ and $2$ need to travel from $C$ to $B$, passengers $3$, $4$, and $5$ from $C$ to $D$, and passenger $6$ from $A$ to $B$. These transit lines, their costs, and passenger routes are illustrated in Figure 1 and Figure 2.

For simplicity, we assume each passenger must travel directly from their origin to their destination on a single bus line (i.e., no transfers). To serve a passenger, the line chosen must be open and cover the passenger’s entire route. The total cost of opened lines must stay within the given budget of $70$. Therefore, we can open at most $2$ lines. Our goal is to choose a set of lines to open within the budget and assign passengers to these lines, maximizing the number of passengers served while adhering to these rules. If a line covers a passenger’s route, assigning this passenger to the line generates a reward of $1$; otherwise, the reward is $0$. The objective is to maximize the overall generated reward in this context.

To solve this problem, we can construct a capacity vector for each of the three lines, as shown in Figure 1. Line $1$ has a capacity vector of $(2,2)$, while $2$ and $3$ have capacity vectors of $(2,2,2)$. Each entry represents the maximum number of passengers that can be accommodated on a segment of the line. The length of each vector corresponds to the number of edges in that line. Figure 2 illustrates how passengers utilize different lines and the corresponding weight vectors. For example, passengers $1$ and $2$, traveling from $C$ to $B$, have weight vectors $(0,0)$ for line $1$, $(0,0,0)$ for line 2, and $(1,1,0)$ for line $3$. These vectors indicate which segments of each line are used by the passengers, with $1$ representing a used segment and $0$ an unused segment. The reward of assigning passengers to a line depends on whether the line covers their route. For instance, assigning passengers $1$ and $2$ to line $1$ or $2$ yields no reward as these lines do not cover their route, while assigning them to line $3$ gives a reward of $1$ per person. To obey capacity constraints, the sum of weight vectors for passengers assigned to a line cannot exceed that line’s capacity vector entry-wise. For example, we cannot assign passengers $1$, $2$, and $3$ to line $3$ as it would exceed the capacity $(3>2)$ for the edges from $C$ to $A$ and $A$ to $B$.

Based on these definitions, we can formulate this problem as an assignment-type integer program. This formulation is a specific case of GBAP, which we will present in details in Section 1.2, specifically in (1.1). It can be verified directly that in this example, the optimal solution is to operate lines $2$ and $3$, covering 5 passengers, with only one passenger (from C to D) left unserved.

Building on the warm-up example, we now formally define GBAP. This problem involves selecting a set of bins within a given budget and assigning a set of items to these selected bins under multidimensional capacity constraints, with the objective of maximizing the assignment reward. To help understand this model, one can think of transit lines as bins and passengers as items to be allocated. Specifically, consider a system with $L$ bins and $P$ items. Each bin $l\in[L]$¹¹1Here, $[n]$ denotes the set $\{1,2,\ldots,n\}$ for any integer $n$. is characterized by a utilization cost $c_{l}\in\mathbb{Q}_{+}$ and an $n_{l}$-dimensional capacity vector $f_{l}=\left(f_{l}^{(1)},\ldots,f_{l}^{(n_{l})}\right)\in\mathbb{Z}^{n_{l}}_{+}$. In our warm-up example, the capacity vector $f_{l}$ has uniform entries across all dimensions. However, in our generalized model, this capacity can vary across dimensions (see Remark 1.2 for further details). Additionally, the dimension $n_{l}$ corresponds to the number of edges involved in a line in the warm-up example. Each item $p\in[P]$ has an $n_{l}$-dimensional weight vector for each bin $l$: $r_{lp}=\left(r_{lp}^{(1)},\ldots,r_{lp}^{(n_{l})}\right)\in\{0,1\}^{n_{l}}$ , where the $1$s in $r_{lp}$ (if any) appear in consecutive positions within the vector. This structure reflects the assumption that routes consist of consecutive edges, as motivated by the warm-up example where routes follow contiguous edges in a line. Assigning item $p$ to bin $l$ yields a reward $v_{lp}\geq 0$. The objective is to maximize the total reward through an assignment that satisfies three constraints: (i) the total weight of items assigned to each bin does not exceed the bin’s capacity in any dimension, (ii) each item is assigned to at most one bin, (iii) items can only be assigned to utilized bins, and (iv) the total cost of utilized bins does not exceed a given budget $B\in\mathbb{Q}_{+}$.

The GBAP problem can be formulated as a $0$-$1$ linear integer programming problem:

(1.1b) ensures that the budget constraint is respected. (1.1c) guarantees that the multidimensional capacity of bins is not breached by the assigned items. (1.1d) requires that item $p$ can be assigned at most one bin. If item $p$ is assigned to bin $l$, then $x_{lp}=1$. Otherwise, $x_{lp}=0$. (1.1e) guarantees that each bin can have at most one copy of each item. Similarly, $y_{l}=1$ indicates that bin $l$ is utilized. Items can only be matched to utilized bins.

For the rest of this paper, we define $k$ as the ratio of the budget to the largest line cost:

We will develop a randomized rounding algorithm based on the solution to the linear programming (LP) relaxation of (1.1). While a natural approach to relaxing (1.1) would be to directly set $x_{lp}$ and $y_{l}$ as continuous variables, this method yields a loose solution, as noted in [11] and [17], thereby limiting the performance of LP-based randomized rounding algorithms. Consequently, we will employ the LP relaxation (1.4) initially proposed by [11], augmented with an additional budget constraint.

Then the LP relaxation of (1.1) can be stated as follows:

When $X_{lS}$ is restricted to $\{0,1\}$, (1.4b) enforces that each bin can be matched with at most one feasible assignment. Constraints (1.4c) and (1.4d) correspond to (1.1d) and (1.1b) respectively. This LP relaxation can be solved in polynomial time using the ellipsoid method as in [11, 17].

The GBAP is a variant of separable assignment problem (SAP). In SAP, there are $L$ bins and $P$ items. For each item $p$ and bin $l$, there is a reward $v_{lp}$ generated when item $p$ is assigned to bin $l$. Moreover, for each bin $l$, there is a separate packing constraint, which means that only certain subsets of the items can be assigned to bin $l$ when the subset satisfies the constraint. The goal is to find an assignment of items to the bins such that all the sets of items assigned to bins do not violate packing constraints, each item is assigned to at most one bin, and the total reward of assignments is optimal. Fleisher et al. [11] propose a $\beta\left(1-\frac{1}{e}\right)$-approximation for SAP assuming that there is a $\beta$-approximation algorithm for the single bin subproblem. Moreover, they showed that a special case of SAP called the capacitated distributed caching problem (CapDC) cannot be approximated in polynomial time with an approximation factor better than $\left(1-\frac{1}{e}\right)$ unless NP$\subseteq$ DTIME$(n^{O(\log\log n)})$. In CapDC, there are $L$ cache locations (bins), $P$ requests (items) and $T$ different files. Bin $l$ has capacity $A_{l}$, and file $t$ has size $a_{t}$. Request $p$ is associated with some file $t_{p}$ and a value $R_{p}$. If a request $p$ is connected to cache location $l$, then there is a cost $c_{lp}$ and the reward is $R_{p}-c_{lp}$. The total size of the files corresponding to connected requests should be no larger than the capacity of the bin.

The maximum generalized assignment problem (GAP) is an important special case of SAP, in which each bin $l$ has size $A_{l}$, each item $p$ has size $a_{lp}$ in each bin $l$ and a feasible assignment means that the total size of assigned items for each bin is not larger than the bin’s capacity. GAP is proved to be APX- hard by Chekuri et al. [8]. The best known approximation algorithm for GAP is from [10] and achieves an approximation factor of $\left(1-\frac{1}{e}+\delta\right)$ for a small constant $\delta>0$.

Calinescu et al. [7] also give a $\left(\beta(1-\frac{1}{e})\right)$-approximation for SAP. Moreover, they give a $\left(1-\frac{1}{e}-\epsilon\right)$-approximation algorithm for GAP with the additional restriction of a budget constraint that on the number of bins that can be used. [14] propose a $\left(1-\frac{1}{e}-\epsilon\right)$-approximation method for GAP with knapsack constraints, where there is a multi-dimensional budget vector and each item has a multi-dimensional cost vector same for each bin. The total cost vector of assigned items in a feasible assignment is no larger than the budget vector entry-wise.

A generalization of SAP, which is called as $\rho$-SAP, is studied by Bender et al. [3] (it is called $k$-SAP by [3], where $k$ is the number of allowed bins there, but here we make it consistent with our notation to avoid confusion). In $\rho$-SAP each item can be assigned to at most $\rho$ different bins, but at most once to each bin. The goal is to find an assignment of items to bins that maximizes total reward. They present a $\beta\left(1-\frac{1}{e^{\rho}}\right)$-approximation algorithm for $\rho$-SAP under the assumption that there is a $\beta$-approximation algorithm for the single bin subproblem. If the single bin subproblem admits an FPTAS, then the approximation factor is $\left(1-\frac{1}{e^{\rho}}\right)$. The scheme can also be extended to the different upper bounds of number of allowed bins for different items: if the upper bound is $\rho_{i}$ for item $i$, and $\rho=\min_{i}\rho_{i}$, then their algorithm yields $\beta\left(1-\frac{1}{e^{\rho}}\right)$ approximation.

None of the aforementioned studies are applicable to scenarios that include budget constraints on bins.

In Périvier et al.’s study [17], the focus is on the Real-Time Line Planning Problem (RLPP), which can be modeled as GBAP. In this problem setting, each passenger is restricted to selecting a single subroute per line, and there is no cost associated with allocating passengers to these lines. To tackle the RLPP, the authors propose a randomized rounding algorithm, building upon the scheme initially introduced by Fleischer et al. [11]. This algorithm yields a $1-\frac{1}{e}-\epsilon$-approximate solution, with the probability of exceeding the budget constraint capped at $e^{-\frac{k}{3}\epsilon^{2}}$. Here, $k=\frac{B}{\max_{l\in[L]}c_{l}}$, where $B$ represents the budget, $c_{l}$ is the cost associated with line $l$, and $L$ is the set of all lines. For a comprehensive discussion and additional related works in the domain of line planning, please see Section 6.

GAP in an online setting has also been studied by Alaei et al. [2]. They propose a $\left(1-\frac{1}{\sqrt{k}}\right)$-competitive algorithm under the assumption that no item takes up more than $\frac{1}{k}$ fraction of the capacity of any bin. In the setting of [2], items arrive in an online manner; upon arrival, an item can be assigned to a bin or discarded; the objective is to maximize the total reward of the assignment. The size of an item is revealed only after it has been assigned to a bin; the distribution of each item’s reward and size is known in advance. The online algorithm is developed based on a generalization of the magician’s problem in [1], where it is used to assign a set of items with limited supply to a set of buyers in order to maximize the expected value of revenue or welfare.

Our objective is to devise an algorithm that maintains a constant approximation ratio while being practically efficient. Balancing theoretical rigor with practical efficiency poses a significant challenge. Moreover, conventional approaches fail to yield a constant approximation ratio for our specific problem while meeting all practical constraints.

Firstly, while our problem shares similarities with the capacitated facility location problem (CFLP), for which [20] provides a $1-\frac{1}{e}$ approximation algorithm based on the CFLP’s submodular structure, our problem lacks this submodular property [17, Proposition 4.10]. Consequently, methods aimed at maximizing submodular functions, as seen in works like [15, 13, 9], are not applicable to our context. This necessitates the development of innovative approaches tailored to the unique challenges discussed in this paper.

Secondly, the classical LP-based randomized rounding algorithms, proposed by [11, 17], while simple, can have a non-trivial probability to produce solutions that violate the budget constraint. More specifically, the approach in [17], an adaptation of the method from [11], attempts to mitigate this by scaling down the LP solutions to manage the probability of budget constraint violations. While this method achieves a $1-\frac{1}{e}-\epsilon$-approximate solution, there remains a non-negligible probability, bounded by $e^{-\frac{k}{3}\epsilon^{2}}$, that the budget constraints may still be breached. This probability fails to guarantee a constant approximation ratio of feasible solutions and can exceed $\frac{1}{2}$ even when $k$ is as large as $\frac{1}{\epsilon^{2}}$.

To control this probability of violation, one might consider setting $\epsilon$ to a relatively high value. However, this adjustment would negatively impact the solution quality, a dilemma extensively discussed in Remark 6.1, which provides a detailed analysis and additional insights into this trade-off.

In summary, classical randomized rounding struggles to manage budget constraints and ensure that each item is assigned to at most one bin while still achieving a constant approximation ratio, especially when the algorithm must be computationally efficient to handle large-scale problems.

We introduce a randomized approximation algorithm that is not only practically efficient but also maintains a constant approximation ratio. Our numerical experiments, conducted using real-world data, also outperform the previous work.

Our preliminary major findings were initially presented as an extended abstract at COCOON [12]. It featured randomized approximation algorithms but lacked formal proofs and did not offer a constant approximation ratio. In this extended work, we have refined our algorithm to achieve a constant approximation ratio.

In Section 5, we introduce our randomized approximation algorithm for solving GBAP, which achieves a constant approximation ratio. Specifically, our algorithm achieves an approximation ratio of $\frac{1}{8}$ for $k<3$, and $\frac{k-1}{2k}\cdot\left(1-\frac{1}{\sqrt{k}}\right)>\frac{1}{8}$ for $k\geq 3$, where $k$ is defined in (1.2). To the best of our knowledge, this is the first algorithm to achieve a constant approximation ratio for GBAP.

Our analysis leverages two online optimization mechanisms detailed in Section 4. The study of online knapsack problems in Section 4.2 may be of independent interest. Furthermore, to overcome the limitations of classical randomized rounding, which struggles to simultaneously satisfy multiple constraints, we introduce a novel approach. Our method utilizes the realizations from randomized rounding to simulate two distinct online mechanisms. This innovative technique enables us to produce solutions that concurrently satisfy different constraints while maintaining theoretical guarantees. Furthermore, this method offers new insights into algorithm design for related complex optimization problems.

In Section 6, we apply our GBAP approximation algorithms to the RLPP . Using real-world data from New York City, we conduct numerical experiments that demonstrate improvements over previous approaches. These results highlight the practical significance of our algorithms in addressing complex transportation challenges.

Note that $W_{1}=0$ with probability $1$, and therefore $\theta_{1}=0$. Then the CDF of $W_{i+1}$ and $\theta_{i+1}$ can be computed based on $W_{i}$ and $\theta_{i}$ in with dynamic programming. For more details, please see [1, Section 7].

One observation is that $S_{i}$ is independent to $X_{i}$ for all $i$.