# Solving Multi-Document Summarization as an Orienteering Problem
## 5 The Proposed Solution
### Selecting Summary Sentences
#### 5.4.4. ACS for OP  
An ACS algorithm is proposed to approximate a solution to an OP instance. The original ACS algorithm was proposed by [PERSON] and [PERSON] [5] for the TSP. The main steps of the proposed ACS algorithm for the OP are outlined by Algorithm 3. Specifically, due to the time constraint, each ant could terminate its path and become inactive at different times based on the vertices (i.e., sentences) it includes in its solution (i.e., path). A set, called _active_set_, is used to keep track of the active ants, which are the ants whose own traveled time does not reach the time budget (i.e., max summary length), and thus can move further to another vertex and complete its solution. In addition, to maximize the coverage objective, the content score of each sentence (i.e., the profit of each vertex) is dynamic. This means that the coverage objective is updated at each cycle based on the last vertex that joins the path. Therefore, each ant has its own graph to keep track of the current profits values of the graph vertices. To satisfy the time constraint by ants, each \(ant_{k}\) has its own time \(T_{k}\). The path of \(ant_{k}\) is stored in the path \(P_{k}\). Moreover, each \(ant_{k}\) keeps track of the set of vertices \(J_{k}\) that have not yet been visited. ```
1:Input:\(OP(T_{max},V,A)\): an OP instance
2:\(T_{max}\): the time budget
3:\(V\): the set of graph vertices (\(N=|V|\))
4:\(A\): the set of arcs between vertex pairs
5:\(I\): the number of iterations
6:\(\tau_{0}\): The initial pheromone level
7:Output:\(P_{best}\): a solution (i.e., path) to the input OP instance. 8:\(L_{best\_so\_far}\gets 0\)\(\vartriangle\) Initialize the content score of the best path found so far
9:\(P_{best\_so\_far}\leftarrow\varnothing\)\(\vartriangle\) Initialize the best path found so far
10:while\(I\
eq 0\)do
11:\(I\gets I-1\)
12:\(\vartriangle\) Starting the initialization step
13:for each arc \(a_{ij}\) in \(A\)do
14:\(\tau_{ij}\leftarrow\tau_{0}\)\(\vartriangle\) Set the initial pheromone level of arc \(a_{ij}\)
15:endfor
16:\(active\_ant\leftarrow\varnothing\)
17:for each \(ant_{k}\)do\(\vartriangle\) Initialize each ant
18:\(P_{k}\leftarrow\varnothing\)
19:\(T_{k}\gets T_{max}\)
20:if\((t_{1(k+1)}+t_{(k+1)N})\leq T_{max}\)then\(\vartriangle\) Check the time budget constraint
21:\(active\_ant\leftarrow\)\(active\_ant+ant_{k}\)
22:\(P_{k}\gets P_{k}+v_{r_{1}}\)\(\vartriangle\) Append the first vertex to the path
23:\(r_{k1}\gets k+1\)\(\vartriangle\)\(\vartriangle\)\(r_{k1}\) is the second vertex for \(ant_{k}\)
24:\(P_{k}\gets P_{k}+v_{r_{k1}}\)
25:\(T_{k}\gets T_{k}-t_{1r_{k}}\)
26:\(r_{k}\gets r_{k1}\)\(\vartriangle\) The vertex \(r_{k}\) is current location of \(ant_{k}\)
27:\(J_{k}(r_{k1})\leftarrow\{1,\ldots,n\}-r_{k1}-1-N\)\(\vartriangle J_{k}(r_{k1})\) is the set of vertices that can be visited by \(ant_{k}\) at vertex \(r_{k1}\) in addition to \(v_{N}\)
28:endif
29:endfor
30:\(\vartriangle\) Building the paths of ants
31:while\(active\_ant\
eq\varnothing\)do
32:for each \(ant_{k}\) in \(active\_ant\)do
33: Choose the next vertex \(v_{d_{k}}\) for \(ant_{k}\) according to Equation (7) and Equation (8)
34:if\(v_{d_{k}}\) is not exist then\(\vartriangle\) Can't add any vertex and satisfy the time constraint \(T_{k}\) or \(ant_{k}\)

passed through all the vertices
35:\(active\_ant\gets active\_ant-ant_{k}\)
36:else
37:\(J_{k}(d_{k})\gets J_{k}(r_{k})-d_{k}\)
38:\(P_{k}\gets P_{k}+v_{d_{k}}\)
39:\(T_{k}\gets T_{k}-t_{r_{k}d_{k}}\)\(\vartriangle\) Subtract the traveled time to reach \(v_{d_{k}}\)
40:endif
41:endfor
42:\(\vartriangle\) Pheromone local updating using Equation (10)
```  
**Algorithm 3** Approximating an OP solution using ACS.