A linear programming based heuristic framework for min-max
regret combinatorial optimization problems with interval costs
Lucas Assunçãoa,∗, Thiago F. Noronhab, Andréa Cynthia Santosc , Rafael Andraded

arXiv:1609.09179v1 [] 29 Sep 2016

a

Departamento de Engenharia de Produção, Universidade Federal de Minas Gerais
Avenida Antônio Carlos 6627, CEP 31270-901, Belo Horizonte, MG, Brazil
b Departamento de Ciência da Computação, Universidade Federal de Minas Gerais
Avenida Antônio Carlos 6627, CEP 31270-901, Belo Horizonte, MG, Brazil
c ICD-LOSI, UMR CNRS 6281, Université de Technologie de Troyes
12, rue Marie Curie, CS 42060, 10004, Troyes CEDEX, France
d
Departamento de Estatı́stica e Matemática Aplicada, Universidade Federal do Ceará
Campus do Pici - Bloco 910, 60455-900, Fortaleza, CE, Brazil

Abstract
This work deals with a class of problems under interval data uncertainty, namely interval robusthard problems, composed of interval data min-max regret generalizations of classical NP-hard
combinatorial problems modeled as 0-1 integer linear programming problems. These problems
are more challenging than other interval data min-max regret problems, as solely computing the
cost of any feasible solution requires solving an instance of an NP-hard problem. The state-ofthe-art exact algorithms in the literature are based on the generation of a possibly exponential
number of cuts. As each cut separation involves the resolution of an NP-hard classical optimization problem, the size of the instances that can be solved efficiently is relatively small. To smooth
this issue, we present a modeling technique for interval robust-hard problems in the context of a
heuristic framework. The heuristic obtains feasible solutions by exploring dual information of a
linearly relaxed model associated with the classical optimization problem counterpart. Computational experiments for interval data min-max regret versions of the restricted shortest path problem and the set covering problem show that our heuristic is able to find optimal or near-optimal
solutions and also improves the primal bounds obtained by a state-of-the-art exact algorithm and
a 2-approximation procedure for interval data min-max regret problems.
Keywords: Robust optimization, Matheuristics, Benders’ decomposition

∗ Corresponding

author.
Email addresses: lucas-assuncao@ufmg.br (Lucas Assunção), tfn@dcc.ufmg.br (Thiago F. Noronha),
andrea.duhamel@utt.fr (Andréa Cynthia Santos), rca@lia.ufc.br (Rafael Andrade)
Preprint submitted to arXiv.org
September 30, 2016

1. Introduction
Robust optimization [1] is an alternative to stochastic programming [2] in which the variability of the data is represented by deterministic values in the context of scenarios. A scenario
corresponds to a parameters assignment, i.e., a value is fixed for each parameter subject to uncertainty. The two main approaches adopted to model robust optimization problems are the discrete
scenarios model and the interval data model. In the former, a discrete set of possible scenarios
is considered. In the latter, the uncertainty referred to a parameter is represented by a continuous interval of possible values. Differently from the discrete scenarios model, the infinite many
possible scenarios that arise in the interval data model are not explicitly given. Nevertheless, in
both models, a classical (i.e., parameters known in advance) optimization problem takes place
whenever a scenario is established.
With respect to robust optimization criteria, the min-max regret (also known as robust deviation criterion) is one of the most used in the literature (see, e.g., [3, 4, 5, 6]). The regret of a
solution in a given scenario is defined as the cost difference between such solution and an optimal one in this scenario. In turn, the robustness cost of a solution is defined as its maximum
regret over all scenarios. Min-max regret problems aim at finding a solution with the minimum
robustness cost, which is referred to as a robust solution. We refer to [1] for details on other
robust optimization criteria.
Robust optimization versions of several combinatorial optimization problems have been studied in the literature, addressing, for example, uncertainties over costs. Handling uncertain costs
brings an extra level of difficulty, such that even polynomially solvable problems become NPhard in their corresponding robust versions [4, 6, 7, 8, 9]. A recent trend in this field is to investigate robust optimization problems whose classical counterparts are already NP-hard. We refer
to these problems as robust-hard problems. The interval data min-max regret restricted shortest
path problem, introduced in this study, belongs to this class of problems, along with interval data
min-max regret versions of the traveling salesman problem [5], the 0-1 knapsack problem [10]
and the set covering problem [11].
This work addresses interval min-max regret problems, which consist of min-max regret versions of combinatorial problems with interval costs. Precisely, we consider interval data min-max
regret generalizations of classical combinatorial problems modeled by means of 0-1 Integer Linear Programming (ILP). Notice that a large variety of combinatorial problems are modeled as 0-1
2

ILP problems, including (i) polynomially solvable problems, such as the shortest path problem,
the minimum spanning tree problem and the assignment problem, and (ii) NP-hard problems,
such as the 0-1 knapsack problem, the set covering problem, the traveling salesman problem and
the restricted shortest path problem [12, 13]. In this study, we are particularly interested in a
subclass of interval min-max regret problems, namely interval robust-hard problems, composed
of interval data min-max regret versions of classical NP-hard combinatorial problems as those
aforementioned in (ii).
Aissi at al. [14] (also see [15]) showed that, for any interval min-max regret problem (including
interval robust-hard problems), the robustness cost of a solution can be computed by solving a
single instance of the classical optimization problem counterpart in a particular scenario. Therefore, one does not have to consider all the infinite many possible scenarios during the search for
a robust solution, but only a subset of them, one for each feasible solution. Notice, however, that,
in the case of interval robust-hard problems, computing the cost of a solution still involves solving an NP-hard problem. Thus, these problems are more challenging than other interval min-max
regret problems.
The state-of-the-art exact algorithms used to solve these problems are based on the generation
of a possibly exponential number of cuts (see, e.g., [5, 11]). Since each cut separation implies
solving an instance of an NP-hard problem (which corresponds to the classical counterpart of the
robust optimization problem considered), the size of the instances efficiently solvable is considerably smaller than that of the instances solved for the corresponding classical counterparts. In
fact, to the best of our knowledge, no work in the literature provides a compact ILP formulation
(with a polynomial number of variables and constraints) for any interval robust-hard problem.
Although we do not close the aforementioned issues in this work, we smooth them by presenting an alternative way to handle interval robust-hard problem. We propose a Linear Programming
(LP) based heuristic framework inspired by the modeling technique introduced in [7, 16] and formalized by Kasperski [9]. The heuristic framework is suitable to tackle interval min-max regret
problems in general and consists in solving a Mixed Integer Linear Programming (MILP) model
based on the dual of a linearly relaxed formulation for the classical optimization problem counterpart. An optimal solution for the model solved by our heuristic is not necessarily optimal for
the original robust optimization problem. However, computational experiments for interval data
min-max regret versions of the restricted shortest path problem and the set covering problem [11]
3

showed that the heuristic is able to find optimal or near-optimal solutions, and that it improves
the upper bounds obtained by both a state-of-the-art exact algorithm and a 2-approximation procedure for interval min-max regret problems.
The theoretical quality of the solutions obtained by the heuristic in general is beyond the scope
of this work, as it may rely on specific problem dependent factors, such as the strength of the
formulation adopted to model the classical counterpart problem within the heuristic framework.
In fact, as we will discuss in the sequel, the study of approximative procedures for interval minmax regret problems is a relatively unexplored field, and not much is known.
The remainder of this work is organized as follows. Related works on robust-hard problems are
discussed in Section 2. In Section 3, we present a standard modeling technique for interval minmax regret problems and a state-of-the-art logic-based Benders’ framework for solving problems
in this class. In this study, the solutions obtained by this exact approach are used to evaluate the
quality of the solutions found by the proposed LP based heuristic framework, which is presented
in Section 4. In Section 5, we formally describe the interval robust-hard problems used as case
studies for the heuristic framework. In this same section, we introduce the interval data minmax regret restricted shortest path problem, along with a brief motivation and related works.
Computational experiments are showed in Section 6, while concluding remarks and future work
directions are discussed in the last section.

2. Related works
As far as we know, Montemanni et al. [5] (also see [17]) were the first to address an interval robust-hard problem. The authors introduced the interval data min-max regret traveling
salesman problem, along with a mathematical formulation containing an exponential number
of constraints. Moreover, three exact algorithms were presented and computationally compared
at solving the proposed formulation: a branch-and-bound, a branch-and-cut and a logic-based
Benders’ decomposition [18] algorithm. The latter algorithm has been widely used to solve robust optimization problems whose classical counterparts are polynomially solvable (see, e.g.,
[4, 6, 8]). Computational experiments showed that the logic-based Benders’ algorithm outperforms the other exact algorithms for the interval data min-max regret traveling salesman problem.
Later on, Pereira and Averbakh [11] introduced the interval data min-max regret set covering
problem. The authors proposed a mathematical formulation for the problem that is similar to
4

the one proposed by [5] for the interval data min-max regret traveling salesman problem. As in
[5], the formulation has an exponential number of constraints. They also adapted the logic-based
Benders’ algorithm of [4, 5, 8] to this problem and presented an extension of the method that aims
at generating multiple Benders’ cuts per iteration of the algorithm. Moreover, the work presents
an exact approach that uses Benders’ cuts in the context of a branch-and-cut framework. Computational experiments showed that such approach, as well as the extended logic-based Benders’
algorithm, outperforms the standard logic-based Benders’ algorithm at solving the instances considered. This robust version of the set covering problem was also addressed in [19], where the
authors propose scenario-based heuristics with path-relinking.
A few works also deal with robust optimization versions of the 0-1 knapsack problem. For
instance, the studies [1] and [20] address a version of the problem where the uncertainty over
each item profit is represented by a discrete set of possible values. In these works, the absolute
robustness criterion is considered. In [20], the author proved that this version of the problem is
strongly NP-hard when the number of possible scenarios is unbounded and pseudo-polynomially
solvable for a bounded number of scenarios. Kouvelis et al. [1] also studied a min-max regret
version of the problem that considers a discrete set of scenarios of item profits. They provided a
pseudo-polynomial algorithm for solving the problem when the number of possible scenarios is
bounded. When the number os scenarios is unbounded, the problem becomes strongly NP-hard
and there is no approximation scheme for it [21].
More recently, Feizollahi and Averbakh [22] introduced the min-max regret quadratic assignment problem with interval flows, which is a generalization of the classical quadratic assignment
problem in which material flows between facilities are uncertain and vary in given intervals.
Although quadratic, the problem presents a structure that is very similar to the robust versions
of combinatorial problems we address in this work. The authors proposed two mathematical
formulations and adapted the logic-based Benders’ algorithm of [4, 5, 8] to solve them through
the linearization of the corresponding master problems. They also developed a hybrid approach
which combines Benders’ decomposition with heuristics.
Regarding heuristics for interval robust-hard problems, a simple and efficient scenario-based
procedure to tackle interval min-max regret problems in general was proposed in [23] and successfully applied in several works (see, e.g., [17, 23, 24]). The procedure, called Algorithm Mean
Upper (AMU), consists in solving the corresponding classical optimization problem in two spe5

cific scenarios: the so called worst-case scenario, where the cost referred to each binary variable
is set to its upper bound, and the mid-point scenario, where the cost of the binary variables are
set to the mean values referred to the bounds of the respective cost intervals. With this heuristic,
one can obtain a feasible solution for any interval min-max regret optimization problem (including interval robust-hard problems) with the same worst-case asymptotic complexity of solving
an instance of the classical optimization problem counterpart. Moreover, it is proven in [24] that
this algorithm is 2-approximative for any interval min-max regret optimization problem. Notice
that AMU does not run in polynomial time for interval robust-hard problems, unless P = NP.
The study of approximative procedures for interval min-max regret problems in general is a
relatively unexplored field, and not much is known. Conde [25] proved that AMU gives a 2approximation for an even broader class of min-max regret problems. Precisely, while the works
of Kasperski et al. [23, 24] only address combinatorial (finite and discrete) min-max regret optimization models, Conde [25] extends the 2-approximation result for models with compact constraint sets in general, including continuous ones. Recently, some research has been conducted to
refine the constant factor of the aforementioned approximation. For example, in [26], the author
attempts to tighten this factor of 2 through the resolution of a robust optimization problem over
a reduced uncertainty cost set. Moreover, in [27], the authors introduced a new bound that gives
an instance dependent performance guarantee of the mid-point scenario solution for interval data
min-max regret versions of combinatorial problems. They show that the new performance ratio is at most 2, and the bound is successfully applied to solve the interval data min-max regret
shortest path problem [1] within a branch-and-bound framework.
Kasperski and Zieliński [28] also developed a Fully Polynomial Time Approximation Scheme
(FPTAS) for interval min-max regret problems. However, this FPTAS relies on two very restrictive conditions: (i) the problem tackled must present a pseudopolynomial algorithm, and (ii) the
corresponding classical counterpart has to be polynomially solvable. Condition (ii) comes from
the fact that the aforementioned FPTAS uses AMU within its framework. Notice that, from (ii),
this FPTAS does not naturally hold for interval robust-hard problems.
The existence of efficient approximative algorithms is closely related to another almost unexplored aspect of interval robust-hard problems, which is their computational complexity. Although NP-hard by definition, whether these problems are necessarily strongly NP-hard or not is
still an open issue.
6

3. Modeling and solving interval min-max regret problems
In this section, we discuss a standard modeling technique in the literature of interval min-max
regret problems, as well as a state-of-the-art exact algorithm to solve problems in this class. To
this end, consider G, a generic 0-1 ILP combinatorial problem defined as follows.
(G)

min
s.t.

cy

(1)

Ay ≥ b

(2)

y ∈ {0, 1}n .

(3)

The binary variables are represented by an n-dimensional column vector y, whereas their corresponding cost values are given by an n-dimensional row vector c. Moreover, b is an mdimensional column vector, and A is an m × n matrix. The feasible region of G is given by
Ω = {y : Ay ≥ b, y ∈ {0, 1}n }.
Let R be an interval data min-max regret robust optimization version of G, where a continuous
cost interval [li , ui ], with li , ui ∈ Z+ and li ≤ ui , is associated with each binary variable yi ,
i = 1, . . . , n. The following definitions describe R formally.
Definition 1. A scenario s is an assignment of costs to the binary variables, i.e., a cost cis ∈ [li , ui ]
is fixed for all yi , i = 1, . . . , n.
Let S be the set of all possible cost scenarios, which consists of the cartesian product of the
continuous intervals [li , ui ], i = 1, . . . , n. The cost of a solution y ∈ Ω in a scenario s ∈ S is given
n
P
by c s y = cis yi .
i=1

Definition 2. A solution opt(s) ∈ Ω is said to be optimal for a scenario s ∈ S if it has the
smallest cost in s among all the solutions in Ω, i.e., opt(s) = arg min c s y.
y∈Ω

Definition 3. The regret (robust deviation) of a solution y ∈ Ω in a scenario s ∈ S, denoted by
rys , is the difference between the cost of y in s and the cost of opt(s) in s, i.e., rys = c s y − c s opt(s).
Definition 4. The robustness cost of a solution y ∈ Ω, denoted by Ry , is the maximum regret of y
among all possible scenarios, i.e., Ry = max rys .
s∈S

∗

Definition 5. A solution y ∈ Ω is said to be robust if it has the smallest robustness cost among
all the solutions in Ω, i.e., y∗ = arg min Ry .
y∈Ω

7

Definition 6. The interval data min-max regret problem R consists in finding a robust solution.
For each scenario s ∈ S, let G(s) denote the corresponding 0-1 ILP problem G under the cost
vector c s ∈ Rn+ referred to s. Also consider an n-dimensional column vector x of binary variables.
Then, R can be generically modeled as follows.
G(s)

(R)

z }| {
max (c y − min c s x)

(4)

y ∈ Ω.

(5)

s

min

x∈Ω

s∈S

s.t.

Theorem 1 (Aissi et al. [14]). The robust deviation (regret) of any feasible solution ȳ ∈ Ω is
maximum in the scenario s(ȳ) induced by ȳ, defined as follows:
for all i ∈ {1, . . . , n},

cis(ȳ)





 ui , if ȳi = 1,
=


 li , if ȳi = 0.

Theorem 1, which is also stated in [15], reduces the number of scenarios to be considered
during the search for a robust solution. Accordingly, R can be rewritten taking into account only
the scenario induced by the solution that the y variables define. This scenario, referred to as s(y),


is represented by the cost vector c s(y) = l1 + (u1 − l1 )y1 , . . . , ln + (un − ln )yn . Then, R can be
rewritten as

G(s(y))

(R̃)

z }| { 

c s(y) y − min c s(y) x

min

x∈Ω

y ∈ Ω.

s.t.

(6)
(7)

In order to obtain an MILP formulation for R, we reformulate R̃ according to [14]. Precisely,
we add a free variable ρ and linear constraints that explicitly bound ρ with respect to all the
feasible solutions that x can represent. The resulting MILP formulation is provided from (8) to
(11).
(F )

min

(

n
X

ui yi − ρ)

(8)

i=1

s.t.

ρ≤

n
X

(li + (ui − li )yi ) x̄i

∀ x̄ ∈ Ω,

(9)

i=1

y ∈ Ω,

(10)

ρ free.

(11)
8

Constraints (9) ensure that ρ does not exceed the value related to the inner minimization in (6).
Note that, in (9), x̄ is a constant vector, one for each solution in Ω. These constraints are tight
whenever x̄ is optimal for the classical counterpart problem G in the scenario s(y). Constraints
(10) define the feasible region referred to the y variables, and constraint (11) gives the domain of
the variable ρ.
The number of constraints (9) corresponds to the number of feasible solutions in Ω. As the
size of this region may grow exponentially with the number of binary variables, this fomulation is
particularly suitable to be handled by decomposition methods, such as the logic-based Benders’
decomposition [18] algorithm detailed below.
3.1. A logic-based Benders’ decomposition algorithm
Benders’ decomposition method was originally proposed in [29] (also see [30]) to tackle MILP
problems by exploring duality theory properties. Several methodologies were later studied to
improve the convergence speed of the method (see, e.g., [31, 32, 33]). More recently, Hooker and
Ottosson [18] introduced the idea of a logic-based Benders’ decomposition, which is a Benderslike decomposition approach suitable for a broader class of problems. This specific method
is intended to address any optimization problem by devising valid cuts solely based on logic
inference.
The logic-based Benders’ algorithm presented below is a state-of-the-art exact method for
interval min-max regret problems [4, 5, 6, 8, 11]. The algorithm solves formulation F , given
by (8)-(11), by assuming that, since several of constraints (9) might be inactive at optimality,
they can be generated on demand whenever they are violated. The procedure is described in
Algorithm 1. Let Ωψ ⊆ Ω be the set of solutions x̄ ∈ Ω (Benders’ cuts) available at an iteration
ψ. Also let F ψ be a relaxed version of F in which constraints (9) are replaced by
ρ≤

n
X

(li + (ui − li )yi ) x̄i

∀ x̄ ∈ Ωψ .

(12)

i=1

Thus, the relaxed problem F ψ , called master problem, is defined by (8), (10), (11) and (12).
Let ubψ keep the best upper bound found (until an iteration ψ) on the solution of F . Notice
that, at the beginning of Algorithm 1, Ω1 contains the initial Benders’ cuts available, whereas
ub1 keeps the initial upper bound on the solution of F . In this case, Ω1 = ∅ and ub1 := +∞. At
each iteration ψ, the algorithm obtains a solution by solving a corresponding master problem F ψ
9

and seeks a constraint (9) that is most violated by this solution. Initially, no constraint (12) is
considered, since Ω1 = ∅. An initialization step is then necessary to add at least one solution to
Ω1 , thus avoiding unbounded solutions during the first resolution of the master problem. To this
end, it is computed an optimal solution for the worst-case scenario su , in which c su = u (Step I,
Algorithm 1).
Algorithm 1: Logic-based Benders’ algorithm.
Input: Cost intervals [li , ui ] referred to yi , i = 1, . . . , n.
Output: A robust solution for F , and its corresponding robustness cost.
ψ ← 1; ub1 ← +∞; Ω1 ← ∅;
Step I. (Initialization)
Find an optimal solution x̄1 = opt(su ) for the worst-case scenario su ;
Ω1 ← Ω1 ∪ { x̄1 };
Step II. (Master problem)
Solve the relaxed problem F ψ , obtaining a solution (ȳψ , ρ̄ψ );
Step III. (Slave problem)
Find an optimal solution x̄ψ = opt(s(ȳψ )) for the scenario s(ȳψ ) induced by ȳψ and use it to
compute Rȳψ , the robustness cost of ȳψ ;
Step IV. (Stopping condition)
lbψ ← uȳψ − ρ̄ψ ;
if lbψ ≥ Rȳψ then
Return (ȳ∗ , R∗ );
end
else
ubψ+1 ← ubψ ← min{ubψ , Rȳψ };
Ωψ+1 ← Ωψ ∪ { x̄ψ };
ψ ← ψ + 1;
Go to Step II;
end

After the initialization step, at each iteration ψ, the corresponding relaxed problem F ψ is
solved (Step II, Algorithm 1), obtaining a solution (ȳψ , ρ̄ψ ). Then, the algorithm checks if (ȳψ , ρ̄ψ )
violates any constraint (9) of the original problem F . For this purpose, it is solved a slave
10

problem that computes Rȳψ (the actual robustness cost of ȳψ ) by finding an optimal solution
x̄ψ = opt(s(ȳψ )) for the scenario s(ȳψ ) induced by ȳψ (see Step III, Algorithm 1). Notice that
each slave problem involves solving the classical optimization problem G, given by (1)-(3), in
the scenario s(ȳψ ).
Let lbψ = uȳψ − ρ̄ψ be the value of the objective function in (8) related to the solution (ȳψ , ρ̄ψ ) of
the current master problem F ψ . According to [34], lbψ and Rȳψ give, respectively, a lower (dual)
and an upper (primal) bounds on the solution of F . If lbψ does not reach Rȳψ , ubψ and ubψ+1
are both set to the best upper bound found by the algorithm until the iteration ψ. In addition,
a new constraint (12) is generated from x̄ψ and added to F ψ+1 by setting Ωψ+1 ← Ωψ ∪ { x̄ψ }.
Otherwise, if lbψ equals Rȳψ , the algorithm stops (see Step IV of Algorithm 1). As proved in
[34], this stopping condition is always satisfied in a finite number of iterations.
The algorithm detailed above is applied to obtain optimal solutions for the interval robust-hard
problems considered in this work, and their corresponding bounds are used to evaluate the quality
of the solutions produced by the heuristic proposed in the next section. We highlight that other
exact algorithms can be adapted and used for this purpose, such as the branch-and-cut algorithm
proposed by Pereira and Averbakh [11] for the interval data min-max regret set covering problem.
In this work, we chose the logic-based Benders’ algorithm, as it has already been successfully
applied to solve a wide range of interval min-max regret problems [4, 5, 6, 8, 11].

4. An LP based heuristic framework for interval min-max regret problems
In this section, we present an LP based heuristic framework for interval robust-hard problems
which is applicable to interval min-max regret problems in general. Consider an interval minmax regret problem R̃, as defined by (6) and (7) in Section 3. For a given ȳ ∈ Ω, the inner
minimization in (6) is a 0-1 ILP problem, namely G(s(ȳ)). Particularly, it corresponds to problem
G, defined by (1)-(3), under the cost vector c s(ȳ) , where s(ȳ) is the scenario induced by ȳ.
Relaxing the integrality on the x variables of G(s(ȳ)), we obtain the LP problem
ϑ(ȳ) = min
s.t.

11

c s(ȳ) x

(13)

Ax ≥ b,

(14)

I x ≤ 1,

(15)

x ≥ 0,

(16)

whose corresponding dual problem is given by
(D(ȳ)) ϑ(ȳ) = max
s.t.

(bT λ + 1T µ)

(17)

AT λ + I T µ ≤ (c s(ȳ) )T ,

(18)

λ ≥ 0,

(19)

µ ≤ 0.

(20)

Here, I is the identidy matrix, and the dual variables λ and µ are associated, respectively, with
constraints (14) and (15) of the primal problem. Notice that, in both LP problems, ϑ(ȳ) corresponds to an optimal solution cost and gives a lower (dual) bound on the optimal value of G(s(ȳ)).
Precisely,
G(s(ȳ))

z }| {
ϑ(ȳ) ≤ min c s(ȳ) x
x∈Ω

∀ ȳ ∈ Ω.

(21)

Replacing G(s(y)) by D(y) in (6), we obtain
min
s.t.



c s(y) y − max (bT λ + 1T µ)

(22)

AT λ + I T µ ≤ (c s(y) )T .

(23)

Constraints (7), (19) and (20),



Recall that c s(y) = l1 + (u1 − l1 )y1 , . . . , ln + (un − ln )yn is the cost vector referred to the scenario

s(y) induced by the y variables. Notice that the nested maximization operator can be omitted,

giving the following formulation.
(R̂)

min
s.t.



c s(y) y − bT λ − 1T µ

(24)

Constraints (7), (19), (20) and (23).

Proposition 1. The cost value referred to an optimal solution for R̂ gives an upper bound on
the optimal solution value of R̃, and this bound is tight (optimal) if (i) the restriction matrix A is
totally unimodular, and (ii) the column vector b is integral.
Proof. Let (ỹ, x̃) and (ŷ, λ̂, µ̂) be optimal solutions for R̃ and R̂, respectively. The value of the
objective function in (6) referred to (ỹ, x̃) is given by (c s(ỹ) ỹ − c s(ỹ) x̃), whereas that of (24) referred
to (ŷ, λ̂, µ̂) is (c s(ŷ) ŷ − (bT λ̂ + 1T µ̂)). Since (ỹ, x̃) is optimal for R̃, we have that (c s(ỹ) ỹ − c s(ỹ) x̃) ≤
(c s(y) y − min c s(y) x) for all y ∈ Ω. In particular, as ŷ ∈ Ω, it holds that
x∈Ω

c s(ỹ) ỹ − c s(ỹ) x̃ ≤ c s(ŷ) ŷ − min c s(ŷ) x.
x∈Ω
12

(25)

As (ŷ, λ̂, µ̂) is optimal for R̂, it follows, from (13)-(21), that
c s(ŷ) ŷ − min c s(ŷ) x ≤ c s(ŷ) ŷ − ϑ(ŷ) = c s(ŷ) ŷ − (bT λ̂ + 1T µ̂).
x∈Ω

(26)

Then, from (25) and (26), we obtain that
c s(ỹ) ỹ − c s(ỹ) x̃ ≤ c s(ŷ) ŷ − (bT λ̂ + 1T µ̂).

(27)

Now, also suppose that (i) the matrix A is totally unimodular, and (ii) the column vector b is
integral. As (ŷ, λ̂, µ̂) is optimal for R̂, it follows, from (13)-(20), that
c s(ŷ) ŷ − (bT λ̂ + 1T µ̂) = c s(ŷ) ŷ − ϑ(ŷ) ≤ c s(y) y − ϑ(y) ∀y ∈ Ω.

(28)

Particularly, as ỹ ∈ Ω,
c s(ŷ) ŷ − (bT λ̂ + 1T µ̂) ≤ c s(ỹ) ỹ − ϑ(ỹ).

(29)

Additionally, from assumption (i), it follows that the restriction matrix (A, I)T referred to (17)(20) is also totally unimodular. Thus, from assumption (ii), inequation (21) is tight, i.e.,
ϑ(ȳ) = min c s(ȳ) x
x∈Ω

∀ȳ ∈ Ω.

(30)

As (ỹ, x̃) is optimal for R̃, we obtain, from (29) and (30),
c s(ŷ) ŷ − (bT λ̂ + 1T µ̂) ≤ c s(ỹ) ỹ − ϑ(ỹ) = c s(ỹ) ỹ − min c s(ỹ) x = c s(ỹ) ỹ − c s(ỹ) x̃,
x∈Ω

(31)

which, along with (27), implies (c s(ŷ) ŷ − (bT λ̂ + 1T µ̂)) = (c s(ỹ) ỹ − c s(ỹ) x̃).
For a given problem R, defined by (4) and (5), the heuristic framework consists in (I) solving
the corresponding formulation R̂, obtaining a solution (ŷ, λ̂, µ̂), and (II) computing the robustness
cost (maximum regret) referred to ŷ, considering Theorem 1. One may note that the heuristic is
applicable not only to interval robust-hard problems, but to any interval min-max regret problem of the general form of R. From Proposition 1, whenever the classical optimization problem
counterpart can be modeled as a 0-1 ILP of the form of G, with a totally unimodular restriction
matrix and b integral, there is a guarantee of optimality at solving R̂. In fact, applying the framework detailed above to the interval data min-max regret versions of the polynomially solvable
shortest path and assignment problems presented, respectively, in [16] and [23], leads to the same
compact MILP formulations proposed and computationally tested in these works.
13

Notice that, whenever G is compact, the resulting formulation R̂ is also compact. We also
highlight that, although the heuristic framework was detailed by the assumption of G being a
minimization problem, the results also hold for maximization problems, with minor modifications. In addition, we conjecture that the heuristic framework also provides valid bounds for the
wider class of interval data min-max regret problems with compact constraint sets addressed in
[25, 26]. We believe that Theorem 1 can be extended to this class of problems through the definition of a specific scenario similar to the one induced by a solution. However, a more careful
study needs to be conducted to close this issue.
In this work, we do not present any theoretical guarantee of quality for the solutions obtained
by the heuristic, as it may rely on specific problem dependent factors, such as the strength of
the formulation adopted to model the classical counterpart problem G. Nevertheless, in the next
section, we present two very successful applications of the heuristic in solving interval robusthard problems.

5. Case studies in solving interval robust-hard problems
In this section, we define the interval robust-hard problems used as case studies for the proposed heuristic framework. For each problem, we give a mathematical formulation according to
the modeling technique presented in Section 3 and devise the corresponding MILP formulation
tackled by the heuristic. For the interval data min-max regret restricted shortest path problem,
which is introduced in this work, we give a more detailed description, along with a brief motivation and some related works. For simplicity, let robust stand for interval data min-max regret in
the designation of each problem.
5.1. The Restricted Robust Shortest Path problem (R-RSP)
The Restricted Robust Shortest Path problem (R-RSP) is an interval data min-max regret version of the Restricted Shortest Path problem (R-SP), an extensively studied NP-hard problem
[12, 13, 35, 36, 37, 38]. Consider a digraph G = (V, A), where V is the set of vertices, and A
is the set of arcs. With each arc (i, j) ∈ A, we associate a resource consumption di j ∈ Z+ and
a continuous cost interval [li j ,ui j ], where li j ∈ Z+ is the lower bound, and ui j ∈ Z+ is the upper
bound on this interval of cost, with li j ≤ ui j . An origin vertex o ∈ V and a destination one t ∈ V
are also given, as well as a value β ∈ Z, parameter used to limit the resource consumed along a
14

path from o to t in G, as discussed in the sequel. An example of an R-RSP instance is given in
Figure 1.
0

}
{2
8]
,
[5

1

}
{1
2]
,
[2

[3,5]{1}

[1,7]{3}

[3,6]{1}
2

[2,2]{1}

3

Figure 1: Example of an R-RSP instance, with origin o = 0 and destination t = 3. The notation
[li j , ui j ]{di j } means, respectively, the cost interval [li j , ui j ] and the resource consumption {di j }
associated with each arc (i, j) ∈ A.

Here, a scenario s is an assignment of arc costs, where a cost cisj ∈ [li j , ui j ] is fixed for all
(i, j) ∈ A. Let P be the set of all paths from o to t and A[p] be the set of the arcs that compose
a path p ∈ P. Also let S be the set of all possible scenarios of G. The cost of a path p ∈ P in
P
a scenario s ∈ S is given by C ps =
cisj . Similarly, the resource consumption referred to a
(i,
j)∈A[p]
P
path p ∈ P is given by D p =
di j . Also consider P(β) = {p ∈ P | D p ≤ β}, the subset of
(i, j)∈A[p]

paths in P whose resource consumptions are smaller than or equal to β.

Definition 7. A path p∗ (s, β) ∈ P(β) is said to be a β-restricted shortest path in a scenario s ∈ S
if it has the smallest cost in s among all paths in P(β), i.e., p∗ (s, β) = arg min C ps .
p∈P(β)

Definition 8. The regret (robust deviation) of a path p ∈ P(β) in a scenario s ∈ S, denoted by
β)
r(s,
, is the difference between the cost C ps of p in s and the cost of a β-restricted shortest path
p
β)
p∗ (s, β) ∈ P(β) in s, i.e., r(s,
= C ps − C ps ∗ (s, β) .
p

Definition 9. The β-restricted robustness cost of a path p ∈ P(β), denoted by Rβp , is the maximum
(s, β)

β

regret of p among all possible scenarios, i.e., R p = max r p
s∈S

.

Definition 10. A path p∗ ∈ P(β) is said to be a β-restricted robust path if it has the smallest
β-restricted robustness cost among all paths in P(β), i.e., p∗ = arg min Rβp .
p∈P(β)

Definition 11. R-RSP consists in finding a β-restricted robust path p∗ ∈ P(β).
15

R-RSP has applications in determining paths in urban areas, where travel distances are known
in advance, but travel times may vary according to unpredictable traffic jams, bad weather conditions, etc. Here, uncertainties are represented by values in continuous intervals, which estimate
the minimum and the maximum traveling times to traverse each pathway. For instance, R-RSP
can model situations involving electrical vehicles with a limited battery (energy) autonomy, when
one wants to find the fastest robust path with a length (distance) constraint. A similar application
arises in telecommunications networks, when one wants to determine a path to efficiently send
a data packet from an origin node to a destination one in a network. Due to the varying traffic
load, transmission links are subject to uncertain delays. Moreover, each link is associated with a
packet loss rate. In order to guarantee Quality of Service (QoS) [38, 39], a limit is imposed on
the total packet loss rates of the path used.
The classical R-SP is a particular case of R-RSP in which li j = ui j ∀ (i, j) ∈ A. As R-SP is
known to be NP-hard [12, 13] even for acyclic graphs [38], the same holds for R-RSP. The main
exact algorithms to solve R-SP can be subdivided into two groups: Lagrangian relaxation and
dynamic programming procedures. The former procedures use Lagrangian relaxation to handle
ILP formulations for the problem (see, e.g., [13, 36]). In addition, preprocessing techniques have
been presented in [35] and refined in [36]. These techniques identify arcs and vertices that cannot
compose an optimal solution for R-SP through the analysis of the reduced costs related to the
resolution of dual Lagrangian relaxations. More recently, [40] proposed a path ranking approach
that linearly combines the arc costs and the resource consumption values to generate a descent
direction of search. In turn, dynamic programming procedures for R-SP consist of label-setting
and label-correcting algorithms, such as the one proposed in [41] and further improved in [42] by
the addition of preprocessing strategies. Recently, Zhu and Wilhelm [43] developed a three-stage
label-setting algorithm that runs in pseudo-polynomial time and figures among the state-of-theart methods to solve R-SP, along with the algorithms presented in [40] and [42]. We refer to [44]
for a survey on exact methods to solve R-SP.
Although NP-hard, R-SP can be solved efficiently by some of the aforementioned procedures
(particularly, the ones proposed in [40, 42, 43]). Moreover, optimization softwares, as CPLEX1 ,
are also competitive in handling reasonably-sized instances (with up to 3000 vertices) of the
problem [43].
1 http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

16

R-RSP is also a generalization of the interval data min-max regret Robust Shortest Path problem (RSP) [1, 3, 45, 46]. RSP consists in finding a robust path (from the origin vertex to the
destination one) considering the min-max regret criterion, with no additional resource consumption restriction on the solution path. Therefore, RSP can be reduced to R-RSP by considering
β = 0 and di j = 0 ∀ (i, j) ∈ A.
Preprocessing techniques able to identify arcs that cannot compose an optimal solution for
RSP have been proposed in [16] and later improved in [47]. A compact MILP formulation for
the problem, based on the dual of an LP formulation for the classical shortest path problem, was
presented in [16]. Exact algorithms have been proposed for RSP, such as the branch-and-bound
algorithm of [48] and the logic-based Benders’ algorithm of [8], which is able to solve instances
with up to 4000 vertices. Moreover, the FPTAS of [28] for interval min-max regret problems
is applicable to RSP when the problem is considered in series-parallel graphs. However, as
pointed out by the end of Section 2, this FPTAS does not naturally extend to interval robust-hard
problems, such as R-RSP.

5.1.1. Mathematical formulation
The mathematical formulation here presented makes use of Theorem 1, which can be stated
for the specific case of R-RSP as follows.
Proposition 2. Given a value β ∈ Z and a path p ∈ P(β), the regret of p is maximum in the
scenario s(p) induced by p, where the costs of all the arcs of p are in their corresponding upper
bounds and the costs of all the other arcs are in their lower bounds.

2{
1}

5{1}

1
1{3}

3{1}
2

2{1}
5{
2}

0

3

Figure 2: Scenario s p̃ induced by the path p̃ = {0, 1, 2, 3} in the digraph presented in Figure 1.
s( p̃)

s( p̃)

For each arc (i, j) ∈ A, the notation ci j {di j } means, respectively, the arc cost ci j in the scenario
s( p̃) and its resource consumption {di j }.
17

Consider the digraph presented in Figure 1 and the scenario s( p̃) induced by the path p̃ =
{0, 1, 2, 3} (as showed in Figure 2). Also let the resource limit be β = 3. According to Proposition
p̃), β)
2, the β-restricted robustness cost of p̃ is given by Rβp̃ = r(s(
= C p̃s( p̃) − C ps(∗p̃)
p̃
(s( p̃), β) = (2 +

2 + 5) − (3 + 5) = 1. Proposition 2 reduces R-RSP to finding a path p∗ ∈ P(β) such that
(s(p), β)

p∗ = arg min r p
p∈P

s(p)

, i.e., p∗ = arg min {C p
p∈P(β)

s(p)

− C p∗ (s(p), β) }. Nevertheless, computing the β-

restricted robustness cost of any feasible solution p for R-RSP still implies finding a β-restricted
shortest path p∗ (s(p), β) in the scenario s(p) induced by p, and this problem is NP-hard.
Now, let us consider the following result, which helps describing an optimal solution path for
R-RSP.
Property 1. Given two arbitrary sets Z1 and Z2 , it holds that Z1 = (Z1 ∩ Z2 ) ∪ (Z1 \Z2 ).
Theorem 2. Given a value β ∈ Z and a non-elementary path p ∈ P(β), for any elementary path
p̃),β)
p̃ ∈ P(β) such that A[ p̃] ⊂ A[p], it holds that r(s(
≤ r(s(p),β)
.
p
p̃

Proof. Consider a value β ∈ Z and a non-elementary path p ∈ P(β). By definition, p contains at
least one cycle. Let G[p] be the subgraph of G induced by the arcs in A[p] and p̃ be an elementary
path from o to t in G[p]. Clearly, A[ p̃] ⊂ A[p] and, therefore, p̃ ∈ P(β). By definition,
(s( p̃),β)

r p̃

s( p̃)

= C p̃

s( p̃)

− C p∗ (s( p̃),β) .

(32)

Consider the set Ā = A[p]\A[ p̃] of the arcs in p which do not belong to p̃. As p is supposed to
contain at least one cycle, then Ā , ∅. Since A[ p̃] ⊂ A[p], the difference between scenarios s(p)
and s( p̃) consists of the cost values assumed by the arcs in Ā. More precisely,
cis(j p̃) = cis(p)
j
cis(p)
j = ui j
s( p̃)

ci j = li j

∀(i, j) ∈ A\Ā,

(33)

∀(i, j) ∈ Ā,

(34)

∀(i, j) ∈ Ā.

(35)

It follows that
C p̃s( p̃) =

X

(i, j)∈A[ p̃]

ui j =

X

(i, j)∈A[p]

X

ui j −

(i, j)∈A[p]\A[ p̃]

18

ui j = C ps(p) −

X

(i, j)∈Ā

ui j .

(36)

Applying Property 1 to the sets A[p∗ (s( p̃), β)] and A[p]:
(a1 )

z
}|
{
A[p (s( p̃), β)] = (A[p∗ (s( p̃), β)] ∩ A[p]) ∪(A[p∗ (s( p̃), β)]\A[p]).
∗

(37)

Since A[ p̃] ⊂ A[p] and Ā = A[p]\A[ p̃], it follows that
A[p] = A[ p̃] ∪ (A[p]\A[ p̃]) = A[ p̃] ∪ Ā.

(38)

Therefore, expression (a1 ) of (37) can be rewritten as
(A[p∗ (s( p̃), β)] ∩ A[p]) = (A[p∗ (s( p̃), β)] ∩ (A[ p̃] ∪ Ā)) =

(A[p∗ (s( p̃), β)] ∩ A[ p̃]) ∪ (A[p∗ (s( p̃), β)] ∩ Ā).

(39)

s

p
Applying (37) and (39) to C ps(∗p̃)
(s( p̃),β) and C p∗ (s( p̃),β) , we obtain:

X

C ps(∗p̃)
(s( p̃),β) =

(i, j)∈A[p∗ (s( p̃),β)]∩A[ p̃]

cis(j p̃)

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

X

+

X

cis(j p̃) +
cis(j p̃) ,

(40)

(i, j)∈A[p∗ (s( p̃),β)]\A[p]

X

C ps(p)
∗ (s( p̃),β) =

(i, j)∈A[p∗ (s( p̃),β)]∩A[ p̃]

X

+

X

cis(p)
j +

cis(p)
j

(i, j)∈A[p∗ (s( p̃),β)]∩Ā
s(p)

ci j .

(41)

(i, j)∈A[p∗ (s( p̃),β)]\A[p]

Considering (33)-(35), (40) and (41), we deduce that the difference between the cost of path
p∗ (s( p̃), β) in s(p) and its cost in s( p̃) is given by the arcs which are simultaneously in Ā and in
A[p∗ (s( p̃), β)]. Thus, expressions (40) and (41) can be reformulated as
X

C ps(∗p̃)
(s( p̃),β) =

(i, j)∈A[p∗ (s( p̃),β)]∩A[ p̃]

+

X

ui j +
X

(i, j)∈A[p∗ (s( p̃),β)]\A[p]

19

li j

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

li j ,

(42)

X

C ps(p)
∗ (s( p̃),β) =

(i, j)∈A[p∗ (s( p̃),β)]∩A[ p̃]

ui j

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

X

+

X

ui j +
li j .

(43)

(i, j)∈A[p∗ (s( p̃),β)]\A[p]

Subtracting (43) from (42),
X

s(p)
C ps(∗p̃)
(s( p̃),β) − C p∗ (s( p̃),β) =

X

li j −

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

ui j .

(44)

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

Therefore,
X

s(p)
C ps(∗p̃)
(s( p̃),β) = C p∗ (s( p̃),β) −

(ui j − li j ).

(45)

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

Applying (36) and (45) in (32):
p̃),β)
r(s(
= C ps(p) −
p̃

X

(i, j)∈Ā


ui j − C ps(p)
∗ (s( p̃),β) −
X

C ps(p) − C ps(p)
∗ (s( p̃),β) +

X

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

(ui j − li j ) −

(i, j)∈A[p∗ (s( p̃),β)]∩Ā


(ui j − li j ) =

X

ui j .

(46)

(i, j)∈Ā

One may note that
X

(ui j − li j ) −

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

X

(i, j)∈Ā

ui j ≤

X

(ui j − li j ) −

X

(i, j)∈Ā

(i, j)∈Ā

P

Since Ā ⊂ A, and li j ≥ 0 for all (i, j) ∈ A, it follows that

ui j ≤

X

(−li j ).

(47)

(i, j)∈Ā

(−li j ) ≤ 0 and, thus,

(i, j)∈Ā

X

(ui j − li j ) −

(i, j)∈A[p∗ (s( p̃),β)]∩Ā

X

ui j ≤ 0.

(48)

(i, j)∈Ā

From (46) and (48),
p̃),β)
r(s(
≤ C ps(p) − C ps(p)
∗ (s( p̃),β) .
p̃

20

(49)

As p∗ (s(p), β) is a path with the smallest cost in s(p) among all the paths in P(β), including
s(p)
p∗ (s( p̃), β), it holds that C ps(p)
∗ (s( p̃),β) ≥ C p∗ (s(p),β) . Thus,
p̃),β)
s(p)
r(s(
≤ C ps(p) − C ps(p)
− C ps(p)
∗ (s( p̃),β) ≤ C p
∗ (s(p),β) .
p̃

(50)

(s( p̃),β)
By definition, r(s(p),β)
= C ps(p) − C ps(p)
≤ r(s(p),β)
.
∗ (s(p),β) . Therefore, r p̃
p
p

Now, we can devise a mathematical formulation for R-RSP from the generic model R̃, defined
by (6) and (7). Consider the decision variables y on the choice of arcs belonging or not to a βrestricted robust path: yi j = 1 if the arc (i, j) ∈ A belongs to the solution path; yi j = 0, otherwise.
Likewise, let the binary variables x identify a β-restricted shortest path in the scenario induced
by the path defined by y, such that xi j = 1 if the arc (i, j) ∈ A belongs to this β-restricted shortest
path, and xi j = 0, otherwise. A nonlinear compact formulation for R-RSP is given by
!
X
X
(li j + (ui j − li j )yi j )xi j .
min
ui j yi j − min
y∈P(β)

x∈P(β)

(i, j)∈A

(51)

(i, j)∈A

As discussed in Section 3, we can derive an MILP formulation from (51) by adding a free
variable ρ and linear constraints that explicitly bound ρ with respect to all the feasible paths that
x can represent. The resulting formulation is provided from (52) to (59).
min

X

u i j yi j − ρ

(52)

(i, j)∈A

s.t.

X

y jo −

X

y ji −

X

y jt −

j:( j,o)∈A

yok = −1,

(53)

k:(o,k)∈A

j:( j,i)∈A

X

yik = 0

X

ytk = 1,

∀ i ∈ V\{o, t},

(54)

k:(i,k)∈A

j:( j,t)∈A

X

X

(55)

k:(t,k)∈A

di j yi j ≤ β,

(56)

(i, j)∈A

ρ≤

X

(li j + (ui j − li j )yi j ) x̄i j

∀ x̄ ∈ P(β),

(57)

(i, j)∈A

yi j ∈ {0, 1} ∀ (i, j) ∈ A,

(58)

ρ free.

(59)

The flow conservation constraints (53)-(55), along with the domain constraints (58), ensure
that the y variables define a path from the origin to the destination vertices. In fact, as pointed out
21

in [16], these constraints do not prevent the existence of additional cycles of cost zero disjoint
from the solution path. Notice, however, that every arc (i, j) of these cycles necessarily has
li j = ui j = 0 and, thus, they do not modify the optimal solution value. Hence, these cycles are
not taken into account hereafter.
Constraint (56) limits the resource consumption of the path defined by y to be at most β,
whereas constraints (57) guarantee that ρ does not exceed the value related to the inner minimization in (51). Note that, in (57), x̄ is a constant vector, one for each path in P(β). Moreover,
these constraints are tight whenever x̄ identifies a β-restricted shortest path in the scenario induced by the path that y defines. Constraint (59) gives the domain of the variable ρ.
Notice that, in the definition of R-RSP, we do not impose that a vertex in the solution path must
be traversed at most once. However, if that is the case, Theorem 2 indicates that the formulation
presented above can also be used to determine an elementary solution path for R-RSP by simply
discarding some edges from the cycles that may appear in the solution. In fact, Proposition 2 and
Theorem 2 imply that, for any β ∈ Z, if P(β) , ∅, then there is an elementary path p ∈ P(β)
which is a β-restricted robust path.
In this study, we use the logic-based Benders’ algorithm discussed in the Section 3.1 to solve
the formulation detailed above.
5.1.2. An LP based heuristic for R-RSP
In this section, we apply to R-RSP the heuristic framework presented in Section 4. To this
end, consider the following R-SP ILP formulation used to compute a β-restricted shortest path
p∗ (s, β) ∈ P(β) in a scenario s ∈ S. The binary variables x define p∗ (s, β), such that xi j = 1 if the
arc (i, j) ∈ A belongs to A[p∗ (s, β)], and xi j = 0, otherwise.
(I1 )

min

X

cisj xi j

(60)

(i, j)∈A

s.t.

X

x jo −

X

x ji −

X

x jt −

j:( j,o)∈A

X

xok = −1,

(61)

k:(o,k)∈A

j:( j,i)∈A

j:( j,t)∈A

X

X

xik = 0

X

xtk = 1,

∀ i ∈ V\{o, t},

(62)

k:(i,k)∈A

(63)

k:(t,k)∈A

di j xi j ≤ β,

(64)

(i, j)∈A

xi j ∈ {0, 1} ∀ (i, j) ∈ A.
22

(65)

The objective function in (60) represents the cost, in the scenario s, of the path defined by x,
while constraints (61)-(65) ensure that x identifies a path in P(β). Relaxing the integrality on x,
we obtain the following LP formulation:
X

(L1 ) θ(s, β) = min

cisj xi j

(66)

(i, j)∈A

s.t.

Constraints (61)-(64),
xi j ≥ 0

∀ (i, j) ∈ A.

(67)

The domain constraints xi j ≤ 1 for all (i, j) ∈ A were omitted from L1 , since they are redundant. Let θ(s, β) be the optimal value for problem L1 in a scenario s. Observe that θ(s, β) provides
a lower bound on the solution of I1 in the scenario s. For the sake of clarity, let us define a new
metric to evaluate the quality of a path in P(β).
Definition 12. The β-heuristic robustness cost of a path p ∈ P(β), denoted by H βp , is the difference
s(p)

between the cost C p

of p in the scenario s(p) induced by p and the relaxed cost θ(s(p), β) in s(p),

i.e., H βp = C ps(p) − θ(s(p), β) .
Definition 13. A path p̃∗ ∈ P(β) is said to be a β-heuristic robust path if it has the smallest
β

β-heuristic robustness cost among all the paths in P(β), i.e., p̃∗ = arg min H p .
p∈P(β)

In the case of R-RSP, the proposed heuristic aims at finding a β-heuristic robust path and relies
on the hypothesis that such a path is a near-optimal solution for R-RSP. The problem of finding
a β-heuristic robust path can be modeled by adapting formulation (51). To this end, the binary
variables y now represent a β-heuristic robust path in P(β). Furthermore, considering the scenario
s(y) induced by the path defined by y, the nested minimization in (51) is replaced by θ(s(y), β) . We
obtain:
min

y∈P(β)

X

(i, j)∈A

!
ui j yi j − θ(s(y), β) .

(68)

Given a scenario s ∈ S, the optimal value assumed by θ(s, β) can be represented by the dual of
L1 , as follows:
(L̃1 )

θ(s,β) = max
s.t.

(λt − λo − βµ)
λ j ≤ λi + cisj + di j µ

(69)
∀ (i, j) ∈ A,

(70)

µ ≥ 0,

(71)

λk free ∀ k ∈ V.
23

(72)

The dual variables {λk : k ∈ V} and µ are associated, respectively, with constraints (61)-(63)
and with constraint (64) in the primal problem L1 . Since L̃1 is a maximization problem, its
objective function, along with (70)-(72), can be used to replace the relaxed cost θ(s(y),β) in (68),
thus deriving the following formulation:
X

min

y∈P(β)

s.t.

(i, j)∈A

From (69) !
z
}|
{
ui j yi j − (λt − λo − βµ)

λ j ≤ λi + li j + (ui j − li j )yi j + di j µ

(73)
∀ (i, j) ∈ A,

(74)

µ ≥ 0,

(75)

λk free ∀ k ∈ V.

(76)

Notice that constraints (74) consider the cost of each arc (i, j) ∈ A in the scenario s(y) induced
by the path identified by the y variables, i.e., the cost of each arc (i, j) ∈ A is given by (li j + (ui j −
li j )yi j ). The domain constraints (75) and (76) related to L̃1 remain the same. Now, we give an
MILP formulation for the problem of finding a β-heuristic robust path.
!
X
(H1 ) min
ui j yi j − λt + λo + βµ

(77)

(i, j)∈A

s.t.

X

y jo −

X

y ji −

X

y jt −

j:( j,o)∈A

X

yok = −1,

(78)

k:(o,k)∈A

j:( j,i)∈A

j:( j,t)∈A

X

X

yik = 0 ∀ i ∈ V\{o, t},

(79)

X

ytk = 1,

(80)

k:(i,k)∈A

k:(t,k)∈A

di j yi j ≤ β,

(81)

(i, j)∈A

Constraints (74)-(76),
yi j ∈ {0, 1} ∀ (i, j) ∈ A.

(82)

The objective function in (77) represents the β-heuristic robustness cost of the path defined
by the y variables. Constraints (78)-(81) and (82) ensure that y belongs to P(β). Constraints
(74)-(76) are the remaining restrictions related to L̃1 .
The heuristic consists in solving the corresponding problem H1 in order to find a β-heuristic
robust path p̃∗ ∈ P(β). Note that p̃∗ is also a feasible solution path for R-RSP, and, according to
Proposition 1, its β-heuristic robustness cost provides an upper bound on the solution of R-RSP.
Such bound can be improved by the evaluation of the actual β-restricted robustness cost of p̃∗ .
24

5.2. The Robust Set Covering problem (RSC)
The Robust Set Covering problem (RSC), introduced by Pereira and Averbakh [6], is an interval data min-max regret generalization of the Set Covering problem (SC). The classical SC is
known to be strongly NP-hard [12], and, thus, the same holds for RSC.
Let O = (oi j ) be an i × j binary matrix, such that I = {1, . . . , i} and J = {1, . . . , j} are its
corresponding rows and columns sets, respectively. We say that a column j ∈ J covers a row
i ∈ I if oi j = 1. In this sense, a covering is a subset K ⊆ J of columns such that every row in
I is covered by at least one column from K. Hereafter, we denote by Λ the set of all possible
coverings.
In the case of RSC, we associate with each column j ∈ J a continuous cost interval [l j ,u j ],
with l j , u j ∈ Z+ and l j ≤ u j . Accordingly, a scenario s is an assignment of column costs, where
a cost c sj ∈ [l j , u j ] is fixed for all j ∈ J. The set of all these possible cost scenarios is denoted by
P s
S, and the cost of a covering K ∈ Λ in a scenario s ∈ S is given by C Ks =
c j.
j∈K

∗

Definition 14. A covering K (s) ∈ Λ is said to be optimal in a scenario s ∈ S if it has the

smallest cost in s among all coverings in Λ, i.e., K ∗ (s) = arg min C Ks .
K∈Λ

Definition 15. The regret (robust deviation) of a covering K ∈ Λ in a scenario s ∈ S, denoted by
rKs , is the difference between the cost C Ks of K in s and the cost of an optimal covering K ∗ (s) ∈ Λ
in s, i.e., rKs = C Ks − C Ks ∗ (s) .
Definition 16. The robustness cost of a covering K ∈ Λ, denoted by RK , is the maximum regret
of K among all possible scenarios, i.e., RK = max rKs .
s∈S

∗

Definition 17. A covering K ∈ Λ is said to be a robust covering if it has the smallest robustness
cost among all coverings in Λ, i.e., K ∗ = arg min RK .
K∈Λ

Definition 18. RSC consists in finding a robust covering K ∗ ∈ Λ.
As far as we are aware, RSC was only addressed in [6] and [19]. On the other hand, the classical SC has been widely studied in the literature, especially because it can be used as a basic model
for applications in several fields, including production planning [49] and crew management [50].
We refer to [51] for an annotated bibliography on the main applications and the state-of-the-art of
SC. We highlight that, as well as for the classical counterpart of R-RSP, directly solving compact
ILP formulations for RSC via CPLEX’s branch-and-bound is competitive with the best exact
algorithms for the problem [52].
25

5.2.1. Mathematical formulation
The mathematical formulation presented below was proposed by Pereira and Averbakh [6]. As
the one for R-RSP presented in Section 5.1.1, this formulation is based on the modeling technique
for interval min-max regret problems in general discussed in Section 3. For the specific case of
RSC, Theorem 1 can be stated as follows.
Proposition 3. Given a covering X ∈ Λ, the regret of K is maximum in the scenario induced by
K, where the costs of all the columns of K are in their corresponding upper bounds and the costs
of all the other columns are in their lower bounds.
Now, consider the decision variables y on the choice of columns belonging or not to a robust
covering, such that y j = 1 if the column j ∈ J belongs to the solution; y j = 0, otherwise. Also
let ρ be a continuous variable. The MILP formulation of [6] is provided from (83) to (87).
min

X

u jy j − ρ

X

oi j y j ≥ 1

ρ≤

X

(83)

j∈J

s.t.

∀ i ∈ I,

(84)

j∈J

(l j + (u j − l j )y j ) x̄ j

∀ x̄ ∈ Λ,

(85)

j∈J

y j ∈ {0, 1} ∀ j ∈ J,

(86)

ρ free.

(87)

The objective function in (83) considers Proposition 3 and gives the robustness cost of a robust
covering. Constraints (84) and (86) ensure that the y variables represent a covering, whereas
constraints (85) guarantee that ρ does not exceed the cost of an optimal covering in the scenario
induced by the covering defined by y. In (85), x̄ is a constant vector, one for each possible
covering. Constraint (87) gives the domain of the variable ρ.
As for R-RSP, we use the logic-based Benders’ algorithm discussed in the Section 3.1 to solve
the formulation described above.

5.2.2. An LP based heuristic for RSC
Consider the following ILP formulation used to model the classical SC in a given cost scenario
s ∈ S. Here, the binary variables x define an optimal covering K ∗ (s) ∈ Λ in s, such that x j = 1 if
26

the column j ∈ J belongs to K ∗ (s), and x j = 0, otherwise.
(I2 )

min

X

c sj x j

(88)

X

oi j x j ≥ 1 ∀ i ∈ I,

(89)

j∈J

s.t.

j∈J

x j ∈ {0, 1} ∀ j ∈ J.

(90)

The objective function in (88) gives the cost, in the scenario s, of the covering defined by x,
while constraints (89) and (90) ensure that x identifies a covering in Λ. Relaxing the integrality
on x, we obtain:
(L2 )

min

X

c sj x j

(91)

j∈J

s.t.

Constraint (89),
xj ≥ 0

∀ j ∈ J.

(92)

Notice that we omitted the domain constraints x j ≤ 1 for all j ∈ J, since they are redundant
in this case. Considering formulations I2 , L2 and the generic model R̂, given by (7), (19), (20),
(23) and (24), we can devise a heuristic formulation for RSC. Now, the y variables represent a
heuristic solution covering, and the variables {λi : i ∈ I} are the ones of the dual problem related
to L2 .
(H2 )

min

X
j∈J

s.t.

X !
u jy j −
λi

(93)

i∈I

X

oi j y j ≥ 1 ∀ i ∈ I,

X

oi j λi ≤ l j + (u j − l j )y j

(94)

j∈J

∀ j ∈ J,

(95)

i∈I

λi ≥ 0 ∀ i ∈ I,

(96)

y j ∈ {0, 1} ∀ j ∈ J.

(97)

According to Proposition 1, the objective function in (93) gives an upper bound on the robustness cost of a robust solution for RSC. Constraints (94) and (97) ensure that y defines a covering
in Λ, while constraints (95) are the ones related to the dual of L2 . Notice that constraints (95)
consider the cost of each column j ∈ J in the scenario induced by the covering identified by the
y variables. Restrictions (96) give the domain of the dual variables λ.
27

In the case of RSC, the LP based heuristic consists in solving formulation H2 and, then,
computing the robustness cost of the solution obtained.

6. Computational experiments
In this section, we evaluate, out of computational experiments, the effectiveness and the time
efficiency of the proposed heuristic at solving the two interval robust-hard problems considered
in this study. For short, the Logic-Based Benders’ decomposition algorithm is referred to as
LB-Benders’, whereas the LP based Heuristic is referred to as LPH. LB-Benders’, LPH and
the 2-approximation heuristic for interval min-max regret problems, namely AMU [23], were
implemented in C++, along with the optimization solver ILOG CPLEX 12.5. The computational
experiments were performed on a 64 bits Intel R Xeon R E5405 machine with 2.0 GHz and 7.0
GB of RAM, under Linux operating system. LB-Benders’ was set to run for up to 3600 seconds
of wall-clock time.
6.1. The Restricted Robust Shortest Path problem (R-RSP)
In all of the algorithms implemented, whenever a classical R-SP instance had to be solved,
we used CPLEX to handle the ILP formulation I1 , defined by (60)-(65), directly. We also used
CPLEX to solve each master problem in LB-Benders’ and the heuristic formulation H1 , defined
by (77)-(82)
6.1.1. Benchmarks description
Due to the lack of R-RSP instances in the literature, we generated two benchmarks of instances
inspired by the applications described in Section 5.1. These benchmarks were adapted from
two sets of RSP instances: Karaşan [16] and Coco [53] instances, which model, respectively,
telecommunications and urban transportation networks.
Karaşan instances have been largely used in experiments concerning RSP [8, 16, 48, 53, 54].
They consist of layered [55] and acyclic [56] digraphs. In these digraphs, each of the κ layers
has the same number ω of vertices. There is an arc from every vertex in a layer b ∈ {1, . . . , κ − 1}
to every vertex in the adjacent layer b + 1. Moreover, there is an arc from the origin o to every
vertex in the first layer, and an arc from every vertex in the layer κ to the destination vertex t.
These instances are named K-v-Φmax -δ-ω, where v is the number of vertices (aside from o and
28

t), Φmax is an integer constant, and 0 < δ < 1 is a continuous value. The arc cost intervals were
generated as follows. For each arc (i, j) ∈ A, a random integer value Φi j was uniformly chosen
in the range [1, Φmax ]. Afterwards, random integer values li j and ui j were uniformly selected,
respectively, in the ranges [(1 − δ) · Φi j , (1 + δ) · Φi j ] and [li j , (1 + δ) · Φi j ]. Note that Φ plays
the role of a base-case scenario, and δ determines the degree of uncertainty. Figure 3 shows an
example of an acyclic digraph with 3 layers of width 2.
1

3

5

0

7
2

4

6

Figure 3: An acyclic digraph with 3 layers of width 2. Here, o = 0 and t = 7.
Coco instances consist of grid digraphs based on n × m matrices, where n is the number of
rows and m is the number of columns. Each matrix cell corresponds to a vertex in the digraph,
and there are two bidirectional arcs between each pair of vertices whose respective matrix cells
are adjacent. The origin o is defined as the upper left vertex, and the destination t is defined as
the lower right vertex. These instances are named G-n×m-Φmax -δ, with 0 < δ < 1, where Φmax
is an integer value. Given Φmax and δ values, the cost intervals are generated as in the Karaşan
instances. Figure 4 gives an example of a grid digraph.
0

1

2

3

4

5

6

7

Figure 4: A 2 × 4 grid digraph, with o = 0 and t = 7.
For all instances, the resource consumption associated with each arc is given by a random
integer value uniformly selected in the interval (0, 10]. The small interval amplitude allows
the generation of instances in which most of the arcs are candidate to appear in an optimal
solution, increasing the number of feasible solutions. The symmetry with respect to arc resource
consumptions was preserved, i.e., we considered di j = d ji for any pair of adjacent vertices i and
j such that (i, j) ∈ A and ( j, i) ∈ A.
The resource consumption limit β of a given instance was computed as follows. Consider
29

the set P of all the paths from o to t, and let p̄ ∈ P be a shortest path in terms of resource
consumption, i.e., p̄ = arg min D p . We set β = 1.1·D p̄ , which means that is given a 10% tolerance
p∈P

with respect to the minimum resource consumption D p̄ . This way, the resource consumption limit
is tighter.
We generated Karaşan and Coco instances of 1000 and 2000 vertices, with Φmax ∈ {20, 200},
δ ∈ {0.5, 0.9} and ω ∈ {5, 10, 25}. Considering these values, a group of 10 instances was generated for each possible parameters configuration. In summary, 480 instances were used in the
experiments.
6.1.2. Results
Computational experiments were carried out in order to evaluate if the proposed heuristic
efficiently finds optimal or near-optimal solutions for the two benchmarks of instances described
above. Results for Karaşan and Coco instances are reported in Tables 1 and 2, respectively. The
first column displays the name of each group of 10 instances. The second and third columns
show, respectively, the number of instances solved at optimality by LB-Benders’ within 3600
seconds, and the average wall-clock processing time (in seconds) spent in solving these instances.
If no instance in the group was solved at optimality, this entry is filled with a dash. The fourth and
fifth columns show, respectively, the average and the standard deviation (over the 10 instances)
of the relative optimality gaps given by 100 ·

UBb −LBb
UBb .

Here, LBb and U Bb are, respectively, the

best lower and upper bounds obtained by LB-Benders’ for a given instance. The sixth column
displays the average wall-clock processing time (in seconds) of AMU. The seventh column shows
the average (over the 10 instances) of the relative gaps given by 100 ·

UBamu −LBb
UBamu ,

where U Bamu

is the best upper bound obtained by AMU for a given instance. The standard deviation of these
gaps is given in the eighth column. Likewise, the ninth column shows the average wall-clock
processing time of LPH, and the last two columns give the average and the standard deviation
(over the 10 instances) of the gaps given by 100 ·

UBlph −LBb
UBlph .

Here, U Blph is the β-restricted

robustness cost of the solution obtained by LPH for a given instance.
Notice that the gaps referred to the solutions obtained by AMU and LPH consider the best
lower bounds obtained by LB-Benders’ (within 3600 seconds of execution), which might not
correspond to the cost of optimal solutions. Thus, the aforementioned gaps may overestimate the
actual gaps between the cost of the solutions obtained and the cost of optimal ones.
30

Table 1: Computational results for the layered and acyclic digraph instances.

LB-Benders’
Test set

#opt

Time (s)

AvgGAP (%)

AMU
StDev (%)

Time (s)

AvgGAP (%)

LPH
StDev (%)

Time (s)

AvgGAP (%)

StDev (%)

31

K-1000-20-0.5-5

8

1515.25

0.11

0.24

3.13

4.21

3.59

10.33

0.11

0.24

K-1000-20-0.9-5

2

2108.61

7.47

5.29

3.12

10.06

4.21

28.84

5.79

3.75

K-1000-200-0.5-5

10

1165.08

0.00

0.00

3.13

3.68

2.18

8.52

0.16

0.28

K-1000-200-0.9-5

1

1919.16

4.85

3.30

3.07

9.77

1.83

21.36

3.80

2.57

K-1000-20-0.5-10

10

83.30

0.00

0.00

4.15

3.06

2.70

11.23

0.07

0.22

K-1000-20-0.9-10

10

218.69

0.00

0.00

4.17

4.52

3.20

17.75

0.00

0.00

K-1000-200-0.5-10

10

42.54

0.00

0.00

3.96

1.57

1.84

10.45

0.31

0.97

K-1000-200-0.9-10

10

413.43

0.00

0.00

3.94

4.50

2.98

24.44

0.05

0.15

K-1000-20-0.5-25

10

17.61

0.00

0.00

7.35

3.12

4.52

21.55

0.00

0.00

K-1000-20-0.9-25

10

32.22

0.00

0.00

7.51

2.35

3.69

26.97

0.24

0.76

K-1000-200-0.5-25

10

18.17

0.00

0.00

7.25

1.27

2.71

23.67

0.00

0.00

K-1000-200-0.9-25

10

41.04

0.00

0.00

7.33

1.13

1.89

30.92

0.00

0.00

K-2000-20-0.5-5

0

0.00

14.47

5.89

10.61

14.30

4.06

64.61

10.43

3.87

K-2000-20-0.9-5

0

0.00

25.01

2.69

10.68

21.35

2.17

241.13

17.94

2.38

K-2000-200-0.5-5

0

0.00

14.45

3.10

10.38

14.15

2.87

69.62

10.70

2.21

K-2000-200-0.9-5

0

0.00

25.77

3.39

10.43

22.13

3.17

454.79

18.15

2.79

K-2000-20-0.5-10

8

1297.89

0.91

2.23

13.01

4.37

3.69

92.04

0.89

1.99

K-2000-20-0.9-10

0

0.00

7.34

4.06

12.75

9.46

4.30

252.91

5.91

3.45

K-2000-200-0.5-10

4

846.44

1.37

2.30

12.34

4.12

2.94

112.94

1.04

1.66

K-2000-200-0.9-10

0

0.00

5.99

2.44

12.39

8.78

3.54

211.80

4.77

2.31

K-2000-20-0.5-25

10

155.30

0.00

0.00

21.72

5.98

7.21

122.22

0.00

0.00

K-2000-20-0.9-25

10

408.79

0.00

0.00

21.60

1.46

1.54

222.00

0.07

0.22

K-2000-200-0.5-25

10

138.88

0.00

0.00

21.88

1.53

2.11

121.82

0.04

0.13

K-2000-200-0.9-25

10

572.74

0.00

0.00

21.18

2.70

2.76

215.21

0.02

0.05

4.49

1.46

6.65

3.15

3.35

1.25

Average

Table 2: Computational results for the grid digraph instances.

LB-Benders’
AvgGAP (%)

StDev (%)

Time (s)

AvgGAP (%)

LPH

32

Test set

#opt

G-32x32-20-0.5

10

7.31

0.00

0.00

3.21

4.16

9.20

3.80

0.22

0.70

G-32x32-20-0.9

10

8.63

0.00

0.00

3.43

5.38

7.49

5.01

0.69

1.67

G-32x32-200-0.5

10

6.83

0.00

0.00

3.35

1.56

2.72

3.88

3.11

4.72

G-32x32-200-0.9

10

9.79

0.00

0.00

3.22

3.90

5.89

5.33

0.00

0.00

G-20x50-20-0.5

10

6.66

0.00

0.00

2.86

2.71

5.94

3.96

0.42

1.34

G-20x50-20-0.9

10

9.14

0.00

0.00

3.00

1.80

2.93

4.76

0.76

1.10

G-20x50-200-0.5

10

6.23

0.00

0.00

3.24

2.54

5.09

4.47

0.78

2.45

G-20x50-200-0.9

10

13.43

0.00

0.00

3.15

2.33

4.43

5.43

0.58

0.74

G-5x200-20-0.5

10

397.06

0.00

0.00

2.92

5.29

4.89

10.97

0.10

0.31

G-5x200-20-0.9

9

670.84

0.28

0.89

2.91

4.64

1.69

19.83

0.36

0.87

G-5x200-200-0.5

10

153.69

0.00

0.00

2.97

4.82

3.57

8.75

0.29

0.66

G-5x200-200-0.9

8

1059.09

0.20

0.50

3.01

8.00

3.73

22.34

0.32

0.57

G-44x44-20-0.5

10

23.52

0.00

0.00

10.36

0.97

1.92

13.15

0.81

1.42

G-44x44-20-0.9

10

29.43

0.00

0.00

10.32

3.92

8.06

15.50

0.55

1.04

G-44x44-200-0.5

10

23.00

0.00

0.00

9.77

5.05

4.02

14.58

0.00

0.00

G-44x44-200-0.9

10

38.13

0.00

0.00

9.53

2.70

3.23

19.98

0.13

0.22

G-20x100-20-0.5

10

34.77

0.00

0.00

10.90

2.81

5.26

20.38

0.00

0.00

G-20x100-20-0.9

10

90.28

0.00

0.00

10.76

5.41

4.98

29.39

0.61

1.13

G-20x100-200-0.5

10

47.27

0.00

0.00

11.39

1.64

1.97

20.17

0.25

0.66

G-20x100-200-0.9

10

59.16

0.00

0.00

10.53

3.37

3.27

26.32

0.21

0.37

G-5x400-20-0.5

1

3444.71

2.57

1.98

10.26

6.82

3.90

62.50

2.14

1.62

G-5x400-20-0.9

0

0.00

7.76

3.95

10.20

10.83

3.16

150.45

5.67

2.89

G-5x400-200-0.5

1

2719.17

5.24

4.32

10.27

8.67

3.59

79.37

3.94

3.17

G-5x400-200-0.9

0

0.00

11.50

3.45

9.93

13.27

3.75

249.81

8.19

2.24

1.15

0.63

4.69

4.36

1.26

1.24

Average

Time (s)

AMU
StDev (%)

Time (s)

AvgGAP (%)

StDev (%)

With respect to Karaşan instances (Table 1), the average gaps referred to the solutions provided by LB-Benders’, AMU and LPH are up to, respectively, 7.47%, 10.06% and 5.79% for
the instances with 1000 vertices (see K-1000-20-0.9-5). For the instances with 2000 vertices,
the average gaps referred to the solutions provided by LB-Benders’, AMU and LPH are up to,
respectively, 25.77%, 22.13% and 18.15% (see K-2000-200-0.9-5). Notice that the average gaps
of AMU over all Karaşan instances is 6.65%, while that of LPH is only 3.35%. In fact, the
average gaps of the solutions provided by LPH are smaller than those of AMU for all the sets
of instances considered. It can also be observed that the smaller the value of ω is, the larger the
average gaps achieved by the three algorithms are. Furthermore, for the hardest instances (with
ω = 5), the average gaps of the solutions provided by LPH are smaller than or equal to those of
LB-Benders’ (except for K-1000-200-0.5-5).
Regarding Coco instances (Table 2), it can be seen that the average optimality gaps referred
to the solutions provided by LB-Benders’, AMU and LPH are at most, respectively, 11.50%,
13.27% and 8.19% (see G-5x400-200-0.9). Also in this case, the average gaps of the solutions
provided by LPH are smaller than those of AMU for all the sets of instances (except for G32x32-200-0.5). The average optimality gap of LB-Benders’ over all Coco instances is very
small (1.15%), while that of LPH is very close to this value (1.26%). It can also be observed
that the instances based on 5x400 grids are much harder to solve than the other grid instances.
Moreover, the average relative gaps referred to the solutions provided by LPH is always smaller
than those of LB-Benders’ for the hardest grid instances.
For both benchmarks, LPH clearly outperforms AMU in terms of the quality of the solutions
obtained. In fact, the heuristic is even able to achieve better upper bounds than LB-Benders’ at
solving some instance sets, especially the hardest ones. Furthermore, LPH required significantly
smaller computational effort than LB-Benders’. Therefore, LPH arises as an effective and time
efficient heuristic to solve Karaşan and Coco instances. One may note that, although the bounds
provided by AMU are not as good as those given by LPH, the 2-approximation procedure performs within tiny average computational times when compared with LB-Benders’, especially
for the hardest instances. Thus, the results suggest that AMU should be considered in the cases
where time efficiency is preferable to the quality of the solutions.
Our computational results also suggest that, for both benchmarks, instances generated with a
higher degree of uncertainty (in particular, δ = 0.9) tend to become more difficult to be handled
33

by LB-Benders’ and LPH. As pointed out in related works [11, 16], high δ values can increase
the occurrence of overlapping cost intervals and, thus, decrease the number of dominated arcs.
As a consequence, the task of finding a robust path becomes more difficult. Such behaviour does
not apply to AMU, as it simply solves R-SP instances in specific scenarios that do not rely on
the amplitude of the cost intervals.
In Tables 3a and 3b, we detail the improvement of LPH over AMU in terms of the bounds
achieved for Karaşan and Coco instances, respectively. The first column displays the name of
each instance set, and the second one shows the number of times (out of 10) that LPH gives
better bounds than AMU. The third and fourth columns show, respectively, the minimum and the
maximum percentage improvements given by 100 ·

UBamu −UBlph
,
UBamu

while the last two columns give

the average and the standard deviation (over the 10 instances in each set) of these values. Notice
that the percentage improvement assumes a negative value whenever AMU gives a better bound
than LPH.
Regarding Karaşan instances (Table 3a), the percentage improvement is up to 21.47% (see
K-2000-20-0.5-25). In fact, AMU only overcomes LPH on two instances from the whole benchmark, one from K-1000-20-0.9-25 and other from K-2000-200-0.9-25. For the grid digraph
instances (Table 3b), the percentage improvement is up to 29.31% (see G-32x32-20-0.5). Moreover, AMU gives better bounds than LPH only on 13 out of the 240 instances tested. We could
not identify a precise pattern on these instances that might indicate why AMU performs better.
However, most of them belong to instance sets based on square-like grids (such as 32x32 and
44x44). Thus, we conjecture that the balance between the number of lines and columns in the
corresponding grids plays a role in such behaviour.

34

Table 3: Details on the improvement of LPH over AMU for the two benchmarks of R-RSP instances.

(b) Grid digraph instances.

(a) Layered and acyclic digraph instances.
LPH Improvement
Test set

#Better

Min (%)

Max (%)

LPH Improvement

Avg (%)

StDev (%)

Test set

#Better

Min (%)

Max (%)

Avg (%)

StDev (%)
9.17

35

K-1000-20-0.5-5

10

0.00

9.79

4.10

3.59

G-32x32-20-0.5

10

0.00

29.31

3.94

K-1000-20-0.9-5

10

0.60

9.62

4.51

3.22

G-32x32-20-0.9

9

-5.49

20.17

4.69

7.95

K-1000-200-0.5-5

10

0.68

8.15

3.52

2.26

G-32x32-200-0.5

7

-11.21

0.00

-1.73

3.71

K-1000-200-0.9-5

10

2.06

12.49

6.14

3.28

G-32x32-200-0.9

10

0.00

18.21

3.90

5.89

K-1000-20-0.5-10

10

0.00

7.79

2.99

2.56

G-20x50-20-0.5

10

0.00

18.89

2.29

5.97

K-1000-20-0.9-10

10

0.00

12.10

4.52

3.20

G-20x50-20-0.9

9

-2.40

8.89

1.03

3.14

K-1000-200-0.5-10

10

0.00

4.18

1.27

1.51

G-20x50-200-0.5

9

-8.41

15.57

1.70

6.14

K-1000-200-0.9-10

10

1.33

12.16

4.45

2.97

G-20x50-200-0.9

9

-1.04

12.78

1.77

4.13

K-1000-20-0.5-25

10

0.00

11.90

3.12

4.52

G-5x200-20-0.5

10

0.00

14.34

5.20

4.89

K-1000-20-0.9-25

9

-2.47

10.39

2.10

3.94

G-5x200-20-0.9

10

2.58

8.01

4.29

1.75

K-1000-200-0.5-25

10

0.00

7.27

1.27

2.71

G-5x200-200-0.5

10

0.00

11.14

4.54

3.51

K-1000-200-0.9-25

10

0.00

5.68

1.13

1.89

G-5x200-200-0.9

10

1.22

12.15

7.70

3.82

K-2000-20-0.5-5

10

0.41

9.88

4.29

3.20

G-44x44-20-0.5

8

-3.95

5.77

0.15

2.40

K-2000-20-0.9-5

10

1.34

8.01

4.13

2.09

G-44x44-20-0.9

9

-3.29

23.26

3.40

7.95

K-2000-200-0.5-5

10

0.39

7.15

3.86

2.21

G-44x44-200-0.5

10

0.00

11.05

5.05

4.02

K-2000-200-0.9-5

10

1.61

8.25

4.86

2.22

G-44x44-200-0.9

9

-0.47

7.45

2.56

3.32

K-2000-20-0.5-10

10

0.00

9.80

3.52

2.81

G-20x100-20-0.5

10

0.00

14.09

2.81

5.26

K-2000-20-0.9-10

10

1.48

6.72

3.80

1.79

G-20x100-20-0.9

10

0.00

11.06

4.85

4.25

K-2000-200-0.5-10

10

0.00

5.66

3.12

1.95

G-20x100-200-0.5

10

0.00

5.80

1.40

1.80

K-2000-200-0.9-10

10

1.04

8.19

4.23

2.31

G-20x100-200-0.9

8

-0.66

7.65

3.17

3.38

K-2000-20-0.5-25

10

0.00

21.57

5.98

7.21

G-5x400-20-0.5

10

1.27

10.58

4.80

2.87

K-2000-20-0.9-25

10

0.00

3.91

1.39

1.60

G-5x400-20-0.9

10

1.59

13.90

5.42

3.65

K-2000-200-0.5-25

10

0.00

6.46

1.49

2.14

G-5x400-200-0.5

10

0.16

10.92

4.88

3.63

K-2000-200-0.9-25

9

-0.14

7.20

2.68

2.78

G-5x400-200-0.9

10

1.72

11.72

5.53

3.26

6.2. The Robust Set Covering problem (RSC)
In all of the algorithms regarding RSC, we used CPLEX to handle the ILP formulation I2 ,
defined by (88)-(90), whenever a classical SC instance had to be solved. We also used CPLEX
to solve each master problem in LB-Benders’ and the heuristic formulation H2 , defined by (93)(97).
6.2.1. Benchmarks description
In our experiments, we considered three benchmarks of instances from the literature of RSC,
namely Beasley, Montemanni and Kasperski-Zieliński benchmarks [6]. The three of them are
based on classical SC instances from the OR-Library [57]. However, the way the column cost
intervals are generated differs from benchmark to benchmark.
Regarding Beasley instances, let Φ j represent the cost of a column j ∈ J in the original SC
instance, and let 0 < δ < 1 be a continuous value used to control the level of uncertainty referred
to an RSC instance. For each j ∈ J , the corresponding cost interval [l j , u j ] is generated by
uniformly selecting random integer values l j and u j in the ranges [(1 − δ) · Φ j , Φ j ] and [Φ j , (1 +
δ) · Φ j ], respectively. These instances are named B.<SCinst>-δ, where <SCinst> stands for the
name of the original SC instance set considered. For each original instance of the classical SC,
we considered three RSC instances, one for each value δ ∈ {0.1, 0.3, 0.5}. In total, 75 instances
from Beasley benchmark were used in our experiments.
In Montemanni instances, the column costs of the original SC instances are discarded, and,
for each column j ∈ J , the corresponding cost interval [l j , u j ] is generated as follows. First, a
random integer value u j is uniformly chosen in the range [0, 1000], and, then, a random integer
value l j is uniformly selected in the range [0, u j]. These instances are named M.<SCinst>-1000,
where <SCinst> is the name of the original SC instance set used. Each original SC instance
considered gives the backbone to generate three RSC instances, and a total of 75 instances from
Montemanni benchmark were used in our experiments.
Kasperski-Zieliński benchmark also consider classical SC instances without the original column costs. In these instances, the cost interval [l j , u j ] of each column j ∈ J is generated as
follows. First, a random integer value l j is uniformly chosen in the range [0, 1000], and, then,
a random integer value u j is uniformly selected in the range [l j , l j + 1000]. These instances are
named KZ.<SCinst>-1000, where <SCinst> is the name of the original SC instance set used.
Each of the SC instances considered gives the backbone to generate three RSC instances, and
36

a total of 75 instances from Kasperski-Zieliński benchmark were used in our experiments. In
summary, 225 RSC instances were considered in the experiments.
6.2.2. Results
Table 4 shows the computational results regarding the three benchmarks of RSC instances
considered. The first column displays the name of each instance set, while the second one gives
(i) the number of instances solved at optimality by LB-Benders’ within 3600 seconds, over (ii)
the cardinality of the corresponding instance set. The average wall-clock processing time (in
seconds) spent in solving these instances at optimality are given in the third column. This entry
is filled with a dash if no instance in the group was solved at optimality. The fourth and fifth
columns show, respectively, the average and the standard deviation (over all the instances in
each set) of the relative optimality gaps given by 100 ·

UBb −LBb
UBb .

Recall that LBb and U Bb are,

respectively, the best lower and upper bounds obtained by LB-Benders’ for a given instance.
The sixth column displays the average wall-clock processing time (in seconds) of AMU. The
seventh column shows the average (over all the instances in each set) of the relative gaps given
by 100 ·

UBamu −LBb
UBamu ,

where U Bamu is the best upper bound obtained by AMU for a given instance.

The standard deviation of these gaps is given in the eighth column. Likewise, the ninth column
shows the average wall-clock processing time of LPH, and the last two columns give the average
and the standard deviation (once again, over all the instances in each set) of the gaps given by
100 ·

UBlph −LBb
UBlph .

Accordingly, U Blph is the robustness cost of the solution obtained by LPH for a

given instance.
As for R-RSP, the gaps referred to the solutions obtained by AMU and LPH consider the (not
necessarily optimal) lower bounds obtained by LB-Benders’ within 3600 seconds of execution.
Thus, these gaps may overestimate the actual gaps between the cost of the solutions obtained and
the cost of optimal ones.
From the results, it can be seen that the average gaps of the solutions provided by LPH are
smaller than those referred to AMU for all the sets of instances tested. Furthermore, for the
hardest instances (Kasperski-Zieliński benchmark), the average gaps of the solutions provided
by LPH are even smaller than those of LB-Benders’. As discussed in [6], Kasperski-Zieliński
instances are especially challenging, mostly because of the high probability of overlap between
arbitrary cost intervals in these instances.
37

Table 4: Computational results for the three benchmarks of RSC instances.

LB-Benders’
Time (s)

AvgGAP (%)

AMU
StDev (%)

Time (s)

AvgGAP (%)

LPH

Beasley set

#opt

StDev (%)

Time (s)

AvgGAP (%)

StDev (%)

B.scp4-0.1

10/10

1.03

0.00

0.00

0.23

4.24

4.92

0.21

0.59

1.86

B.scp5-0.1

10/10

3.32

0.00

0.00

0.34

9.01

8.27

0.42

2.60

3.62

38

B.scp6-0.1

5/5

2.23

0.00

0.00

0.88

8.02

7.41

0.64

1.43

3.19

B.scp4-0.3

10/10

9.82

0.00

0.00

0.24

5.24

3.46

0.44

0.98

1.12

B.scp5-0.3

10/10

28.23

0.00

0.00

0.34

6.21

2.61

0.92

1.78

2.62

B.scp6-0.3

5/5

12.18

0.00

0.00

1.08

2.44

2.70

1.05

1.63

1.51

B.scp4-0.5

10/10

93.98

0.00

0.00

0.29

3.56

2.12

0.64

1.20

1.49

B.scp5-0.5

10/10

94.20

0.00

0.00

0.34

5.38

4.33

1.21

0.87

1.00

B.scp6-0.5

5/5

22.57

0.00

0.00

1.00

4.08

4.21

1.16

1.44

2.23

0.00

0.00

5.35

4.45

1.39

2.07

Average

LB-Benders’
Montemanni set

StDev (%)

Time (s)

Time (s)

M.scp4-1000

27/30

598.94

0.04

0.14

0.23

1.13

0.78

0.61

0.05

0.16

M.scp5-1000

30/30

481.98

0.00

0.00

0.21

1.00

0.90

0.70

0.01

0.04

M.scp6-1000

15/15

13.90

0.00

0.00

0.42

0.78

0.94

0.80

0.06

0.14

0.01

0.05

0.97

0.87

0.04

0.11

LB-Benders’
Kasperski-Zieliński set

#opt

K.scp4-1000

0/30

K.scp5-1000

0/30

K.scp6-1000

3/15

Average

Time (s)

AvgGAP (%)

LPH

#opt

Average

AvgGAP (%)

AMU
StDev (%)

Time (s)

AMU

AvgGAP (%)

StDev (%)

0.00

14.25

2.93

0.00

8.63

3.45

1881.73

2.95

3.13

8.61

3.17

Time (s)

AvgGAP (%)

StDev (%)

LPH

AvgGAP (%)

StDev (%)

Time (s)

AvgGAP (%)

StDev (%)

3.08

14.27

2.73

124.86

12.90

2.62

2.90

8.63

3.45

44.93

7.99

3.01

11.96

4.04

2.90

115.31

2.77

2.82

8.98

3.03

7.89

2.82

Notice that LPH clearly outperforms AMU in terms of the quality of the solutions obtained
and requires significantly smaller computational effort than LB-Benders’. In fact, for most of the
instance sets considered, the average execution times of LPH are comparable to those of AMU.
Therefore, LPH arises as an effective and time efficient heuristic in solving the three benchmarks
of RSC instances tested. Nevertheless, we highlight that AMU should still be considered in the
cases where time efficiency is preferable to the quality of the solutions, especially for the more
challenging instances.
Table 5: Details on the improvement of LPH over AMU for the three benchmarks of RSC instances.

LPH Improvement
Test set

#Better

Min (%)

Max (%)

Avg (%)

StDev (%)

B.scp4-0.1

10/10

0.00

12.50

3.66

5.05

B.scp5-0.1

10/10

0.00

20.83

6.53

8.33

B.scp6-0.1

5/5

0.00

15.00

6.69

6.79

B.scp4-0.3

10/10

0.00

11.76

4.29

3.57
2.98

B.scp5-0.3

10/10

0.00

8.06

4.47

B.scp6-0.3

4/5

-2.50

6.52

0.80

3.37

B.scp4-0.5

10/10

0.52

5.36

2.39

1.42

B.scp5-0.5

9/10

-1.52

13.64

4.52

5.06

B.scp6-0.5

5/5

0.00

6.58

2.70

2.94

M.scp4-1000

30/30

0.17

3.30

1.08

0.79

M.scp5-1000

30/30

0.00

3.51

0.99

0.88

M.scp6-1000

15/15

0.00

2.87

0.72

0.94

KZ.scp4-1000

29/30

-0.04

4.59

1.56

1.33

KZ.scp5-1000

29/30

-0.08

3.13

0.71

0.80

KZ.scp6-1000

14/15

-0.13

4.25

1.29

1.61

In Table 5, we detail the improvement of LPH over AMU in terms of the bounds achieved
for the three benchmarks of RSC instances. The first column displays the name of each instance
set, and the second one shows (i) the number of times LPH gives better bounds than AMU,
over (ii) the cardinality of the corresponding instance set. The third and fourth columns show,
respectively, the minimum and the maximum percentage improvements given by 100·

UBamu −UBlph
,
UBamu

while the last two columns give the average and the standard deviation (over all the instances in
each set) of these values. These percentage improvements assume negative values whenever
39

AMU gives better bounds than LPH.
Regarding Beasley instances, the percentage improvement is up to 20.83% (see B.scp5-0.1).
In fact, AMU only overcomes LPH on two instances from the whole benchmark, one from
B.scp6-0.3 and other from B.scp5-0.5. With respect to Montemanni instances, the percentage improvement is up to 3.51% (see M.scp5-1000), and LPH always gives better bounds than
AMU. Regarding Kasperski-Zieliński instances, the percentage improvement is at most 4.59%
(see KZ.scp4-1000), and AMU overcomes LPH on three instances, one from each instance set.
We could not identify any specific pattern on the instances for which AMU outperforms LPH.
However, such behaviour is only verified in 5 out of the 225 instances tested.

7. Concluding remarks
In this study, we proposed a novel heuristic approach to address the class of interval robusthard problems, which is composed of robust optimization versions of classical NP-hard combinatorial problems. We applied this new technique to two interval robust-hard problems, namely the
Restricted Robust Shortest Path problem (R-RSP) and the Robust Set Covering problem (RSC).
To our knowledge, the former problem was also introduced in this study.
In order to evaluate the quality of the solutions obtained by our heuristic (namely LPH), we
adapted to R-RSP and to RSC a logic-based Benders’ decomposition algorithm (referred to as
LB-Benders’), which is a state-of-the-art exact method to solve interval data min-max regret
problems in general. We also compared the results obtained by the proposed heuristic with a
widely used 2-approximation procedure, namely AMU.
Regarding R-RSP, the computational experiments showed the heuristic’s effectiveness in solving the two benchmarks of instances considered. For the layered and acyclic digraph instances,
the average relative gaps of LB-Benders’ and AMU were, respectively, 4.49% and 6.65%, while
that of LPH was only 3.35%. For the grid digraph instances, the average relative gaps of LBBenders’, AMU and LPH were, respectively, 1.15%, 4.69% and 1.26%. Moreover, the average
processing times of LPH were much smaller than those of LB-Benders’ for both benchmarks
considered and remain competitive with those referred to AMU for most of the instances. In addition, LPH was able to provide better bounds than AMU for 465 out of the 480 R-RSP instances
tested.
With respect to RSC, the results show that the average gaps of the solutions provided by LPH
40

were smaller than those referred to AMU for all the sets of instances from the three benchmarks
used in the experiments. Moreover, LPH achieved better primal bounds than LB-Benders’ for the
hardest instances (Kasperski-Zieliński benchmark) and was able to provide better bounds than
AMU for 220 out of the 225 RSC instances tested.
The results point out to the fact that the proposed heuristic framework may also be efficient in
finding optimal or near-optimal solutions for other interval robust-hard problems, which can be
explored in future studies. Other directions of future work remain open. For instance, research
can be conducted to close the conjecture that the heuristic framework can be applied to the
wider class of interval data min-max regret problems with compact constraint sets addressed in
[25, 26]. Future works can also add to our framework local search strategies, such as Local
Branching [58], to further improve the quality of the solutions obtained by the heuristic.

Acknowledgments
This work was partially supported by the Brazilian National Council for Scientific and Technological Development (CNPq), the Foundation for Support of Research of the State of Minas
Gerais, Brazil (FAPEMIG), and Coordination for the Improvement of Higher Education Personnel, Brazil (CAPES).

References
[1] P. Kouvelis, G. Yu, Robust Discrete Optimization and Its Applications, Kluwer Academic Publishers, Boston, 1997.
[2] J. C. Spall, Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control, Wiley, New
York, 2003.
[3] I. Averbakh, Computing and minimizing the relative regret in combinatorial optimization with interval data, Discrete Optimization 2 (4) (2005) 273–287.
[4] R. Montemanni, A Benders decomposition approach for the robust spanning tree problem with interval data, European Journal of Operational Research 174 (3) (2006) 1479–1490.
[5] R. Montemanni, J. Barta, L. M. Gambardella, The robust traveling salesman problem with interval data, Transportation Science 41 (3) (2007) 366–381.
[6] J. Pereira, I. Averbakh, Exact and heuristic algorithms for the interval data robust assignment problem, Computers
& Operations Research 38 (8) (2011) 1153–1163.
[7] H. Yaman, O. E. Karaşan, M. Ç. Pinar, The robust spanning tree problem with interval data, Operations Research
Letters 29 (1) (2001) 31–40.
[8] R. Montemanni, L. M. Gambardella, The robust shortest path problem with interval data via Benders decomposition, 4OR 3 (4) (2005) 315–328.

41

[9] A. Kasperski, Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach (Studies in Fuzziness
and Soft Computing), Springer Berlin, 2008.
[10] V. G. Deineko, G. J. Woeginger, Pinpointing the complexity of the interval min-max regret knapsack problem,
Discrete Optimization 7 (4) (2010) 191–196.
[11] J. Pereira, I. Averbakh, The robust set covering problem with interval data, Annals of Operations Research 207 (1)
(2013) 217–235.
[12] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H.
Freeman & Co., New York, NY, USA, 1979.
[13] G. Handler, I. Zang, A dual algorithm for the constrained shortest path problem, Networks 10 (4) (1980) 293–309.
[14] H. Aissi, C. Bazgan, D. Vanderpooten, Minmax and minmax regret versions of combinatorial optimization problems: A survey, European Journal of Operational Research 197 (2) (2009) 427–438.
[15] I. Averbakh, On the complexity of a class of combinatorial optimization problems with uncertainty, Mathematical
Programming 90 (2) (2001) 263–272.
[16] O. E. Karaşan, M. Ç. Pinar, H. Yaman, The robust shortest path problem with interval data, Tech. rep., Bilkent
University, Ankara, Turkey (2001).
[17] R. Montemanni, J. Barta, L. M. Gambardella, Heuristic and preprocessing techniques for the robust traveling
salesman problem with interval data, Tech. rep., Dalle Molle Institute for Artificial Intelligence (2006).
[18] J. Hooker, G. Ottosson, Logic-based Benders decomposition, Mathematical Programming 96 (1) (2003) 33–60.
[19] A. A. Coco, A. C. Santos, T. F. Noronha, Scenario-based heuristics with path-relinking for the robust set covering
problem, in: Proceedings of the XI Metaheuristics International Conference (Agadir, Marocco, 2015), 2015, pp.
1–8.
[20] G. Yu, On the max-min 0-1 knapsack problem with robust optimization applications, Operations Research 44 (2)
(1996) 407–415.
[21] H. Aissi, C. Bazgan, D. Vanderpooten, Approximation of min-max and min-max regret versions of some combinatorial optimization problems, European Journal of Operational Research 179 (2) (2007) 281–290.
[22] M. J. Feizollahi, I. Averbakh, The robust (minmax regret) quadratic assignment problem with interval flows, INFORMS Journal on Computing 26 (2) (2014) 321–335.
[23] A. Kasperski, P. Kobylański, M. Kulej, P. Zieliński, Minimizing maximal regret in discrete optimization problems
with interval data, in: Issues in Soft Computing. Decisions and Operations Research, O. Hryniewicz, J. Kacprzyk,
D. Kuchta (eds.), Akademicka Oficyna Wydawnicza EXIT, Warszawa, 2005, pp. 193–208.
[24] A. Kasperski, P. Zieliński, An approximation algorithm for interval data minmax regret combinatorial optimization
problems, Information Processing Letters 97 (5) (2006) 177–180.
[25] E. Conde, A 2-approximation for minmax regret problems via a mid-point scenario optimal solution, Operations
Research Letters 38 (4) (2010) 326–327.
[26] E. Conde, On a constant factor approximation for minmax regret problems using a symmetry point scenario, European Journal of Operational Research 219 (2) (2012) 452 – 457.
[27] A. B. Chassein, M. Goerigk, A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem, European Journal of Operational Research 244 (3) (2015) 739 –
747.

42

[28] A. Kasperski, P. Zieliński, On the existence of an FPTAS for minmax regret combinatorial optimization problems
with interval data, Operations Research Letters 35 (4) (2007) 525–532.
[29] J. F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik
4 (1) (1962) 238–252.
[30] A. M. Geoffrion, Generalized Benders decomposition, Journal of Optimization Theory and Applications 10 (4)
(1972) 237–260.
[31] D. McDaniel, M. Devine, A modified Benders’ partitioning algorithm for mixed integer programming, Management Science 24 (3) (1977) 312–319.
[32] T. L. Magnanti, R. T. Wong, Accelerating Benders decomposition: Algorithmic enhancement and model selection
criteria, Operations Research 29 (3) (1981) 464–484.
[33] M. Fischetti, D. Salvagnin, A. Zanette, A note on the selection of Benders’ cuts, Mathematical Programming
124 (1-2) (2010) 175–182.
[34] L. Assunção, A. C. Santos, T. F. Noronha, R. Andrade, On the finite optimal convergence of logic-based Benders’
decomposition in solving 0-1 min-max regret optimization problems with interval costs, Lecture Notes in Computer
Science 9849 (1) (2016) 1–12.
[35] Y. P. Aneja, V. Aggarwal, K. P. K. Nair, Shortest chain subject to side constraints, Networks 13 (2) (1983) 295–302.
[36] J. Beasley, N. Christofides, An algorithm for the resource constrained shortest path problem, Networks 19 (4)
(1989) 379–394.
[37] R. Hassin, Approximation schemes for the restricted shortest path problem, Mathematics of Operations Research
17 (1) (1992) 36–42.
[38] Z. Wang, J. Crowcroft, Quality-of-Service routing for supporting multimedia applications, IEEE on Selected Areas
in Communications 14 (7) (1996) 1228–1234.
[39] G. Apostolopoulos, R. Guérin, S. Kamat, S. K. Tripathi, Quality of Service based routing: A performance perspective, SIGCOMM Computer Communication Review 28 (4) (1998) 17–28.
[40] L. Santos, J. Coutinho-Rodrigues, J. R. Current, An improved solution algorithm for the constrained shortest path
problem, Transportation Research Part B: Methodological 41 (7) (2007) 756–771.
[41] H. Joksch, The shortest route problem with constraints, Journal of Mathematical Analysis and Applications 14 (2)
(1966) 191–197.
[42] I. Dumitrescu, N. Boland, Improved preprocessing, labeling and scaling algorithms for the weight-constrained
shortest path problem, Networks 42 (3) (2003) 135–153.
[43] X. Zhu, W. E. Wilhelm, A three-stage approach for the resource-constrained shortest path as a sub-problem in
column generation, Computers & Operations Research 39 (2) (2012) 164–178.
[44] L. D. P. Pugliese, F. Guerriero, A survey of resource constrained shortest path problems: Exact solution approaches,
Networks 62 (3) (2013) 183–200.
[45] M. J. Rosenhead, M. Elton, S. K. Gupta, Robustness and optimality as criteria for strategic decisions, Operational
Research Quarterly 23 (4) (1972) 413–431.
[46] P. Zieliński, The computational complexity of the relative robust shortest path problem with interval data, European
Journal of Operational Research 158 (3) (2004) 570–576.
[47] D. Catanzaro, M. Labbé, M. Salazar-Neumann, Reduction approaches for robust shortest path problems, Computers

43

& Operations Research 38 (11) (2011) 1610–1619.
[48] R. Montemanni, L. M. Gambardella, A. V. Donati, A branch and bound algorithm for the robust shortest path
problem with interval data, Operations Research Letters 32 (3) (2004) 225–232.
[49] J. K. Cochran, A. M. Uribe, A set covering formulation for agile capacity planning within supply chains, International Journal of Production Economics 95 (2) (2005) 139–149.
[50] A. Caprara, M. Fischetti, P. Toth, D. Vigo, P. L. Guida, Algorithms for railway crew management, Mathematical
Programming 79 (1) (1997) 125–141.
[51] S. Ceria, P. Nobili, A. Sassano, Set covering problem, in: Annotated Bibliographies in Combinatorial Optimization,
M. DellAmico, F. Maffioli and S. Martello (eds.), Wiley, 1997, pp. 415–428.
[52] A. Caprara, P. Toth, M. Fischetti, Algorithms for the set covering problem, Annals of Operations Research 98 (1)
(2000) 353–371.
[53] A. A. Coco, J. C. A. Júnior, T. F. Noronha, A. C. Santos, An integer linear programming formulation and heuristics
for the minmax relative regret robust shortest path problem, Journal of Global Optimization 60 (2) (2014) 265–287.
[54] R. Montemanni, L. M. Gambardella, An exact algorithm for the robust shortest path problem with interval data,
Computers & Operations Research 31 (10) (2004) 1667–1680.
[55] K. Sugiyama, S. Tagawa, M. Toda, Methods for visual understanding of hierarchical system structures, IEEE
Transactions on Systems, Man & Cybernetics 11 (2) (1981) 109–125.
[56] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Elsevier, New York, 1976.
[57] J. E. Beasley, OR-Library: Distributing test problems by electronic mail, The Journal of the Operational Research
Society 41 (11) (1990) 1069–1072.
[58] M. Fischetti, A. Lodi, Local branching, Mathematical Programming 98 (1-3) (2003) 23–47.

44

