Supplementary material for the paper:

On the Invariance of Ant Colony Optimization

Mauro Birattari, Paola Pellegrini, and Marco Dorigo
mbiro@ulb.ac.be; paolap@pellegrini.it; mdorigo@ulb.ac.be


The following information is extracted from: P. Pellegrini and M. Birattari (2006) Some combinatorial optimization problems on which ant colony optimization is invariant. Technical Report TR/IRIDIA/2006-026, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.

Traveling salesman problem

The traveling salesman problem (TSP) consists in finding a Hamiltonian circuit of minimum cost on an edge-weighted graph $ G=(N,E)$. Let $ N$ be the set of nodes, and $ E$ be the set of edges. If a directed graph is considered, the problem is known as the asymmetric traveling salesman problem (1).

Let $ x_{ij}(s)$ be a binary variable taking value 1 if edge $ \langle i,j\rangle $ is included in tour $ s$, and 0 otherwise. Let $ c_{ij}$ be the cost associated to edge $ \langle i,j\rangle $. The goal is to find a tour $ s$ such that the function

$\displaystyle f(s)= \sum_{i \in N}\sum_{j \in N} c_{ij} x_{ij}(s)$    

is minimized.
Transformation of units:
If the cost of all edges is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$. Indeed, $ \Bar{c}_{ij}=\zeta c_{ij}$, for all $ \langle i,j\rangle $ $ \implies \Bar{f}(s)=\zeta f(s)$, for all $ s$.
Reference solution:
Many constructive heuristics exist for the TSP (2) that can be conveniently adopted here.
Heuristic information:
The typical setting is $ \eta_{ij}=1/c_{ij}$, for all $ \langle i,j\rangle $. This meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold. In the literature, the three variants of ant colony optimization considered in this paper have been applied to the traveling salesman problem with the setup just described (3).
Strongly-invariant heuristic information:
Let $ \eta_{ij}=f(s_{0})/nc_{ij}$, for all $ \langle i,j\rangle $, where $ n=\vert N\vert$. It is worth noting that the term $ n$ is not needed for the invariance to transformation of units. It has been included for achieving another property: the above defined $ \eta_{ij}$ does not depend on the size of the instance under analysis--that is, on the number $ n$ of cities. This definition meets Condition 2 with $ \lambda =f(s_{0})/n$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Vehicle routing problem

In the vehicle routing problem (VRP) $ n$ customers have to be served starting from one central depot (which is indexed 0). Each customer $ i$ has a non-negative demand $ d_i$ of the same good, and for each pair of customers $ \langle i,j\rangle $ a travel time $ c_{ij}$ between the two customers is given. The customers are served by a fleet of vehicles of equal capacity. The objective is to find a set of routes that minimizes the total travel time, such that: each customer is served once by exactly one vehicle; the route of each vehicle starts and ends at the depot; and the total demand covered by each vehicle does not exceed its capacity. Using the notation introduced for the traveling salesman problem, the objective function can be written as:

$\displaystyle f(s)= \sum_{i \in N}\sum_{j \in N} c_{ij} x_{ij}(s).$    

Variants of the problem may have different goals, as for example the minimization of the number of vehicles used (4).

Transformation of units:
If the cost of all edges is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$. Indeed, $ \Bar{c}_{ij}=\zeta c_{ij}$, for all $ \langle i,j\rangle $ $ \implies \Bar{f}(s)=\zeta f(s)$, for all $ s$.
Reference solution:
Many constructive heuristics exist for the VRP (4) that can be conveniently adopted here.
Heuristic information:
Let $ \eta_{ij}=\mathcal{s}_{ij}$ (5), with $ \mathcal{s}_{ij}$ measure of the cost saving that would be achievable by using edge $ \langle i,j\rangle $ (6): We first consider a solution with one separate tour per customer, i.e. tours starting and ending at the depot and touching only one customer each. Then, for each pair $ \langle i,j\rangle $ of customers, a saving $ \mathcal{s}_{ij}= c_{i0}+c_{0j}-c_{ij}$ is computed. This meets Condition 1 with $ g_2=\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold. In the literature, variants of the VRP have been tacked with ACO algorithm. Limiting this survey to the standard version, let us cite, among the others, Bullnheimer et al. (5); Reimann et al. (7).
Strongly-invariant heuristic information:
Let $ \eta_{ij}=n\mathcal{s}_{ij}/f(s_{0})$, for all $ \langle i,j\rangle $, where $ n=\vert N\vert$. As in the case of the traveling salesman problem, the term $ n$ is not needed for the invariance to transformation of units. It has been included for achieving another property: the above defined $ \eta_{ij}$ does not depend on the size of the instance under analysis--that is, on the number $ n$ of cities. This definition meets Condition 2 with $ \lambda =n/f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Sequential ordering problem

The sequential ordering problem (SOP) consists in finding a minimum weight hamiltonian path on a directed graph with weights on edges and nodes, subject to precedence constraints (8). It is often tackled as a constrained version of the asymmetric traveling salesman problem, by associating to each edge $ \langle i,j\rangle $ a cost $ c_{ij}^{\prime}$:

$\displaystyle c_{ij}^{\prime}=\left\{\begin{array}{ll}\infty&\mbox{ if node }j\mbox{ has to precede node }i,\\ c_{ij}+p_j&\mbox{ otherwise,}\end{array}\right.$    

where $ c_{ij}$ is the weight of edge $ \langle i,j\rangle $, and $ p_j$ is the weight of node $ j$. With this feature the objective function can be expressed as

$\displaystyle f(s)= \sum_{i \in N}\sum_{j \in N} c_{ij}^{\prime} x_{ij}(s)$    

using the notation introduced for the TSP.
Transformation of units:
If the cost of both edges and nodes is multiplied by a constant $ \zeta$, then the cost $ c_{ij}^{\prime}$ is scaled by the same constant $ \zeta$, for all $ \langle i,j\rangle $. The resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$. Indeed, $ \Bar{c}_{ij}^{\prime}=\zeta c_{ij}^{\prime}$, for all $ \langle i,j\rangle $ $ \implies \Bar{f}(s)=\zeta f(s)$, for all $ s$.
Reference solution:
For the construction of a reference solution, one of the heuristics available for the TSP (2) can be conveniently adopted.
Heuristic information:
The typical setting is $ \eta_{ij}=1/c_{ij}^{\prime}$, for all $ \langle i,j\rangle $. This meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold. One of the best algorithms available in the literature for the sequential ordering problem is the hybrid ant colony system proposed by Gambardella and Dorigo (9), where the authors use this invariant setup.
Strongly-invariant heuristic information:
Let $ \eta_{ij}=f(s_{0})/nc_{ij}^{\prime}$, for all $ \langle i,j\rangle $, where $ n=\vert N\vert$. This definition meets Condition 2 with $ \lambda =f(s_{0})/n$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Quadratic assignment problem

In the quadratic assignment problem (QAP), $ n$ facilities and $ n$ locations are given, together with two $ n\times n$ matrices $ A=[a_{uv}]$ and $ B=[b_{ij}]$, where $ a_{uv}$ is the distance between locations $ u$ and $ v$, and $ b_{ij}$ is the flow between facilities $ i$ and $ j$. A solution $ s$ is an assignment of each facility to a location. Let $ x_i(s)$ denote the location to which facility $ i$ is assigned. The goal is to find an assignment that minimizes the function:

$\displaystyle f(s)= \sum_{i=1}^n \sum_{j=1}^n b_{ij} a_{x_i(s) x_j(s)}.$    

Transformation of units:
If all distance are multiplied by a constant $ \zeta_1$ and all flows by a constant $ \zeta_2$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta_1\zeta_2$.
Reference solution:
The construction of the reference solution is typically stochastic: a number of solutions are randomly generated and improved through a local search. The best solution obtained is adopted as the reference solution (10). It is worth noting that a local search is an invariant algorithm.
Heuristic information:
Often, the heuristic information is not adopted (10), that is, $ \beta=0$. In this case, Condition 1 is trivially met. Some authors (11,12) set $ \eta_{ij}=1/\sum_{l=1}^n a_{il}$. This meets Condition 1 with $ g_2=1/\zeta_1$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
If the heuristic information is adopted, $ \eta_{ij}=f(s_{0})/\sum_{l=1}^n a_{il}$, for all $ \langle i,j\rangle $. This meets Condition 2 with $ \lambda =f(s_{0})$, and Condition 3. On the other hand, if no heuristic information is adopted as suggested in (10), Conditions 2 and 3 are trivially met.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Generalized assignment problem

In the generalized assignment problem (GAP), a set of tasks $ I$ has to be assigned to a set of agents $ J$ in such a way that a cost function is minimized. Each agent $ j$ has only a limited capacity $ a_j$, and each task $ i$ consumes, when assigned to agent $ j$, a quantity $ b_{ij}$ of the agent's capacity. Moreover, a cost $ c_{ij}$ of assigning task $ i$ to agent $ j$ is given. The objective is to find a feasible task assignment $ s$ that minimizes

$\displaystyle f(s)=\sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij}(s),$    with $\displaystyle \sum_{i \in I} b_{ij}x_{ij}(s) \leq a_j, \forall j \in J.$    

$ x_{ij}(s)$ is equal to 1 if task $ i$ is assigned to agent $ j$ in $ s$, and 0 otherwise.
Transformation of units:
If the cost of assigning each task $ i$ to each agent $ j$ is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$.
Reference solution:
The construction of the reference solution is typically stochastic.
Heuristic information:
The typical setting is $ \eta_{ij}=1/c_{ij}$, for all $ \langle i,j\rangle $ (13). This meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
Let $ \eta_{ij}=f(s_{0})/nc_{ij}$, for all $ \langle i,j\rangle $, where $ n=\vert N\vert$. This definition meets Condition 2 with $ \lambda =f(s_{0})/n$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Single machine total weighted tardiness scheduling problem

In the single machine total weighted tardiness scheduling problem (SMTWTP) (14), $ n$ jobs are to be processed sequentially on a single machine, without interruption. Each job $ j$ has an associated processing time $ p_j$, a weight $ w_j$, and a due date $ d_j$. All jobs are available for processing at time zero. The tardiness of job $ j$ is defined as $ t_j(s)=\max \{0, c_j(s) - d_j\}$, where $ c_j(s)$ is its completion time in the current job sequence $ s$. The objective is to find the sequence $ s$ that minimizes the sum of the weighted tardiness:

$\displaystyle f(s)= \sum_{j=1}^n w_j t_j(s).$    

Transformation of units:
If, for all the jobs, both the processing time and the due date are multiplied by a constant $ \zeta_1$, and the weight is multiplied by a constant $ \zeta_2$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta_1\zeta_2$.
Reference solution:
A heuristic based on the apparent urgency (15) is typically used for the construction of the reference solution. In this approach, jobs are arranged in the descending order of their apparent urgency priorities:

$\displaystyle AU_j=\frac{w_j}{p_j} \exp{\left(\frac{-max\{0,d_j-t-p_j\}}{k\hat{p}}\right)},$   for all $\displaystyle j.$    

Here, $ k$ is called the look-ahead parameter and is set according to the tightness of the due date; $ \hat{p}$ the average processing time; $ t$ is the current time. As it can be seen, the selection criterion is invariant to transformation of units.
Heuristic information:
The typical setting is $ \eta_{ij}=1/d_{ij}$, for all $ \langle i,j\rangle $. This meets Condition 1 with $ g_2=1/\zeta_1$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold. In the literature, den Besten et al. (16) apply ant colony system to SMTWTP. In the analysis, the authors define various priority rules, which imply various heuristic measures. Among them the one previously described is considered.
Strongly-invariant heuristic information:
Let $ \eta_{ij}=\sum_{j=1}^n t_j(s_{0})/d_{ij}$, for all $ \langle i,j\rangle $. This definition meets Condition 2 with $ \lambda =\sum_{j=1}^n t_j(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Open shop scheduling problem

In open shop scheduling problems (OSP) (17), a finite set $ \mathcal{O}$ of operations is given, which is partitioned into a collection of subsets $ \mathcal{M}=\{M_1,M_2,\dots,M_U\}$ and a collection of subsets $ \mathcal{J}=\{J_1,J_2,\dots,J_V\}$. Each $ M_u$ is the set of operations that have to be performed by machine $ u$; and each $ J_v$ is the set of operations belonging to job $ v$. A non-negative processing time $ t(o_j)$ and the earliest possible starting time $ e(o_j)$ are associated with operation $ o_j\in\mathcal{O}$. A solution $ s$ is a collection of schedules $ \mathcal{X}(s)=\{X^1(s),X^2(s),\dots,X^U(s)\}$, where $ X^u(s)$ is the sequence of operations scheduled for machine $ u$ and $ X^u_r(s)$ is the operation in position $ r$ in sequence $ X^u(s)$. The completion time $ c^u_r(s)$ of operation $ X^u_r(s)$ is computed recursively from $ c^u_{r'}(s)=t\big(X^u_{r'}(s)\big)+ \max\big[e\big(X^u_{r'}(s)\big),c^u_{r'-1}(s)\big]$, with $ c^u_{0}(s)=0$. The goal is to minimize the makespan, which is given by:

$\displaystyle f(s)= \max_{u} c^u_{\,\vert\!M_u\!\vert}(s).$    

Transformation of units:
If all processing times and earliest possible starting times are multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$.
Reference solution:
The construction of the reference solution is typically stochastic.
Heuristic information:
The heuristic information is $ \eta_{ij}=1/e(o_j)$, for all $ \langle i,j\rangle $, which meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
The heuristic information is $ \eta_{ij}=f(s_{0})/e(o_j)$, for all $ \langle i,j\rangle $. This meets Condition 2 with $ \lambda =f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Permutation flow shop scheduling problem

In the Permutation flow shop scheduling problem (PFSP), $ J$ jobs are to be processed. A set $ I$ of machines is available. Each job $ j$ is partitioned in a set of operations $ O_j=\{o_{1j},o_{2j},\cdots,o_{Ij}\}$, where operation $ o_{ij}$ is to be processed on machine $ i$. To each operation $ o_{ij}$ a processing time $ t(i,j)$ is associated. It may be equal to 0 if job $ j$ is not to be processed on machine $ i$. Let $ x_r(s)$ be the $ r$-th job scheduled in sequence $ s$. The completion time $ c^u_r(s)$ of operation $ o_{u x_r(s)}$ on machine $ u$ is computed recursively from $ c^u_{r'}(s)=t\big(u,o_{u x_{r'}(s)}\big)+ c^u_{r'-1}(s)$, with $ c^u_{0}(s)=0$.

The goal is to minimize the makespan:

$\displaystyle f(s)= \max_{u} c^u_{\,\vert\!J\!\vert}(s).$    

Transformation of units:
If the processing time is multiplied by a constant $ \zeta$ for all the jobs, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$.
Reference solution:
The NEH heuristic (15) is typically used for the construction of the reference solution. In this approach, first the jobs are ordered by decreasing sums of total job processing times on the machines. Then, the first two jobs are scheduled so as to minimize the partial makespan as if there were only two jobs. Finally, for all the following ones, insert one job at a time in the partial schedule, into the location which minimizes the partial makespan. As it can be seen, the selection criterion is invariant to transformation of units.
Heuristic information:
Typically, the heuristic information is not adopted (18), that is, $ \beta=0$. In this case, Condition 1 is trivially met.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
As for the case seen in 3, if no heuristic information is adopted as suggested by Stützle (18), Conditions 2 and 3 are trivially met.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Set covering problem

In the set covering problem (SCP) (19), $ u\times v$ matrix $ A=[a_{ij}]$ is given. All the matrix element are either 0 or 1. Additionally, each column is given a non-negative cost $ c_{j}$. We say that a column $ j$ covers a row $ i$ if $ a_{ij}=1$. A solution $ s$ is represented by a subset of columns that covers every row. Let $ x_j(s)$ be a binary variable which is 1 if column $ j$ is included in $ s$, and 0 otherwise. The goal is finding a solution of minimal cost. The objective function is:

$\displaystyle f(s)= \sum_{j=1}^v c_{j} x_j(s).$    

Transformation of units:
If the cost of all columns is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$.
Reference solution:
The construction of the reference solution is typically stochastic.
Heuristic information:
Let $ \eta_{j}= e_j/c_{j}$, where $ e_j$ is the cover value of column $ j$, that is, the number of additional rows covered when adding column $ j$ to the current partial solution. This meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold. Ant system is applied to the set covering problem by Leguizamón and Michalewicz (20); Hadji et al. (21), using the invariant framework.
Strongly-invariant heuristic information:
Let $ \eta_{j}= f(s_{0})e_j/c_{j}$. This meets Condition 2 with $ \lambda =f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Arc-weighted k-cardinality tree problem

The arc-weighted $ k$-cardinality tree problem (KCT) is a generalization of the minimum spanning tree problem. It consists in finding a subtree with exactly $ k$ arcs in a graph with arc weights, such that the sum of the weights is minimal (22).

More formally, the KCT problem can be defined as follows. Let $ G=(N,E)$ be a graph. A weight $ c_{ij}$ is assigned to each edge $ \langle i,j\rangle $. A solution $ s$ is a $ k$-cardinality tree in $ G$. Let $ x_{ij}(s)$ be a binary variable which is 1 if edge $ \langle i,j\rangle $ is included in $ s$, and 0 otherwise. Then, the edge-weighted problem $ (G, c_{} , k)$ consists of finding a solution $ s$ that minimizes the objective function:

$\displaystyle f(s)= \sum_{\langle i,j\rangle \in E}c_{ij} x_{ij}(s).$    

Transformation of units:
If the weight of all edges is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$. Indeed, $ \Bar{c}_{ij}=\zeta c_{ij}$, for all $ j$ $ \implies \Bar{f}(s)=\zeta f(s)$, for all $ s$.
Reference solution:
The construction of the reference solution is typically stochastic.
Heuristic information:
The heuristic information typically used (23) is $ \eta_{ij}=1/c_{ij}$. This meets Condition 1 with $ g_2=1/\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
Let $ \eta_{ij}= f(s_{0})/c_{ij}$. This meets Condition 2 with $ \lambda =f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Multiple knapsack problem

In the multiple knapsack problem (MKP), a set $ I$ of items and a set $ J$ of resources are given. A profit $ p_i$ and a requirement $ r_{ij}$ of resource $ j\in J$ are assigned to each item $ i \in I$. A set of constraints is given as a limit $ a_j$ on each resource $ j$ (24). A solution $ s$ is a subset of items that meets all the constraints. The goal is to find a solution that maximizes the total profit. The objective function can be formulate as:

$\displaystyle f(s)= \sum_{i \in I}p_{i} x_i(s),$    with $\displaystyle \sum_{i \in I} r_{ij} x_i(s) \leq a_j, \forall j \in J.$    

$ x_i(s)$ is a binary variable which is 1 if $ i\in s$, and 0 otherwise.
Transformation of units:
If the profit associated to each item is multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=\zeta$.
Reference solution:
The construction of the reference solution is typically stochastic.
Heuristic information:
Let $ s_k(t)$ be the partial solution of ant $ k$ at construction step $ t$, and $ v_j(k,t)=a_j-\sum_{z \in s_k(t)}r_{zj}$ be the remaining amount of resource $ j$. The tightness of component $ i$ with respect to resource $ j$ is defined as: $ w_{ij}(k,t)=r_{ij}/v_j(k,t)$. Finally the average tightness of all constraints with respect to component $ i$ is computed as $ aw_i(k,t)=\sum_{j \in R}w_{ij}(k,t)/l$, where $ l$ is the number of resource constraints. Let $ \eta_{i}(s_k(t))= p_i/aw_i(k,t)$ (25). This definition meets Condition 1 with $ g_2=\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
Let $ \eta_{i}(s_k(t))= p_i/\left(aw_i(k,t)f(s_{0})\right)$. This meets Condition 2 with $ \lambda =1/f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Bin packing problem

In the bin packing problem (BPP), a set $ J$ of bins of fixed capacity $ W$ and a set $ I$ of items are given. A fixed weight $ w_i$, $ 0<w_i < W$ is associated to each item $ i$ (26). A solution $ s$ is an assignment of the items to bins such that the capacity of the bins is not violated. The goal is to pack the items in as few bins as possible. More formally, let $ x_{ij}(s)$ be a binary variable which is 1 if item $ i$ is inserted in bin $ j$ in solution $ s$, and 0 otherwise. Let $ y_{j}(s)$ be a binary variable which is 1 if bin $ j$ is used is solution $ s$, that is, if $ \sum_{i \in I} x_{ij}(s) >0$; and 0 otherwise. The function to be minimized is:

$\displaystyle f(s)=\sum_{j \in J} y_j(s),$    with $\displaystyle \sum_{i \in I} w_i x_{ij}(s) < W, \forall j \in J.$    

Transformation of units:
If the capacity of the bins and the weight of all the items are multiplied by a constant $ \zeta$, the resulting instance $ \Bar{I}$ is equivalent to the original $ I$, that is, $ \Bar{I}=g_1I$, with $ g_1=1$.
Reference solution:
The construction of the reference solution is typically done using the best fit decreasing heuristic. In this approach, first the items are ordered by decreasing weight. Then, each of them is assigned to the bin which will have the least amount of space left, after accommodating the item. As it can be seen, the selection criterion is invariant to transformation of units.
Heuristic information:
The heuristic information is typically defined as $ \eta_{ij}=1/w_i$ (27). This meets Condition 1 with $ g_2=\zeta$.
Therefore, the theorems on the weak invariance of ant system, $ \cal M\mspace{-2mu}AX\!$- $ \cal \!MI\mspace{-1mu}N\!$ ant system, and ant colony system hold.
Strongly-invariant heuristic information:
Let $ \eta_{ij}=f(s_{0})/w_i$. This meets Condition 2 with $ \lambda =1/f(s_{0})$, and Condition 3.
Therefore, si AS , si $ \mathcal{M\mspace{-2mu}M}$AS , and si ACS are indeed strongly invariant and are functionally equivalent to their original counterparts.

Bibliography

1
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys.
The Travelling Salesman Problem.
John Wiley & Sons, Chichester, United Kingdom, 1985.

2
D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis II.
An analysis of several heuristics for the traveling salesman problem.
SIAM Journal on Computing, 6 (5): 563-581, 1977.

3
M. Dorigo and T. Stützle.
Ant Colony Optimization.
MIT Press, Cambridge, MA, USA, 2004.

4
P. Toth and D. Vigo, editors.
The Vehicle Routing Problem.
SIAM, Philadelphia, PA, USA, 2002.

5
B. Bullnheimer, R.F. Hartl, and C. Strauss.
An improved ant system for the vehicle routing problem.
Annals of Operations Research, 89: 319-328, 1999.

6
G. Clarke and J.W. Wright.
Scheduling of vehicles from a central depot to a number of delivery points.
Operations Research, 12: 568-581, 1964.

7
M. Reimann, M. Stummer, and K. Doerner.
A saving based ant system for the vehicle routing problem.
In W.B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M.A. Potter, A.C. Schultz, J.F. Miller, E. Burke, and N. Jonoska, editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 1317-1325, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers.

8
L.F. Escudero.
An inexact algorithm for the sequential ordering problem.
European Journal of Operational Research, 37: 232-253, 1988.

9
L.M. Gambardella and M. Dorigo.
Ant colony system hybridized with a new local search for the sequential ordering problem.
INFORMS Journal on Computing, 12 (3): 237-255, 2000.

10
T. Stützle and M. Dorigo.
ACO algorithms for the quadratic assignment problem.
In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 3-50. McGraw-Hill, New York, NY, USA, 1999.

11
V. Maniezzo, A. Colorni, and M. Dorigo.
The ant system applied to the quadratic assignment problem.
Technical Report TR/IRIDIA/1994-28, IRIDIA, Université Libre de Bruxelles, Brussels, Belgium, 1994.

12
V. Maniezzo and A. Colorni.
The ant system applied to the quadratic assignment problem.
IEEE Transactions on Data and Knowledge Engineering, 11 (5): 769-778, 1999.

13
H.Lourenço and D. Serra.
Adaptive search heuristics for the generalized assignment problem.
Mathware and Soft Computing, 9: 209-234, 2002.

14
H.A.J. Crauwels, C.N. Potts, and L.N. Van Wassenhove.
Local search heuristics for the single machine total weighted tardiness scheduling problem.
INFORMS Journal on Computing, 10 (3): 341-350, 1998.

15
T.E. Morton, R.M. Rachamadugu, and A.Vepsalainen.
Accurate myopic heuristis for tardiness scheduling.
Technical Report 36-83-84, Carnegie Mellon, Pittsburgh, PA, USA, 1984.

16
M. den Besten, T. Stützle, and M. Dorigo.
Ant colony optimization for the total weighted tardiness problem.
In M. Schoenauer, K. Deb, G. Rudolf, X. Yao, E. Lutton, J.J. Merelo, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature, 6th International Conference, PPSN VI, pages 1111-1118, Berlin, Germany, 2000. Springer Verlag.

17
L. Chung-Yee and L. Lei.
Scheduling: theory and applications.
Baltzer Science Publishers, Amsterdam, The Netherlands, 1997.

18
T. Stützle.
An ant approach to the flow shop problem.
In EUFIT'98: The 6th European Congress on Intelligent Techniques and Soft Computing, Abstract Booklet with CD Rom, pages 1560-1564, Aachen, Germany, 1998. Verlag Mainz.

19
A. Caprara, P. Toth, and M. Fischetti.
Algorithms for the set covering problme.
Annals of Operations Research, 89: 353-371, 2000.

20
G. Leguizamón and Z. Michalewicz.
Ant system for subset problems.
Unpublished, 2000.

21
R. Hadji, M. Rahoual, E. Talbi, and V. Bachelet.
Ant colony for the set covering problem.
In M. Dorigo, M. Middendorf, and T. Stützle, editors, Proceedings of ANTS 2000--From Ant Colonies to Artificial Ants: 2nd International Workshop on Ant Algorithms, pages 63-66, Berlin, Germany, 2000. Springer Verlag.

22
H.W. Hamacher, K. Jørnsten, and F. Maffioli.
Weighted $ k$-cardinality trees.
Technical Report 23, Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy, 1991.

23
C. Blum and M.J. Blesa.
New metaheuristic approaches for the edge-weighted $ k$-cardinality tree problem.
Computers & Operations Research, 32 (6): 1355-1377, 2005.

24
C.E. Ferreira, A. Martin, and R. Weismantel.
Solving multiple knapsac problems by cutting planes.
SIAM Journal on Optimization, 6 (3): 858-877, 1996.

25
G. Leguizamón and Z. Michalewicz.
A new version of ant system for subset problems.
In P.J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Congress on Evolutionary Computation (CEC'99), pages 1459-1464, Piscataway, NJ, USA, 1999. IEEE Press.

26
E.G. Coffman Jr., M.R. Garey, and D.S. Johnson.
Approximation algorithms for bin-packing: An updated survey.
In G. Ausiello, M. Lucertini, and P. Serafini, editors, Algorithm Design for Computer Systems Design, pages 49-106. Springer Verlag, Berlin, Germany, 1984.

27
J. Levine and F. Ducatelle.
Ant colony optimization and local search for bin packing and cutting stock problems.
Journal of the Operational Research Society, 55 (7): 705-716, 2004.