# BORWin: Exact algorithm based on a Bi-Objective Relaxation for Window-constrained problems

Christian Artigues, Pascale Bendotti, Alexandre Heintzmann, Sandra Ulrich

Ngueveu, Cécile Rottner

► To cite this version:

Christian Artigues, Pascale Bendotti, Alexandre Heintzmann, Sandra Ulrich Ngueveu, Cécile Rottner.
BORWin: Exact algorithm based on a Bi-Objective Relaxation for Window-constrained problems.
2025. hal-05269754

HAL Id: hal-05269754

https://edf.hal.science/hal-05269754v1

Preprint submitted on 15 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# BORWin: Exact algorithm based on a Bi-Objective Relaxation for Window-constrained problems

Christian Artigues, Pascale Bendotti, Alexandre Heintzmann, Sandra U. Ngueveu, Cécile Rottner

September 19, 2025

## Abstract

A mixed integer maximization problem involving several additional constraints defined with both a lower and an upper bound is considered. It is assumed that one of such constraints is more restrictive than the others. As it can be seen as a resource window constraint, it defines the so-called window-constrained problem. From a bi-objective perspective, a 2-phase algorithm, called BORWin, is devised. It stands for Bi-Objective Relaxation for Window-constrained problems. The first phase is generic for any window-constrained problem and provides a family of upper bounds based on a bi-objective relaxation of the additional constraints. It is shown that the latter bounds strongly relate to the Lagrangian dual bounds. The second phase is derived for a variant involving a graph structure, namely the window-constrained longest-path problem on an acyclic graph. The aim is to take advantage of the upper bounds to devise an efficient label extension algorithm. It is shown that complementary upper bounds could be derived to further improve performance in some special cases. A typical example is when the additional constraints have special knapsack structures. This is the case for the Hydro-Unit Commitment problem with a single plant (1-HUC). From numerical experiments for the 1-HUC, BORWin appears to be very efficient compared to state-of-the-art approaches.

# 1 Introduction

Consider a mixed integer problem of the form:

$$ (P) \quad \begin{array}{ll} \max_{x} & cx \\ \text{s.t.} & x \in X \end{array} \qquad (1) $$

$$ \beta \le \gamma x \le \alpha \qquad (2) $$

$$ \tilde{\beta}_k \le \tilde{\gamma}^k x \le \tilde{\alpha}_k \qquad k \in \{1, \dots, K\} \qquad (3) $$
where $X \subset \mathbb{R}^n$, $\alpha, \tilde{\alpha}_k, \beta, \tilde{\beta}_k$ are real numbers and $\gamma, \tilde{\gamma}^k$ are vectors of $\mathbb{R}^n$.

Subset $X$ is a set of admissible solutions such that the corresponding sub-problem:

$$ (SP) \quad \max_{x} cx \\ \text{s.t.} \quad x \in X \qquad (4) $$

is considered efficiently solved, while (2) and (3) are additional constraints. Constraint (2) is defined as the main additional constraint and can be arbitrarily chosen. The rational behind is to pick among the additional constraints one that is particularly structuring for the problem.

In particular, the main additional constraint is defined with both a lower and an upper bound: if quantity $\gamma x$ is regarded as a resource, the main additional constraint can be considered as a window constraint. Such a type of constraints is scarcely addressed in the literature and remains hard to handle. For example, if set $X$ corresponds to the feasible set of a shortest path problem, and constraints (2)-(3) correspond to a window for each vertex $k$ of the underlying graph, then we obtain a Window-Constrained Shortest Path Problem (WCSP), a generalization of the classical Resource-Constrained Shortest Path Problem (RCSPP). Here the main additional constraint can be chosen as the window constraint associated with the vertex having the most restrictive bounds. While the RCSPP is well-solved by state-of-the-art methods [29], the WCSP has been less considered in the literature as discussed in Section 2.

If we relax additional constraints (3), we obtain problem (R), defined as problem (SP) combined with the main additional constraint (2).

A standard technique, such as a Lagrangian relaxation, can be performed on this main additional constraint, producing a sub-problem of the form

$$ \max_{x \in X} cx + \mu\gamma x \qquad (5) $$

where $\mu$ is the lagrangian multiplier. Such a subproblem can also be viewed from a bi-objective perspective [12]: it maximizes a vector of two (conflicting) values, $V_1(x) = cx$ and $V_2(x) = \gamma x$, under constraint set $X$. The bi-objective relaxation of (R) is thus as follows:

$$ (BOR) \quad \max_{x} (cx, \gamma x) \\ \text{s.t.} \quad x \in X \qquad (6) $$

In this paper, we look at the problem from the bi-objective perspective. The aim is to propose a novel algorithm to solve problems with structure (P), and in particular the acyclic longest-path, namely the Window-Constrained Longest Path Problem on an Acyclic Graph (AWCLPP). The algorithm is called BOR-Win (Bi-Objective Relaxation for Window-constrained problems) and includes two phases. The first phase is generic for any problem (P) and provides a family
of upper bounds based on a bi-objective relaxation. It is inspired by the two-phase algorithm used in bi-objective optimization [37, 39]. The second phase relies on the graph structure of the AWCLPP to implicitly enumerate feasible solutions using the family of bounds provided by the first phase by means of a label extension algorithm.

Numerical experiments show that the BORWin algorithm is efficient compared to two alternative approaches. The first one is a Mixed-Integer Linear Program solved by CPLEX and the second one is a standard RCSPP algorithm, as considered in the literature. This comparison is carried out on a case study corresponding to the single-plant Hydro Unit Commitment Problem (1-HUC). Roughly speaking the 1-HUC is to maximize the daily power generation over a discrete time horizon with water flowing through turbines of a plant from an upstream reservoir. The optimization of such turbines can be modeled as an acyclic longest-path problem. Moreover, the total volume of water must satisfy window constraints at each time period. At the last time period of the horizon, tighter volume windows are applied on some reservoirs (referred to as target volumes), in order to efficiently manage the water stock throughout a yearly horizon. Such a target volume constraint can thus be defined as the main additional constraint.

As the plant is operated on a set of discrete points, the 1-HUC can alternatively be seen as a special case of the Nested Multiple-Choice Knapsack problem (NMCKP) [4], which is itself an NP-hard particular case of the AWCLPP. This generalization of the knapsack problem features a partition $\{N_i, i \in K\}$ of the objects, such that only one object from each set $N_i$ can be selected. It features also M knapsack constraints, which are nested over the sets $N_i$ of the partition, in the sense that for each $m \in \{1, ..., M\}$, the $m^{th}$ knapsack constraint involves objects in a union $S_m$ of sets $N_i$, such that $S_m$ is included in the set $S_{m+1}$ corresponding to the $m+1$ knapsack constraint.

There are strong links between the NMCKP and the 1-HUC. Indeed, each window upper-bound of the 1-HUC can be identified as a knapsack constraint [22], and as the resource cumulates from one time period to the other, such window constraints have a nested structure. The multiple-choice aspect comes from the fact that at each time period, exactly one operating point must be chosen among a discrete set of feasible points. Similarly, the window lower-bounds can be seen as demand constraints [9], i.e., knapsack constraints with negative coefficients and such constraints can also be identified to an NMCKP. Hence, the second phase of the BORWin algorithm will exploit both the AWCLPP and the NMCKP structures in the problem considered.

Three sets of 1-HUC instances are considered: the first is a large set of realistic instances from the literature, the second is a large set of realistic EDF instances, and the last is a set of difficult instances inspired by the EDF ones. As the first instance set will prove very easy to solve in our context, the numerical experiments will focus on the second and the third one.

Section 2 presents a literature review on bi-objective optimization, its relationship with decomposition methods and algorithms for the RCSPP, WCSPP and their longest-path variants. In Section 3, theoretical results and algorithms
for the first phase of the BORWin algorithm are described. Section 4 is devoted to the second phase of BORWin. In Section 5, the 1-HUC problem is described, along with a dedicated state of the art and a mathematical programming formulation. Finally, in Section 6 experimental results showing the efficiency of the BORWin algorithm on the 1-HUC problem are provided. Concluding remarks are drawn in Section 7.

# 2 Literature review

Since Phase I of our approach is based on a bi-objective relaxation of the problem, bi-objective optimization basics are recalled in Section 2.1. As stated in the introduction, decomposition techniques can be used alternatively with dedicated multiobjective reformulations. Related works are presented in Section 2.2. We mentioned that phase II of the BORWin algorithm provides an exact solution framework for the AWCLPP, which can be modeled as an acyclic WCSPP. Therefore, Section 2.3 formally presents the WCSPP and its bi-objective relaxation as well as related work. Finally Section 2.4, focuses on the AWCLPP specificities.

## 2.1 Bi-objective optimization and two-phase method

Consider a bi-objective problem where $V_1(x)$ and $V_2(x)$ denote the first and second objective values of a solution $x$, to be maximized. We first recall below the definitions of Pareto-dominance, Pareto-optimality and Pareto-supported solutions. Consider two solutions $x$ and $x'$. Solution $x$ weakly Pareto-dominates solution $x'$, denoted by $x \ge_p x'$, if $V_1(x) \ge V_1(x')$ and $V_2(x) \ge V_2(x')$. Solution $x$ strongly Pareto-dominates $x'$, denoted by $x >_p x'$, if it weakly Pareto-dominates $x'$ and if in addition $V_1(x) > V_1(x')$ or $V_2(x) > V_2(x')$. A solution $x$ is Pareto-optimal if no other solution strongly dominates it. A Pareto-optimal solution is Pareto-supported if it belongs to the convex hull of the feasible points in the objective space.

The two-phase method was first introduced in [37] as a procedure to solve bi-objective combinatorial optimization problems and more specifically in [39] to solve the bi-objective knapsack problem. This classical method is particularly efficient to deal with two or even three objectives when the corresponding problem with a single objective is easy to solve. The rationale behind this method is that the space search is dramatically reduced once Pareto-supported solutions are defined. In the bi-objective case, the two-phase method works as follows. The first phase obtains Pareto-supported solutions, i.e., Pareto-optimal solutions that form the convex envelope of the solutions' space. The main idea is to solve the problem with the two objectives aggregated into a single one by convex combination. Solving the problem with various convex combination parameters can yield to different Pareto-supported solutions. The second phase is to use an enumeration algorithm, to obtain remaining Pareto-optimal solutions within the reduced search space defined by the Pareto-supported solutions. The
most straightforward approach is the enumeration of all Pareto-optimal solu-
tions, which can be done with a Branch & Bound variant [37, 39] or dedicated
algorithms [15]. As the number of Pareto-optimal solutions can be exponential,
such algorithms can become very time-consuming.

One way to reduce the computational time is to generate only a subset of the
Pareto-optimal solutions, for instance with a *K*-best solutions algorithm [16].
The downside is that the set of solutions may not contain the most adequate
Pareto-optimal solution with respect to the decision maker's preferences, or even
may not contain any feasible solution for problem (P).

## 2.2 Decomposition and multi-objective perspective

In [10], the authors consider a very general integer program featuring efficiently solved subproblems combined with a (small) set of coupling constraints. Problem (P) corresponds to a particular case of such problems, as it features a single subproblem with only one main additional constraint among many additional constraints. To handle such a generic class of problems, the authors propose a multiobjective reformulation, coupling constraints are seen as resource constraints, and the subproblems feasible sets as non-dominated Pareto solutions. Then, they propose a family of solution algorithms based on successive disjunctive linear programs solved via a MILP solver, and subproblem solutions to generate new non-dominated Pareto solutions. This approach is very generic and enables to handle problems with multiple subproblems coupled by several constraints. Clearly the algorithms performed at each iteration are expected to be quite time-consuming as they rely in particular on solving an MILP.

In the particular case of constraint structures such that one of the coupling
constraint is more important than the others, more dedicated approaches can
be considered. Typically, in [12], an algorithm generating a dual bound for a
linear problem with a single side-constraint is proposed. In this case, the con-
sidered subproblem (SP) should be formulated in such a way that no binary
variables are necessary. Network problems with totally unimodular constraint
matrices are an example of such linear problems. The algorithm relies on it-
erated solutions of subproblem of the form (5), where the dual multiplier $\mu$ is
updated using reduced cost of non-basic variables from the simplex solution of
subproblem (SP). However, the paper does not propose to exploit the obtained
lower bound in a second phase, whereas our approach relies on an efficient di-
chotomy from the two-phase method (see in Section 4 for details). Contrarily
to our approach, this algorithm may feature degeneracy, and slow convergence.
Nevertheless, the algorithm in [12] could be compared to the first phase of our
algorithm as it provides similar bounds.

In [38], the considered problem features nested lower and upper bounds
constraints on integer variables, with a separable Lipschitz-continuous objective
function. The constraints are a special case of the constraints of problem (P),
as all variable coefficients $\gamma$, $\tilde{\gamma}^k$ are 0 or 1. For this special case, the authors
propose an exact polynomial-time decomposition algorithm based on recursion
arguments.
## 2.3 The Window-Constrained Shortest Path Problem

Let $G = (U, A)$ denote a directed graph with a set of vertices $U$ and a set of arcs $A$. Each vertex $u \in U$ is associated with a window constraint $[\bar{R}_u, \bar{R}_u]$ and each arc $a \in A$ has a value $V(a)$ and a resource consumption $R(a)$. Let $\pi = (U_\pi, A_\pi)$ denote a path traversing vertex set $U_\pi \subseteq U$ and arc set $A_\pi \subseteq A$. Let $\pi_{uv}$ denote its sub-path from vertex $u \in U_\pi$ to vertex $v \in U_\pi$. Let $R(\pi)$ denote the resource consumption of path $\pi$, while $V(\pi)$ denote its value: with $R(\pi) = \sum_{a \in A_\pi} R(a)$ and $V(\pi) = \sum_{a \in A_\pi} V(a)$. Consider a particular origin vertex $s \in U$ and a target vertex $p \in U$. Let $\Pi_{sp}$ denote the set of paths from $s$ to $p$. A path $\pi \in \Pi_{sp}$ satisfying window constraints is such that $\bar{R}_u \le R(\pi_{su}) \le \bar{R}_u, \forall u \in U_\pi$. The WCSPP consists in finding a path from $s$ to $p$ of minimum value satisfying the window constraints. The problem with a single window constraint on the target vertex is also known as the doubly-constrained shortest path problem [32]. As an extension of the RCSPP, the WCSPP is NP-hard.

In the survey [36], a state-of-the-art review of different shortest path variants is provided. The most studied related variant is the RCSPP and its elementary version (ERCSPP) [23, 5, 29], corresponding to the WCSPP with no lower bound on the window constraint usually solved by label setting algorithms [11]. A label can be assimilated to a partial path issued from $s$. Label setting algorithm are based on dynamic programming and use the following Pareto-dominance between two labels, for minimization.

**Dominance rule 1.** If two feasible partial paths $\pi_{su}$ and $\pi'_{su}$ towards the same vertex $u$ are such that

$$V(\pi_{su}) \le V(\pi'_{su}) \text{ and } R(\pi_{su}) \le R(\pi'_{su})$$

then $\pi'$ can be discarded as it cannot lead to a better solution than $\pi$.

Two-phase Lagrangian relaxation approaches have also been considered to solve the RCSPP [35, 13]. Focusing on a single window constraint only on vertex $p$, the first phase computes the dual Lagrangian bound $\max_{\lambda \ge 0} \min_{\pi \in \Pi_{sp}} V(\pi) + \lambda R(\pi) - \lambda \bar{\pi}_p$. The second phase aims at closing the gap using this bound for pruning and/or guiding the search in an enumeration procedure, that could be either a branch-and-bound algorithm [13], a K-shortest path algorithm [35] or a label setting algorithm [14].

Consider now the bi-objective relaxation of the WCSPP, obtained by ignoring all window constraints except the one on $p$. The latter constraint is transformed into an objective, thus yielding the bi-objective shortest path problem (BOSPP) $\min\{V(\pi), R(\pi)\}$, s.t. $\pi \in \Pi_{sp}$. The link between the RCSPP and the BOSPP is often explicit in the aforementioned two-phase Lagrangian relaxation-based methods. The Lagrangian optimization results in two successive non-dominated paths $\pi^1$ and $\pi^2$ in the convex hull of the bi-objective solution space. Path $\pi^1$ such that $R(\pi^1) \le \bar{R}_p$ provides an UB and path $\pi^2$ such that $R(\pi^2) > \bar{R}_p$ defines the Lagrangian LB. The second phase aims at searching the optimal path between those two to close the gap. Even though Lagrangian relaxation is not necessarily used in recent state-of-the-art approaches
for the RCSPP, the A*-based algorithm in [3] is shown to be one of the most competitive algorithm to date for the RCSPP with a single constraint on the terminal vertex. It is also used to solve the BOSPP.

More specifically, little work has been reported on the RCSPP with equality constraints, or window constraints (WCSPP). In [32], a heuristic using Lagrangian relaxation and BOSPP concepts is proposed to solve the WCSPP with only one window constraint at the last vertex. The heuristic builds an s, p-cut in the network and enumerates, for each origin vertex of an arc of the cut, the non-dominated points of the Lagrangian relaxation by means of a parametric shortest path procedure. Then, the partial solutions are extended by enumeration. In [6], the problem is solved by branch-and-bound where the Lagrangian relaxation bound is used to prune the search tree.

The three-phase algorithm described in [40] solves the RCSPP with window constraints on acyclic graphs. The main idea is to extend the graph, such that if multiple paths lead to the same vertex from the source, a new vertex is created for each of these paths. Once the graph has been extended in this way, the problem is solved with a pseudo-polynomial time algorithm. In [24], a two-phase method is proposed to solve the elementary doubly-constrained shortest path problem. The first phase performs various reductions on the graph by estimating minimum and maximum consumptions along any elementary path. The second phase is an adaptation of the depth-first search with pruning strategies of [26].

In [1, 2], the WCSPP is considered for an application to the 1-HUC, which will be addressed in Section 5. The authors propose a label extension algorithm inspired by the standard RCSPP algorithms. Because of lower bound constraints present in the WCSPP, the dominance rule 1 does not hold in general. Therefore additional sufficient conditions must be added, thus seriously weakening its effectiveness. The authors remark that under a restricting condition the following dominance rule can be applied :

**Dominance rule 2.** Given two feasible partial paths $\pi$ and $\pi'$ from $s$ to $u$, let $\Gamma(u)$ be the set of vertices reachable from $u$, if $\pi$ and $\pi'$ satisfy the condition of dominance rule 1 and $\pi$ satisfies the following condition.

$$R(\pi) \geq \underline{R}(v), \forall v \in \Gamma(u)$$

then $\pi'$ can be discarded.

## 2.4 The Window-Constrained Longest Path Problem on an acyclic graph

For the sake of consistency with the literature, we presented in the previous section the shortest path variants of the problems WCSPP and BOSPP. Note that the WCSPP reduces to the window-constrained longest path problem where the value is to be maximized subject to the graph being acyclic. In the sequel we will consider the Acyclic Window-Constrained Longest Path Problem (AWCLPP) as it directly applies to the 1-HUC problem considered as case study. When graph $G$, defined in section 2.3, is acyclic, solving the WCSPP on graph
<figure><img src="image_2.png" /><figcaption>Figure 1: Graph for an instance of the AWCLPP</figcaption></figure>

<table><caption>Table 1: Resource consumption and values of the paths in the graph displayed in Figure 1</caption><thead><tr><th></th><th colspan="5">path</th><th>value</th></tr></thead><tbody><tr><td>π<sub>1</sub></td><td>s</td><td>1</td><td>3</td><td>2</td><td>p</td><td rowspan="2">32</td></tr><tr><td></td><td>0</td><td>5</td><td>10</td><td>25</td><td>35↑</td></tr><tr><td>π<sub>2</sub></td><td>s</td><td>3</td><td>p</td><td></td><td></td><td rowspan="2">27</td></tr><tr><td></td><td>0</td><td>15</td><td>21</td><td></td><td></td></tr><tr><td>π<sub>3</sub></td><td>s</td><td>1</td><td>2</td><td>p</td><td></td><td rowspan="2">31</td></tr><tr><td></td><td>0</td><td>5</td><td>15</td><td>25</td><td></td></tr><tr><td>π<sub>4</sub></td><td>s</td><td>1</td><td>3</td><td>p</td><td></td><td rowspan="2">33</td></tr><tr><td></td><td>0</td><td>5</td><td>10</td><td>16↓</td><td></td></tr><tr><td>π<sub>5</sub></td><td>s</td><td>3</td><td>2</td><td>p</td><td></td><td rowspan="2">26</td></tr><tr><td></td><td>0</td><td>15</td><td>30↑</td><td>40↑</td><td></td></tr></tbody></table>

$G$ is equivalent to solving the AWCLPP on the same graph $G$, with opposite arc values $-V(a)$, $\forall a \in A$. Even when $G$ is acyclic, the problem remains NP-hard. Likewise the Acyclic Bi-Objective Longest Path Problem (ABOLPP) can be defined.

**Example 1.** Figure 1 displays an AWCLPP instance with 5 vertices. Each vertex has a window constraint except vertex $s$. Values $(V(a), R(a))$ appear near each arc $a$. Table 1 gives the value of each path of this graph and the resource consumption for each node of each path. Each consumption exceeding a window upper bound (resp. lower bound) is marked with ↑ (resp. ↓). Here only $\pi_2$ and $\pi_3$ are feasible and the longest feasible path is $\pi_3$.

Both the WCSPP and the AWCLPP fall into the general scheme of problem (P) presented in section 1. The feasible set $X$ is the set of paths in $\Pi_{sp}$ and problem (SP) is the easy-to-solve shortest/longest path problem on an acyclic graph. The main additional window constraint (2) is on terminal vertex $p$, and the remaining additional window constraints on other vertices. Without loss of generality, the main additional window constraint could be defined on any vertex of the graph, not necessarily the terminal one.

Note that a single window constraint on the terminal vertex is considered
in all the references cited in Section 2.3 but [1, 2]. In this paper we look for the extended case where window constraints occur on several vertices. Even if the first stage of the proposed approach computes also the lagrangian lower bound by ignoring all window constraints except the one on the last vertex, it is obtained for general problem (P) by an original bi-objective relaxation algorithm. Then, the second stage uses a label extension algorithm as in [1, 2], except that we guide the search and perform additional pruning thanks to the lagrangian bound and further enhancements.

# 3 Phase I of BORWin: bi-objective relaxation upper bounds

In this section, we present the first phase relative to BORWin. The first phase computes a family of upper bounds for (P) based on the considered bi-objective relaxation (BOR). This bi-objective relaxation is presented in details in Section 3.1. The properties yielding the family of upper bounds and the tightest of them are established in Section 3.2. The first-phase algorithm is presented in Section 3.3. An illustrative application of the first-phase algorithm to the AWCLPP is presented in 3.4.

## 3.1 Bi-objective relaxation

The idea of the bi-objective relaxation is the following: additional constraints (3) are relaxed, and the main additional constraint (2) is turned into an optimization criterion.

To do so, consider an optimal solution $x_{SP}^*$ of subproblem (SP). We distinguish 2 cases :

* “Locally Infeasible by Default" (LID), if $\gamma x_{SP}^* \le \beta$

* “Locally Infeasible by Excess" (LIE), if $\gamma x_{SP}^* > \alpha$

The term “locally” means that feasibility is only related to (SP) plus constraint (2). Side-constraints (3) are ignored in this phase and will be dealt with in the second phase of the method.

Without loss of generality, we suppose in the following that we are in the LID case. Indeed, if we were in the LIE case, we could rewrite constraint (2) as $-\alpha \le -\gamma x \le -\beta$ and obtain a new formulation of problem (P) falling into the LID case. Supposing the LID case, in this section we consider the following relaxation of (P):

$$ (R) \begin{array}{ll} \max_{x} & cx \\ \text{s. t.} & x \in X \\ & \beta \le \gamma x \end{array} \qquad (7) $$
The results described in this section will rely on the bi-objective relaxation (BOR) of (R), maximizing the vector of objective cx and $\gamma x$.

Each objective component is denoted by $V_1(x) = cx$ and $V_2(x) = \gamma x$.

**Definition 1 (Aggregated value).** Consider a scalar $\delta \in \mathbb{R}^+$. For a solution $x \in X$, we define $\mu_\delta(x) = V_1(x) + \delta \cdot V_2(x)$ as the aggregated value of a solution $x$ considering weight $\delta$ for objective $V_2(x)$. By convention when $\delta = +\infty$, $\mu_{+\infty}(x) = V_2(x)$.

Note that when $\delta = 0$ then $\mu_0(x) = V_1(x)$. Note also that a solution $x$ is Pareto-supported if there exists $\delta$ such that $\mu_\delta(x) \ge \mu_\delta(x')$ for any other solution $x'$, because in this case $x$ belongs to the convex hull of the feasible points in the objective space.

We provide the following definition for the Pareto-equality and Pareto-difference.

**Definition 2 (Pareto-equality and Pareto-difference).** Consider two solutions $x$ and $x'$. Solutions $x$ and $x'$ are Pareto-equal, denoted by $x =_p x'$, if $V_1(x) = V_1(x')$ and $V_2(x) = V_2(x')$. Otherwise, $x \neq_p x'$.

In the following, we denote by $S$ the ordered set of Pareto-supported solutions in increasing value of the first objective $V_1(x) = cx$. We do not consider in $S$ two solutions with the exact same values, meaning that for two solution $x$ and $x'$ in $S$, $x \neq_p x'$.

## 3.2 Family of upper-bounds

In this section, we first define some properties for the solutions of (BOR). Besides, we show that one can obtain a family of upper bounds for (P) using solutions of (BOR) with a well-chosen $\delta$ for their aggregated value. In Section 3.3, we will use such results to efficiently compute these bounds in the first phase of the BORWin algorithm. The second phase will also exploit these results to restrict the search space.

First, we can introduce an upper bound for $V_1(x^*)$ with $x^*$ the optimal solution of (P).

**Property 1.** Let $x$ be the Pareto-supported solution maximizing $V_1(x)$ and $x^*$ the optimal solution of (P). Then, $V_1(x)$ is a valid upper bound for $V_1(x^*)$.

*Proof.* As $x^*$ is a valid solution for (P), it is also a valid solution for (BOR). Consequently, if $V_1(x^*) > V_1(x)$, then $x$ cannot be the Pareto-supported solution maximizing $V_1(x)$. We then deduce $V_1(x^*) \le V_1(x)$. $\square$

However, it is possible to provide a tighter upper bound. We first introduce the following lemma.

**Lemma 1.** Let $x_1, x_2$ and $x_3$ be three solutions of (BOR) with $V_1(x_1) \le V_1(x_2) \le V_1(x_3)$. Consider that these solutions do not dominate each other. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_3)$. If $\mu_\delta(x_2) < \mu_\delta(x_1)$ then $x_2$ cannot be Pareto-supported.
*Proof.* Solutions $x_1, x_2$ and $x_3$ do not dominate each other, therefore : $V_2(x_1) \ge V_2(x_2) \ge V_2(x_3)$. Thus, if we suppose $\mu_\delta(x_2) < \mu_\delta(x_1)$, then for any $\delta' > \delta$, $\mu_{\delta'}(x_2) < \mu_{\delta'}(x_1)$, and as $\mu_\delta(x_1) = \mu_\delta(x_3)$, for any $\delta' < \delta$, $\mu_{\delta'}(x_2) < \mu_{\delta'}(x_3)$. Therefore, $x_2$ is not Pareto-supported. $\square$

We introduce **Properties 2** to **4** and **Theorem 1** to provide a tighter upper bound for $V_1(x^*)$.

**Property 2.** Let $(x_1, x_2)$ be a pair of consecutive solutions in $S$. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_2)$. For each solution $x$ of (BOR), $\mu_\delta(x) \le \mu_\delta(x_1)$.

The proof of **Property 2** is in Appendix A.1.

**Corollary 1.** Let $(x_1, x_2)$ be a pair of solutions in $S$. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_2)$. Let $x_3$ be the solution maximizing $\mu_\delta(x_3)$. If solution $x_3 \neq_p x_1$ and $x_3 \neq_p x_2$, then $V_1(x_3) \in]V_1(x_1); V_1(x_2)[$ and $V_2(x_3) \in]V_2(x_2); V_2(x_1)[$. If solution $x_3 =_p x_1$ or $x_3 =_p x_2$, then $x_1$ and $x_2$ are consecutive solutions in $S$.

*Proof.* The proof of **Property 2** indicates that if $x_3 \neq_p x_1$ and $x_3 \neq_p x_2$, then $V_1(x_3) \in]V_1(x_1); V_1(x_2)[$ and $V_2(x_3) \in]V_2(x_2); V_2(x_1)[$. Otherwise, either $x_1$ or $x_2$ cannot be Pareto-supported, which yields a contradiction.

In the case $x_3 =_p x_1$ or $x_3 =_p x_2$, then clearly there cannot be any Pareto-supported solution $x_4$ with $V_1(x_4) \in]V_1(x_1); V_1(x_2)[$ as it cannot be part of the solutions' convex hull in the objective space. $\square$

For a solution $x$ of (BOR), provided we know the value $V_2(x)$, Property 2 gives an upper bound of $V_1(x)$ for each pair of consecutive solutions in $S$. As the optimal solution $x^*$ of (P) is also a feasible solution of (BOR), it also applies to $x^*$. As we do not know the value $V_2(x^*)$, we cannot use this property directly to bound $V_1(x^*)$. However, we know that $V_2(x^*) \in [\beta; \alpha]$ from the main additional constraint (2).

**Property 3.** Let $(x_1, x_2)$ be a pair of consecutive solutions in $S$. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_2)$. Let $\bar{V}_1(x_1, \delta) = \mu_\delta(x_1) - \delta \cdot \beta$. Then $\bar{V}_1(x_1, \delta)$ is an upper bound for the value of the optimal solution $V_1(x^*)$ of (P).

*Proof.* As $x^*$ is a feasible solution of (P), it is also a feasible solution of (BOR). From **Property 2**, we know that $V_1(x^*) \le \mu_\delta(x_1) - \delta \cdot V_2(x^*)$. As $x^*$ is a feasible solution of (P), then $V_2(x^*) \in [\beta; \alpha]$, meaning that $V_2(x^*) \ge \beta$. Hence, we can deduce $V_1(x^*) \le \mu_\delta(x_1) - \delta \cdot V_2(x^*) \le \mu_\delta(x_1) - \delta \cdot \beta$. $\square$

Note that in the objective space $(V_1, V_2)$, the bound $\bar{V}_1(x_1, \delta)$ corresponds to the value on the first objective of the point located at the intersection of line $V_2 = \beta$ and the line going through $x_1$ and $x_2$.

**Property 3** provides an upper bound that can be computed independently from the values $V_1(x^*)$ and $V_2(x^*)$.
**Property 4.** Let $(x_1, x_2)$ be a pair of consecutive solutions in $S$. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_2)$. For any $R \le \beta$, $\bar{V}_1(x_1, \delta) \le \mu_\delta(x_1) - \delta \cdot R$. For any $R > \beta$, $\mu_\delta(x_1) - \delta \cdot R$ is not a valid upper bound for the value of the optimal solution $V_1(x^*)$ of (P)

*Proof.* Clearly, for any $R \le \beta$, $\mu_\delta(x_1) - \delta \cdot \beta \le \mu_\delta(x_1) - \delta \cdot R$. Consider the case $R > \beta$. As $V_2(x^*) \ge \beta$, there is no guarantee that $R \le V_2(x^*)$. Hence, it is not possible to deduce $V_1(x^*) \le \mu_\delta(x_1) - \delta \cdot R$ as done in **Property 3**. The following **Example 2** gives a counter-example to complete this proof in the case $R > \beta$. $\square$

Property 4 shows that for any choice of $R \ne \beta$, the bound $\mu_\delta(x_1) - \delta \cdot R$ would either be invalid or looser than $\bar{V}_1(x_1, \delta)$.

**Example 2.** Consider an instance of problem (P) with no additional constraints besides the main one, with bounds $\beta = 3$ and $\alpha = 5$. Consider this problem to have three distinct solutions denoted $x_1, x_2$ and $x_3$ with the following values: $(7, 1), (5 - \epsilon, 3)$ where $5 - \epsilon < 4$ and, $(2, 6)$, respectively. Note that we are in the case LID. Indeed, the optimal solution $x_{SP}^*$ of the sub-problem (SP) is $x_1$, as $V_1(x_1) > V_1(x_2) > V_1(x_3)$ and $V_2(x_1) = 1 < \beta = 3$.

Consider now the bi-objective relaxation problem (BOR) associated with (P). All the following explanations are illustrated in Figure 2.

Clearly, solutions $x_1$ and $x_3$ are Pareto-supported, but not $x_2$. Hence, the list of Pareto-supported solutions $S$ is $\{x_3, x_1\}$. Due to bounds $\alpha$ and $\beta$, only $x_2$ is a feasible solution of (P), meaning $x_2$ is the optimal one.

Consider $\delta = 1$, so that $\mu_\delta(x_1) = \mu_\delta(x_3)$. Let $R$ be any number such that $R > \beta$. For any value $R$, $\mu_\delta(x_1) - \delta \cdot R = 1 \cdot 7 + 1 \cdot 1 - 1 \cdot R = 8 - R$. As $R > \beta = 3$, we deduce $8 - R < 5$. For this instance, one can select $\epsilon < R - 5$ such that $V_1(x_2) = 5 - \epsilon > 8 - R$. Consequently, if $R > \beta$, one cannot deduce a valid upper bound for the value $V_1(x^*)$ of the optimal solution of (P).

From the previous **Properties 3** and **4**, we know that for a given pair $(x_1, x_2)$ of consecutive solutions in $S$, there is no $R \ne \beta$ providing a tighter upper bound than $\bar{V}_1(x_1, \delta)$. Recall that in general, the number of Pareto-supported solutions is exponential, hence there exists an exponential number of bounds. We prove in the following that it is possible to characterize the pair $(x_1, x_2)$ of consecutive solutions in $S$ that provides the tightest bound $\bar{V}_1(x_1, \delta)$.

**Definition 3.** A pair $(x_1, \delta) \in S \times \mathbb{R}^+$ is a *Pareto-supported pair* if there exists solution $x_2 \in S$ consecutive to $x_1$ in $S$ satisfying $\mu_\delta(x_1) = \mu_\delta(x_2)$.

**Theorem 1.** Let $(x_1, x_2)$ be a pair of consecutive solutions in $S$ such that $V_2(x_1) \ge \beta > V_2(x_2)$. Let $\delta$ be such that $\mu_\delta(x_1) = \mu_\delta(x_2)$. Among all Pareto-supported pairs, solution $x_1$ and value $\delta$ minimize the value $\bar{V}_1(x_1, \delta)$.

The proof of **Theorem 1** is in Appendix A.2.
<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration of Example 2</figcaption></figure>

3.3 Algorithm of Phase I

The aim of this first phase is to define upper bounds, thus defining a reduced search space. More precisely, we search for a Pareto-supported pair (x, δ), that provides the tightest bound $\bar{V}(x, \delta)$ for the value of the optimal solution $x^*$ of (P), according to the result provided in Theorem 1.

The first step is to compute $x_{SP}^*$ the optimal solution of (SP). If $V_2(x_{SP}^*) \in [\beta, \alpha]$, the algorithm stops and returns $x_{SP}^*$ and $\delta = 0$. Note that the associated upper bound is then $V_1(x_{SP}^*)$. Otherwise, one needs to find $(x_A, x_B)$ a pair of consecutive solutions in $S$ such that $V_2(x_A) \ge \beta > V_2(x_B)$.

The idea to obtain this pair of solutions is to do an enumeration of Pareto-
supported solutions following the dichotomic principle.

The steps of this enumeration are illustrated in Figure 3, where $\delta_{i,j}$ is the value such that $\mu_{\delta_{i,j}}(x_i) = \mu_{\delta_{i,j}}(x_j)$, for $(i,j) = (1,2), (3,2), (4,2), (4,5)$.

We start with two Pareto-supported solutions $x_A$ and $x_B$, not necessarily successive in $S$, such that $V_2(x_A) \ge \beta > V_2(x_B)$ as represented in Figure 3a with solutions $x_1$ and $x_2$. Let $\delta$ be such that $\mu_\delta(x_A) = \mu_\delta(x_B)$. From there, we distinguish two cases.

The first case occurs when the solution $x_C$ obtained by maximizing $\mu_\delta()$ is such that $x_C =_p x_A$ or $x_C =_p x_B$. Then, we know from Corollary 1, that $x_A$ and $x_B$ are successive in $S$. As such, we can return $x_A$, $x_B$ and $\delta$, as $(x_A, x_B)$ is a pair of consecutive Pareto-supported solutions in $S$ such that $V_2(x_A) \ge \beta > V_2(x_B)$.

In the second case, solution $x_C$ maximizing $\mu_\delta()$ is such that $x_C \neq_p x_A$ and $x_C \neq_p x_B$. Then, we know from Corollary 1, that $V_1(x_C) \in ]V_1(x_A); V_1(x_B)]$ [and
$V_2(x_C) \in ]V_2(x_B)$; $V_2(x_A)$]. In other words, $x_C$ is a Pareto-supported solution between $x_A$ and $x_B$ in $S$. If $V_2(x_C) \ge \beta$, then one can consider the two solutions $x_C$ and $x_B$ rather than $x_A$ and $x_B$ as shown in Figure 3b. Otherwise, one can consider the two solutions $x_A$ and $x_C$ rather than $x_A$ and $x_B$.

The idea is to use this new pair, $x_A$ and $x_C$ (resp. $x_B$ and $x_C$), and reuse the result of Corollary 1 either to prove both solutions to be successive in $S$, or to find a new solution $x_4$. Figure 3c and 3d show an example of the solutions $x_4$ and $x_5$ thus obtained.

<figure><img src="image_4.png" /><figcaption>Figure 3: Illustrations of the dichotomic enumeration of the first phase</figcaption></figure>

Algorithm 1 gives a pseudo-code for this first phase. Lines 4 and 6 define the first two solutions. Here the solutions maximizing respectively the first and the second objective are selected. In the case where the solution maximizing the second objective has the second objective smaller than the lower bound $\beta$, then clearly no solution of (P) will satisfy this bound, hence the algorithm stops (line 7 to 9). Lines 11 to 18 are the while loop to enumerate until the new solution is Pareto-equal to the two incumbent solutions. The updated $\delta$ value used to compute the new solution is at line 17, and the new solution is obtained at line 18. At line 19 the algorithm returns one of the two incumbent solutions as well
as the value $\delta$ used in the while loop.

**Algorithm 1 BORWin: first phase**

**Require:** A MIP of the form of (P)

1: Compute $x_{SP}^*$ the optimal solution of (SP)

2: **if** $V_2(x_{SP}^*) \in [\beta; \alpha]$ **then**

3: **return** $x_{SP}^*$, $\delta = 0$

4: $x_A = x_{SP}^*$

5: $\delta \leftarrow +\infty$

6: $x_B \leftarrow$ solution of (BOR) maximizing $\mu_\delta$()

7: **if** $V_2(x_B) < \beta$ **then**

8: No feasible solution to (P)

9: **return** Infeasible

10: $x_C \leftarrow \emptyset$

11: **while** $x_C \neq_p x_A$ and $x_C \neq_p x_B$ **do**

12: **if** $x_C \neq \emptyset$ **then**

13: **if** $V_2(x_C) \ge \beta$ **then**

14: $x_B \leftarrow x_C$

15: **else**

16: $x_A \leftarrow x_C$

17: $\delta \leftarrow \frac{V_1(x_A) - V_1(x_B)}{V_2(x_B) - V_2(x_A)}$

18: $x_C \leftarrow$ solution of (BOR) maximizing $\mu_\delta$()

19: **return** $x_A, x_B, \delta$

With solutions $x_A$, $x_B$ and value $\delta$ obtained from **Algorithm 1**, we can define a search space for the second phase. To do so, we use four valid bounds for the optimal solution $x^*$ of P.

**Definition 4 (Search space $\Omega$).** Search space $\Omega$ is defined as the set:

$$ \Omega = \left\{ x \in X \mid \beta \le V_2(x) \le \alpha, V_1(x) \le \bar{V}_1(x_A, \delta), \mu_\delta(x) \le \mu_\delta(x_A) \right\} $$

**Property 5.** Any optimal solution $x^*$ of (P) belongs to $\Omega$.

*Proof.* Clearly, $x^*$ is a valid solution of P, hence $\beta \le V_2(x^*) \le \alpha$. Then, as shown in **Property 3**, $V_1(x^*) \le \bar{V}_1(x, \delta)$. Finally, $\mu_\delta(x^*) \le \mu_\delta(x)$, otherwise there would be a contradiction with the definition of **Algorithm 1**.

<figure><img src="image_5.png" /></figure>

The following example illustrates how search space $\Omega$ can be derived from the result of **Algorithm 1**.
**Example 3.** Consider two instances of problem (P), each with five solutions, $x_1, \dots, x_5$. For each instance, solution $x_4$ is with the highest value $V_1$. The first instance is such that $V_2(x_4) < \beta$, while the second instance is such that $V_2(x_4) \in [\beta; \alpha]$. **Figure 4a** (resp. **4b**) shows search space $\Omega$ (in the bi-objective space) in grey, for the first (resp. second) instance.

<figure><img src="image_6.png" /><figcaption>Figure 4: Representation of search space $\Omega$ along with the solutions of (BOR) in the objective space</figcaption></figure>

## 3.4 Application to the AWCLPP

In this section, we present an illustrative application of Phase I using Algorithm 1 to the AWCLPP.

Consider the AWCLPP instance described in **Example 1**, **Figure 1** and **Table 1**. At line 1 of **Algorithm 1**, the longest path according to $V_1$ (arc values $V$ in the AWCLPP) gives $\pi_4 = (s, 1, 3, p)$ with $V_1(\pi_4) = V(\pi_4) = 33$. This path is infeasible by default (LID case) since $V_2(\pi_4) = R(\pi_4) = 16 < \beta = 20$, so $x_A = \pi_4$ (line 4). Then, at line 6, the computation of the longest path according to $V_2$ (resource $R$ in the AWCLPP) gives path $x_B = \pi_5 = (s, 3, 2, p)$ with $V_2(\pi_5) = R(\pi_5) = 40$, which is greater than $\beta$ so that no unfeasibility is detected and we enter the main loop. At line 17, we obtain $\delta = \frac{33-26}{40-16} = \frac{7}{24}$, which is illustrated in **Figure 7a**. For each arc $a$, we compute $\mu_\delta(a) = V_1(a) + \delta V_2(a)$, which gives the graph, displayed in **Figure 5**.

The longest path in this graph is the solution of (BOR) that maximizes $\mu_\delta()$ (line 18). We obtain path $x_C = \pi_1 = (s, 1, 3, 2, p)$ which is pareto-equal to neither $x_A$ nor $x_B$ (condition at line 11). Since $V_2(\pi_1) = 35 > \beta$ we set $x_B = \pi_1$ (line 14) and $\delta = \frac{33-32}{35-16} = \frac{1}{19}$, as illustrated in **Figure 7b**. The solution of (BOR) that maximizes $\mu_\delta()$ is computed again by computing the longest path in the graph displayed in **Figure 6**. There are two solutions that maximize this objective, namely $\pi_1 = x_B$ and $\pi_4 = x_A$ with $\mu_\delta(\pi_1) = \mu_\delta(\pi_4) = \frac{643}{19}$. Setting
<figure><img src="image_7.png" /><figcaption>Figure 5: Graph for maximization of $\mu_{\delta}$ with $\delta = \frac{7}{24}$ before the first iteration</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: Graph for maximization of $\mu_{\delta}$ with $\delta = \frac{1}{19}$ after the first iteration</figcaption></figure>

$x_C$ to one of these paths, the stop condition at line 11 is satisfied. The algorithm returns $x_A = \pi_4$, $x_B = \pi_1$ and $\delta = \frac{1}{19}$. We obtain $\bar{V}_1(\pi_4) = \frac{643}{19} - \frac{20}{19} \approx 32.7$, which gives an upper bound of 32, improving the longest path upper bound ($V_1(\pi_4) = 33$).

<figure><img src="image_9.png" /><figcaption>Figure 7: Phase I dichotomic enumeration for AWCLPP Example 1</figcaption></figure>
## 3.5 Relationship to Lagrangian and Dantzig-Wolfe relaxation

The first phase of the BORWin algorithm is described in Section 3.3 through a bi-objective perspective, but it remains closely linked to the Lagrangian duality theory. In particular, it can be shown to return the optimal solution of the Lagrangian relaxation of (R).

Indeed, suppose we dualize constraint (7), we obtain Lagrangian function $\theta$ defined for $\lambda \ge 0$:

$$ \theta(\lambda) = \max_{x \in X} cx + \lambda(\beta - \gamma x) $$

With $\text{Ext}(X) = \{x_1, ..., x_K\}$ the set of extreme points of $X$, we consider the Lagrangian minimization problem

$$ \min_{\lambda \ge 0} \theta(\lambda) = \min_{\sigma, \lambda} \sigma + \lambda\beta \\ \text{s. t.} \quad \sigma \ge (c - \lambda\gamma)x_k \quad \forall k \in \{1, ..., K\} \quad (8) $$

$$ \lambda \ge 0 \quad (9) $$

an optimal solution $\lambda^* = \arg\min_{\mu \ge 0} \theta(\lambda)$ and its linear programming dual, namely the Dantzig-Wolfe relaxation:

$$ (DW) \quad \max_{\xi} \sum_{k=1}^{K} (cx_k)\xi_k \\ \text{s. t.} \quad \sum_{k=1}^{K} \xi_k = 1 \quad (10) $$

$$ \beta \le \sum_{k=1}^{K} \xi_k \gamma x_k \quad (11) $$

$$ \xi_k \in [0, 1] \quad \forall k $$

First we give a practical lemma on the solution structure of (DW) relying on the fact that only one constraint is dualized.

**Lemma 2.** There exists an optimal solution $\xi^*$ of (DW) such that : $\exists i, j \in \{1, ..., K\}$ verifying

$$ \bullet \quad \xi_k^* = 0 \quad \forall k \ne i, j $$

$$ \bullet \quad \xi_i + \xi_j = 1 $$

$$ \bullet \quad \xi_i(\gamma x_i) + \xi_j(\gamma x_j) = \beta $$

$$ \bullet \quad \text{The value } v^* = \xi_i(cx_i) + \xi_j(cx_j) = \theta(\lambda^*) \text{ is an upper bound on the value of } (P) $$
*Proof.* The optimal solution $\xi^*$ of this relaxation corresponds to a convex combination of extreme points of $X$ that maximizes the value $\sum_{k=1}^K (cx_k)\xi_k$ while ensuring the window lower bound $\beta$.

Since there is only one dualized constraint, we can geometrically represent the solutions of problem (R) in two dimensions, in the space (value $v = cx$, resource $r = \gamma x$).

We consider the convex hull $H$ of the extreme points of $X$ in the 2-dimensional space $(v, r)$. In this space, the feasible set $F$ of (DW) corresponds to the intersection of $H$ with the half-space of equation "$r \ge \beta$".

The optimal point of (DW) will therefore correspond to the extreme point of $H$ that maximizes the value $v$. This point is at the intersection of the line "$r = \beta$" (because we are in the LID case) and a facet of $H$, defined by a segment between two extreme points $x_i$ and $x_j$ of the hull $H$ (because we are in a 2-dimensional space). $\square$

We denote by $\tilde{x}_1$ and $\tilde{x}_2$ the two extreme points with nonzero support in $\xi^*$.

In the following, we prove that the coefficient $\delta$ obtained at convergence of Phase I corresponds to an optimal solution $\lambda^*$ of the Lagrangian minimization problem. Moreover, $\tilde{x}_1$ and $\tilde{x}_2$ are optimal solutions of (BOR) maximizing $\mu_\delta$.

**Property 6.** Let $(x_A, \delta)$ be the result obtained at convergence of Algorithm 1 (when not infeasible). Then, $\mu_\delta(\tilde{x}_1) = \mu_\delta(\tilde{x}_2) = \mu_\delta(x_A)$. Moreover, $\delta \in \arg\max \theta(\lambda)$.

*Proof.* Note that the goal of Algorithm 1 is precisely to find a pair of points $x_A \in X$ and $x_B \in X$ such that:

(i) Solutions $x_A$ and $x_B$ are Pareto-supported (thus are extreme points of the convex hull $H$)

(ii) Solutions $x_A$ and $x_B$ are consecutive in the ordered set of supported-Pareto points $S$ (therefore the segment between $x_A$ and $x_B$ is a facet of $H$)

(iii) In space (value $v$, resource $r$), consider the line with equation $\theta = v + \lambda(\beta - r)$ passing through $x_A$ and $x_B$ ($\theta$ and $\lambda$ being determined by this condition). Solutions $x_A$ and $x_B$ are such that $\theta$ is minimal among pairs satisfying properties defined in (i) and (ii).

Thus, we can conclude that solutions $\tilde{x}_1, \tilde{x}_2, x_A$ and $x_B$ are all on the same line $\theta = v + \lambda(\beta - r)$, using Lemma 2. This line has slope $-\delta$, as $\delta = \frac{V_1(x_A) - V_1(x_B)}{V_2(x_B) - V_2(x_A)}$. Therefore, $\mu_\delta(\tilde{x}_1) = \mu_\delta(\tilde{x}_2) = \mu_\delta(x_A)$.

There exists $\lambda^* \in \arg\max \theta(\lambda)$ such that the slope of this line is also equal to $-\lambda^*$: indeed, if window lower bound $\beta$ decreases by one unit, a new optimal solution of (DW) can be found on the line between $\tilde{x}_1$ and $\tilde{x}_2$, with increased objective value corresponding to an optimal dual value of constraint (11). $\square$

All in all, the upper bound $V_1(x_A, \delta)$ obtained at convergence of Algorithm 1 corresponds exactly to the Lagrangian upper bound $\min_{\lambda \ge 0} \theta(\lambda)$.
## 4 Phase II of BORWin: a label-extension procedure for the AWCLPP

We consider now the AWCLPP as described in section 2.4. The second phase of the BORWin algorithm aims at solving the AWCLPP using value $\delta$ and search space $\Omega$ obtained from Algorithm 1. The dedicated label extension algorithm solves the LPP problem with objective $\mu_{\delta}(\cdot)$. This algorithm uses value $\delta$ both to guide the search and to prune sub-paths, as Lagrangian relaxation-based label extension algorithms do for the RCSPP [14].

This section is organised as follows. In section 4.1, we introduce the concept of hybrid paths and establish properties on which the algorithm efficiency relies. We provide in section 4.2 an additional upper bounding scheme when the AWCLPP has the special structure of a multiple choice knapsack with nested window constraints (NMCKP) (see definition in the introduction). The overall second-phase algorithm is described in section 4.3.

### 4.1 Properties of hybrid paths and dominance rule

We introduce the concept of hybrid paths that will be used to build feasible paths of the AWCLPP defined on graph $G = (U, A)$.

The notations used in Section 4 are the following. The set of all paths from vertex $s$ to vertex $p$ in $G$ is denoted by $\Pi_{sp}$. Any path $\pi$ in $\Pi_{sp}$ can be identified using its vertex and edge sets $\pi = (U_{\pi}, A_{\pi})$. Let $\pi_{uv}$ denote its sub-path from vertex $u \in U_{\pi}$ to vertex $v \in U_{\pi}$. The AWCLPP aims at finding a path of maximal value from $s$ to $p$ in acyclic graph $G$. Such a path must also satisfy all window constraints, i.e., $\underline{R}_u \le R(\pi_{su}) \le \bar{R}_u, \forall u \in U_{\pi}$. We also identify $V_1(\pi) = V(\pi) = \sum_{a \in A_{\pi}} V(a)$ as the value of a path $\pi \in \Pi_{sp}$ and $V_2(\pi) = R(\pi) = \sum_{a \in A_{\pi}} R(a)$ as its used resource amount.

**Definition 5 (Hybrid path $\hat{\pi}$).** For a given vertex $v \in U$, a hybrid path $\hat{\pi} \in \Pi_{sp}$ through vertex $v$ in graph $G$ is composed of two sub-paths: $\pi$ from $s$ to $v$, and $\bar{\pi}$ from $v$ to $p$. Sub-path $\pi$ satisfies the windows constraints of the AWCLPP, while $\bar{\pi}$ relaxes them and is the longest path from $v$ to $p$ according to $\mu_{\delta}(\cdot)$.

From such hybrid paths, it is possible to define upper bounds of value $\mu_{\delta}(\pi)$ for any path $\pi$ feasible for the AWCLPP.

**Theorem 2.** Let $\hat{\pi} = (\pi, \bar{\pi})$ be a hybrid path through vertex $v$. For any hybrid path $\hat{\pi}'$ through $v$, feasible for the AWCLPP, it holds that $\mu_{\delta}(\hat{\pi}) \ge \mu_{\delta}(\hat{\pi}')$.

*Proof.* Suppose $\mu_{\delta}(\hat{\pi}) < \mu_{\delta}(\hat{\pi}')$, then as $\hat{\pi} = (\pi, \bar{\pi})$ and $\hat{\pi}' = (\pi, \bar{\pi}')$, we deduce $\mu_{\delta}(\bar{\pi}) < \mu_{\delta}(\hat{\pi}')$. Hence, there is a contradiction, as $\bar{\pi}$ would not maximize $\mu_{\delta}(\cdot)$. $\square$

A lower bound on the value $\mu_{\delta}(\pi^*)$, with $\pi^*$ the optimal path of the AWCLPP can also be obtained.
**Theorem 3.** Let $\pi$ and $\pi^*$ be, respectively, a feasible and an optimal path for the AWCLPP. Let $\underline{\mu}_{\delta}(\pi) = V(\pi) + \delta \underline{R}(p)$. Then $\pi^*$ is such that $\mu_{\delta}(\pi^*) \ge \underline{\mu}_{\delta}(\pi)$.

*Proof.* Clearly, $V(\pi^*) \ge V(\pi)$, $R(\pi^*) \ge \underline{R}(\pi)$ and by construction $\delta \ge 0$. Hence $\mu_{\delta}(\pi^*) \ge \underline{\mu}_{\delta}(\pi) = V(\pi) + \delta \underline{R}(p)$.

□

According to Theorems 2 and 3, the following pruning rule can be enounced.

**Pruning rule 1.** Let $\pi$ be a feasible solution. For a given vertex $v$, consider a hybrid path $\hat{\pi}' = (\pi', \bar{\pi}')$ through $v$, such that $\mu_{\delta}(\hat{\pi}') \le \underline{\mu}_{\delta}(\pi)$. Then, sub-path $\pi'$ can be discarded.

Pruning rule 1 is useful for implicit enumeration algorithms such as the one proposed in Section 4.3. We also propose a weakened variant of the RCSPP dominance rule 1.

**Dominance rule 3.** If two feasible sub-paths $\pi_{su}$ and $\pi'_{su}$ from $s$ to $u$ are such that

$$R(\pi_{su}) = R(\pi'_{su}) \text{ and } V(\pi_{su}) \le V(\pi'_{su})$$

then $\pi'_{su}$ can be discarded as it cannot lead to a better solution than $\pi_{su}$.

## 4.2 Complementary upper bounds based on other underlying easily solved structures

Problem (P) has been defined as a structured problem featuring a shortest/longest path sub-structure -represented by feasible set $X$- coupled to window constraints (2) - (3). Based on such a structure, phase I of the BORWin algorithm computes a Lagrangian upper bound on a weighted combination of values $V_1$ and $V_2$.

However, other useful underlying structures may exist in (P), and such structures can also be exploited to compute upper bounds complementary to the upper bounds obtained in phase I.

Consider a subproblem (Q) $\max_{x \in Y} cx$ of (P), i.e., the solution set Y contains the feasible set of X :

$$\{x \in X | (2) - (3)\} \subset Y$$

Suppose problem (Q) is easily solved, in the sense that there exists a very efficient algorithm to obtain an optimal solution. Then, BORWin algorithm can benefit from the upper bound on (P) obtained by solving (Q).

More precisely, we suppose that the structure of (Q) is preserved by partial variable fixing, i.e., for any partial solution $\bar{x}$ - defined as a dictionary containing the following pairs (index, partial solution value for this index), problem $(Q(\bar{x}))$ remains easily solved:

$$\begin{array}{lll} (Q(\bar{x})) & v_Q(\bar{x}) = \max_{x} cx & \\ \text{s.t.} & x_i = \bar{x}_i & \forall i \in \bar{x} \end{array}$$
Then, phase II of BORWin algorithm can efficiently rely on the following
very classical result.

**Property 7.** Consider $v$ the value of a given feasible solution to (P). For any partial solution $\bar{x}$, if $v_Q(\bar{x}) \le v$ then partial solution $\bar{x}$ cannot lead to a solution with better value than $v$ (and therefore it can be "pruned").

Note that for such a bound to be complementary to the Lagrangian bound
from phase I, it is necessary that feasible set $Y$ be different from $X$.

Set $Y$ can contain a selection of window constraints (2) - (3) for which efficient algorithms are known. In the case where set $Y$ can be identified to a matroid, efficient greedy algorithms are optimal [17]. In another case where the union of (some of) these window constraints features a nested multiple-choice knapsack structure, efficient linear relaxation algorithms exist [4, 21]. Moreover, if such a nested multiple-choice knapsack structure features symmetric weights, an efficient dedicated A\* algorithm exists to obtain an integer optimal solution [21].

Returning to the AWCLPP, if the graph possesses such a special structure
$Y$, let $UB(\pi)$ denote the specific upper bound associated with the partial solu-
tion defined by a sub-path $\pi$. If no special structure exists, we can always set
$UB(\pi) = V(\pi)$. We then define the following additional pruning rule.

**Pruning rule 2.** Let $\pi$ be a feasible solution and $\pi'$ a sub-path issued from $s$. If $UB(\pi') \le V(\pi)$, then $\pi'$ can be discarded.

4.3 Algorithm of Phase II

**Algorithm 2** describes the enumeration of the second phase, which works as follows. A hybrid path $\hat{\pi} = (\pi, \bar{\pi})$ can be viewed as a label used in standard label extension algorithms. As soon as a new label/hybrid path $\hat{\pi}$ is generated, the values $V(\hat{\pi}_{sv})$, $R(\hat{\pi}_{sv})$ and $\mu_{\lambda}(\hat{\pi}_{sv})$ are stored in a list $L_v$ for each vertex $v \in U_{\hat{\pi}}$ to avoid useless recomputations. A preprocessing phase at line 1 computes the longest path $\bar{\pi}_{up}$ according to $\mu_{\delta}(\cdot)$ from each vertex $u \in U$ to $p$. The list $L$ of hybrid paths is then initialized to a unique hybrid path $(\emptyset, \bar{\pi}_{sp})$ at line 2. This corresponds to the initial label with an empty feasible sub-path and the longest path in $G$ according to $\mu_{\delta}(\cdot)$. List $L$ will be kept sorted by decreasing value $\mu_{\delta}(\cdot)$ during the whole algorithm to drive the search towards the most promising direction in terms of the Lagrangian upper bound. The best path found so far $(\pi^*)$ is initialized as the empty path at line 3. As long as $L$ is not empty, the main loop (lines 4–22) proceeds with the following steps. The first hybrid path $\hat{\pi} = (\pi, \bar{\pi})$ in $L$ is selected at line 5. Then, two cases are considered.

The first case is when $\hat{\pi}$ is feasible, which is tested at line 6 by checking
window constraints for all vertices in longest path $\bar{\pi}$. Then, lines 7–9 remove
all labels $\hat{\pi}' = (\pi', \bar{\pi}')$ in $L$ whose upper bounds $\mu_{\delta}(\hat{\pi}')$ is not larger than the
lower bound $\mu_{\delta}(\hat{\pi})$ defined by $\hat{\pi}$ (pruning rule 1). We also remove label $\hat{\pi}'$ when
$UB(\pi') \le V(\bar{\pi})$ (pruning rule 2).
The second case is when $\hat{\pi}$ is not feasible due to $\bar{\pi}$ and we consider extensions of $\pi$. A classical label extension algorithm would then consider the last vertex $u$ in the feasible sub-path $\pi$ and its extension through each arc $(u, v) \in A$. Taking advantage of the longest path already evaluated $\bar{\pi}$, we generalize this extension scheme to generate more new hybrid paths, thus obtaining feasible paths faster. For each vertex $u$ of $\bar{\pi}$ such that $\hat{\pi}_{su}$ is a feasible sub-path, which is checked at line 15, all feasible extensions of $\hat{\pi}_{su}$ via each arc $(u, v) \in A \setminus A_{\bar{\pi}}$ (the successor of $u$ in $\bar{\pi}$ can be excluded) are considered inside the loop delimited by lines 13-22. This extension, denoted by $\pi'$, is checked according to the weak dominance rule 3 against each $\pi''$ stored in list $L_v$ of feasible sub-paths that have already reached vertex $v$ (line 18). If sub-path $\pi'$ is not dominated, new hybrid path $\hat{\pi}'$ is created. Then, if the upper bounds $\mu_{\delta}(\hat{\pi}')$ and $UB(\pi')$ compared to the best known solutions do not allow to discard it via pruning rules 1 and 2, hybrid path $\hat{\pi}'$ and sub-path $\pi'$ are added to $L$ and $L_v$, respectively (lines 18-22).

## 4.4 Application to the AWCLPP

In this section, we present an illustrative application of Phase II using Algorithm 2 to the AWCLPP.

Consider again the AWCLPP instance described in **Example 1**, **Figure 1** and **Table 1**. At the first phase, described in Section 3.4, we obtained $\delta = \frac{1}{19}$.

We start the second phase with a first hybrid path maximizing $\mu_{\delta}()$. We choose $\hat{\pi}^1 = (\emptyset, \{(s, 1), (1, 3), (3, 2), (2, p)\})$. For this example, we ignore any specific upper bound $UB(\pi^1)$. We initialize list $L = [\hat{\pi}^1]$. **Figure 8a** gives the search space and the known solution at the start of the second phase. The hybrid path satisfies all windows constraints except the one of $p$ and is thus infeasible. Indeed, $R(\hat{\pi}^1) = 35$ while $\bar{R}(p) = 29$. We then remove $\hat{\pi}^1$ from $L$ and create new hybrid paths from $\hat{\pi}^1$.

* The only arc starting with $s$, different from $(s, 1)$ is $(s, 3)$. The longest path from $3$ to $p$ with $\delta = 0.053$ is $\{(3, p)\}$. Hence we have $\hat{\pi}^2 = \{(\hat{s}, 3)\}, \{(3, p)\})$ with $V(\hat{\pi}^2) = 27$ and $R(\hat{\pi}^2) = 21$.

* The only arc starting with $1$, different from $(1, 3)$ is $(1, 2)$. The longest path from $2$ to $p$ with $\delta = 0.053$ is $\{(2, p)\}$. Hence we have $\hat{\pi}^3 = \{(\hat{s}, 1), (1, 2)\}, \{(2, p)\})$ with $V(\hat{\pi}^3) = 31$ and $R(\hat{\pi}^3) = 25$.

* The only arc starting with $3$, different from $(3, 2)$ is $(3, p)$. As $p$ is the target vertex, we have $\hat{\pi}^4 = (\{(s, 1), (1, 3), (3, p)\}, \emptyset)$ with $V(\hat{\pi}^4) = 33$ and $R(\hat{\pi}^4) = 16$. However, sub-path $\pi^4$ of $\hat{\pi}^4$ does not satisfy the constraints. Indeed, this path uses 16 amount of resources from $s$ to $p$ while $\bar{R}(p) = 20$. Consequently, we discard path $\hat{\pi}^4$.

* There are no arcs starting with $2$ different from $(2, p)$.

Two hybrid paths were generated from $\hat{\pi}^1$, namely $\hat{\pi}^2$ and $\hat{\pi}^3$. By adding these hybrid paths to $L$ in decreasing values of $\mu_{\delta}()$, we have $L = [\hat{\pi}^3, \hat{\pi}^2]$. **Figure 8b** gives the search space and known solutions after the first iteration of phase
**Algorithm 2 BORWin: second phase**

**Require:** An AWCLPP graph $G = (U, A)$ and a scalar $\delta$
1: Compute $\bar{\pi}_{up}$, the longest $u-p$ path such that $\mu_{\delta}(\bar{\pi}_{up})$ is maximized, $\forall u \in U$.
2: $L \leftarrow [(\emptyset, \bar{\pi}_{sp})]$
3: $\pi^* \leftarrow \emptyset$
4: **while** $L \neq \emptyset$ **do**
5: & Pop $\hat{\pi} = (\pi, \bar{\pi})$ the first element of $L$
6: & **if** $\forall v \in U_{\bar{\pi}}, R(\hat{\pi}_{sv}) \in [\underline{R}(v), \bar{R}(v)]$ ($\hat{\pi}$ is feasible) **then**
7: & & **for** $\hat{\pi}' = (\pi', \bar{\pi}') \in L$ **do**
8: & & & **if** $\mu_{\delta}(\hat{\pi}') \le \mu_{\delta}(\hat{\pi})$ or $UB(\pi') \le V(\hat{\pi})$ **then**
9: & & & & remove $\hat{\pi}'$ from $L$
10: & & **if** $\pi^* = \emptyset$ or $V(\hat{\pi}) > V(\pi^*)$ **then**
11: & & & $\pi^* \leftarrow \hat{\pi}$
12: & **else**
13: & & **for** $u \in U_{\bar{\pi}} \setminus \{p\}$ **do**
14: & & & $\pi' \leftarrow \pi \cup \bar{\pi} \setminus \bar{\pi}_{up}$
15: & & **if** $R(\pi'_{sv}) \in [\underline{R}(v), \bar{R}(v)]$, $\forall v \in \bar{\pi} \setminus \bar{\pi}_{up}$ **then**
16: & & & **for** each arc $(u, v) \in A \setminus A_{\bar{\pi}}$ **do**
17: & & & & $\pi' \leftarrow \pi' \cup (u, v)$
18: & & **if** $\forall \pi'' \in L_v, R(\pi'') \neq R(\pi') \lor V(\pi'') > V(\pi')$ **then**
19: & & & $\hat{\pi}' \leftarrow (\pi', \bar{\pi}_{vp})$
20: & & **if** $\mu_{\delta}(\hat{\pi}') > \mu_{\delta}(\pi^*)$ and $UB(\pi') > V(\pi^*)$ **then**
21: & & & add $\hat{\pi}'$ to $L$ according to decreasing $\mu_{\delta}(\cdot)$
22: & & & add $\pi'$ to $L_v$
23: & **return** $\pi^*$
II. Hybrid path $\hat{\pi}^3$ is a feasible solution. We save $\hat{\pi}^3$ as the current best solution found $\pi^*$ and remove $\hat{\pi}^3$ from $L$. We compute the lower bound $\underline{\mu}_{\delta}(\pi^*) = V(\pi^*) + \delta \underline{R}(p) = \frac{609}{19}$. As $\mu_{\delta}(\hat{\pi}^2) = \frac{534}{19} < \underline{\mu}_{\delta}(\hat{\pi}^3)$, we can discard solution $\hat{\pi}^2$. List $L$ being now empty, the algorithm stops and returns the path corresponding to $\pi^3$ as the optimal solution.

<figure><img src="image_10.png" /><figcaption>Figure 8: Illustration of the search space explored by Phase II algorithm for Example 1</figcaption></figure>

Note that the proposed implementation is to store for each vertex $v$ a list $L_v$ containing all enumerated non-dominated feasible sub-paths from $s$ to $v$.

**Remark 1.** This implementation is particularly effective if there are many paths using the exact same amount of resource between vertex $s$ and a vertex $v$, as the lists $L_v$ at each vertex will remain small thanks to the weakened dominance rule 3. This appears when there are symmetries in resource use. This happens to be the case for the NMCKP when some weights of the items are identical.

# 5 Application to the single-plant Hydro Unit Commitment problem

The Hydro Unit Commitment (HUC) problem specific to hydroelectric plants is part of the electricity production planning problem called Unit Commitment Problem (UCP). At Electricité de France (EDF), large-scale instances of the UCP are solved on a daily basis by a Lagrangian decomposition [31]. The HUC problem is the sub-problem dedicated to the valleys and is solved using an MILP formulation [18].

In this paper the considered use-case is the single-plant HUC (1-HUC). Recall it features window constraints as main additional constraints. The idea is to see how the BORWin algorithm compares in terms of performance with classical 1-HUC approaches in the literature.
In this section, a description of the 1-HUC along with a mathematical formulation is proposed in Section 5.1. A state of the art relative to the 1-HUC focusing on dynamic programming is presented in Section 5.2. It is followed in Section 5.3 by the graph representation dedicated to model the 1-HUC as an AWCLPP.

## 5.1 Description and formulation for the 1-HUC

The 1-HUC comprises a set of units, each of which being the combination of a turbine and a generator. From the hydroelectric production principle, the units discharge a water flow from a reservoir upstream to another downstream. The reverse is also possible for some plants equipped with pumping units. The horizon $T$ is discretized in time periods. The plant operates at a finite number $|N|$ of so called operating points defined as pairs $(P_i, D_i)$, $i \in \{1, ..., |N|\}$, of the generated power and the corresponding water flow. Note that operating points do not depend on the time period. The production rate is subject to upper and lower bounds, namely ramping constraints defined by bounds $R_u$ and $R_d$, respectively. Min-up/min-down constraints apply, in the sense that when a plant is ramping up (resp. down), a minimum time delay $L$ is imposed before ramping down (resp. up). Each reservoir has an initial volume, as well as window constraints, defined by a minimum and maximum volume per time period. The time-dependent maximum and minimum capacities make it possible to account for additional intake of water in the reservoirs and also to set target volumes for specific time periods. A target volume is defined as the volume to be met at the end of a predefined period, typically a day, for water management policies. The case of a price-taker revenue maximization problem is considered. For each time period $t$ and operating point $i$, the associated revenue is the price $\Psi_{t,i}$, usually provided by the Lagrangian decomposition algorithm run daily at EDF, and defined as follows: $\Psi_{t,i} = \Lambda_t P_i + (\Phi^2 - \Phi^1)D_i$ where $\Lambda_t$ is a time-dependent unitary value of the power, and $\Phi^1$ (resp. $\Phi^2$) is the unitary value of the water in the upstream (resp. downstream) reservoir at the end of the time horizon.

In the sequel a mathematical programming formulation for the considered 1-HUC problem is introduced. Without loss of generality the proposed formulation does not feature pumps, since an instance of the 1-HUC featuring both pumps and turbines can be cast as an instance featuring only turbines [2]. Besides complementary reformulations along with bound tightening techniques from [21] are used to further enhance the formulation.

Let $x_t^i$ be the binary variable indicating that operating point $i$ is active at time period $t$. The formulation $\mathcal{M}_{HUC}$ is as follows.

$$ \max \sum_{t=1}^{T} \sum_{i \in N} \Psi_{t,i} \cdot x_t^i \qquad (12) $$
$$ \text{s.t.} \quad \underline{D}_t \le \sum_{t'=1}^{t} \sum_{i \in \mathcal{N}} D_i x_{t'}^i \le \overline{D}_t \qquad \forall t \le T \quad (13) $$

$$ x_t^i \ge x_t^{i+1} \qquad \forall t \le T, \forall i \le |\mathcal{N}| - 1 \quad (14) $$

$$ -R_d \le \sum_{i \in \mathcal{N}} D_i x_t^i - \sum_{i \in \mathcal{N}} D_i x_{t-1}^i \le R_u \qquad \forall t \in \{2, \dots, T\} \quad (15) $$

$$ \sum_{t'=t-L+1}^{t} v_{t'}^{i} \le x_{t}^{i} \qquad \forall t \in \{L, \dots, T\}, \forall i \in \mathcal{N} \quad (16) $$

$$ \sum_{t'=t-L+1}^{t} v_{t'}^{i} \le 1 - x_{t-L}^{i} \qquad \forall t \in \{L, \dots, T\}, \forall i \in \mathcal{N} \quad (17) $$

$$ v_t^i \ge x_t^i - x_{t-1}^i \qquad \forall t \in \{2, \dots, T\}, \forall i \in \mathcal{N} \quad (18) $$

$$ x_t^i \in \{0, 1\} \qquad \forall t \le T, \forall i \in \mathcal{N} \quad (19) $$

$$ v_t^i \in \{0, 1\} \qquad \forall 2 \le t \le T, \forall i \in \mathcal{N} \quad (20) $$

Objective-function (12) represents the total revenue. Inequalities (13) correspond to the tight upper bound $\underline{D}_t$ and lower bound $\overline{D}_t$ for the amount of water used since time period 1, for each time period $t \le T$. Inequalities (14) are the order constraints between the operating points. Inequalities (15) express the ramping constraints. Inequalities (16) to (18) are the min-up/down constraints as formulated in [30, 33] with additional binary variables $v_t^i$.

In this formulation, constraints (14) to (20) can be modeled as a longest-path problem in an acyclic graph. Constraints (13) for $t' < T$ are additional constraints (3), and constraint (13) for $t' = T$, which corresponds to the target volume, is the main additional constraint (2).

Note that the 1-HUC features a Nested Multiple-Choice Knapsack (NMCKP) structure: indeed, for each $t$, constraint (13) can be interpreted as a knapsack constraint with both an upper and a lower bound. The multiple-choice aspect comes from the fact that for a given time $t'$, variables $x_{t'}^i$ are incremental, therefore exactly one operating point is chosen per time period. As for the nested structure, it arises from constraints (13) where the amount of water used $\sum_{t'=1}^{t} \sum_{i \in \mathcal{N}} D_i x_t^i$ increases with $t$.

## 5.2 Related work on the HUC

The second phase of BORWin can be identified to a dynamic programming method. Such an approach has been widely used to solve the HUC. For the sake of conciseness, the presentation of the related work on the HUC in this section is focused on dynamic programming.

In [31] a two-phase approach is presented for solving the HUC problem. In the first phase, an LP for the HUC problem is considered, where various constraints are omitted. In the second phase, a dynamic programming algorithm is devised to solve the 1-HUC problem for each plant of a valley. The aim is to
get a solution as close as possible to the LP solution, while taking into account omitted constraints. The underlying graph relies on a discretization of the volume for each reservoir, thus leading to hundreds of possible values. As there is also a discretization of the time in periods, a vertex is defined for each pair of values for the volume and time and an arc between any two consecutive vertices in terms of time periods. A Bellman-Ford algorithm [7] is used to find a path in this graph. Note that even a fine discretization of the volume discards a lot of realistic paths. In this paper, the graph does not rely on a discretization of the volume.

In [27] a dynamic programming approach is defined, aiming to solve the 1-HUC with a target volume. The underlying graph is similar to the one in [31]. In order to match a discrete value of the volume and keep the instance feasible, the target volume is relaxed. Then the corresponding arcs are built by generating the feasible paths to reach the target volume, while satisfying the bounds on the volume at each time period. A backward algorithm is then proposed, aiming to maximize the value of the generated power. As we consider the 1-HUC with and also without target volume, this approach may not be practical. Indeed, if no target volumes are set, then one needs to repeat the algorithm for any possible volume value at the last time period, which can be exponential.

In [2], a decomposition algorithm is considered. The main idea is to decompose the valley into single plants, thus reducing to 1-HUC in each sub-problem. The 1-HUC problem is transformed as a WCSPP to be solved with dynamic programming [5]. For the underlying graph, there is a vertex for each operating point and each time period and an arc between any two consecutive vertices in time provided the corresponding operating points satisfy the ramping constraints. When the volumes are not restrictive, the 1-HUC is solved by a shortest path algorithm, otherwise by a labeling algorithm as mentioned in Section 2.3. In the latter case, the labeling algorithm is an adaptation of an RCSPP algorithm [5], which considers a window lower bound. It is mentioned that the use of dominant rules is crucial to efficiently reduce all possible labels. Such rules are not effective between any two labels when one satisfies the lower bound while the other does not. This would be the case when considering window constraints for the target volume.

In [19] an alternative A*-based exact algorithm, denoted HA*, is proposed by defining 1-HUC as a longest-path problem in a graph with a pseudo-polynomial number of vertices. Unfortunately, the upper bound used to guide the search is seriously weakened when min-up, min-down and ramping constraints are present. In [21], HA* is evaluated on 1-HUC instances without such constraints. Numerical experiments highlight significant improvements in the case of a window constraint on the target volume compared to state-of-the-art methods.

The 1-HUC problem is related to the subproblem dedicated to a thermal plant. It shares the ramping constraints, but obviously there is no lower bound on the volume and the definition of the min-up/min-down constraints differs slightly. In [25], the subproblem dedicated to each thermal plant is represented as an RCSPP solved with dynamic programming. Even if the underlying graph could be adapted to represent the min-up/min-down constraints for hy-
dro plants, it would not account for window contraints on the volume, which
appears to be the main issue for the 1-HUC problem.

To summarize, efficient dynamic programming-based approach proposed so-
far for the 1-HUC mostly either ignored the window constraints or the ramping
and min-up/min-down constraints. The labeling algorithm proposed in [2] con-
siders windows and ramping constraints but no min-up/min-down constraints.
In what follows, we show how the 1-HUC with windows, ramping and min-
up/min-down constraints can be modeled as an AWCLPP making it address-
able by BORWin. Compared to the labeling algorithm proposed in [2], BORWin
uses the phase I bound to guide the search, as well as pruning rules (1–2) and
dominance rule (3).

5.3 Graph representation

The 1-HUC graph representation we consider extends the ones of [2, 21] by
taking into account min-up/down constraints and allows us to model the 1-
HUC as an AWCLPP.

Let $G_H = (U_H, A_H)$ be the graph defined as follows. Each vertex $u \in U_H$
is defined as a triplet $(t, i, l)$. For this definition, $t$ is the time period, $i$ the
operating point, and $l \in \{-L+1, \dots, L-1\}$ the remaining time for min-up/down
constraints to be satisfied. Also, a source vertex and target vertex, respectively
$s=(0,0,0)$ and $p=(T+1,0,0)$ are defined. For any vertex $u = (t, i, l) \in U_H \setminus \{s,p\}$
we define the window $[\underline{R}(u) = \underline{D}_t; \overline{R}(u) = \overline{D}_t]$. For vertex $s$, the window is
$[\underline{R}(s) = 0; \overline{R}(s) = \infty]$ and for $p$ it is $[\underline{R}(p) = \underline{D}_T; \overline{R}(p) = \overline{D}_T]$.

There is an arc in $A_H$ from each vertex $(T, i, l)$ towards $p$ of value 0 and which uses 0 resource. For the following description of the arcs, consider a vertex $u=(t, i, l)$ with $t \in \{0, \dots, T-1\}$.

If $l \ge 1$ there is an arc $a \in A_H$ towards $(t+1, i, l-1)$. Similarly, if $l \le -1$
there is an arc $a \in A_H$ towards $(t+1, i, l+1)$. If $l=0$, there is an arc towards
$a \in A_H$ $(t+1, i, 0)$

If $l \ge 0$, for any $i' > i$ such that $\sum_{j=i+1}^{i'} D_i \le R_u$ there is an arc $a \in A_H$ from $u$ to $(t+1, i', L-1)$, or $(t+1, i', 0)$. Similarly, if $l \le 0$, for any $i' < i$ such that $\sum_{j=i+1}^{i'} D_i \le R_d$ there is an arc $a \in A_H$ from $u$ to $(t+1, i', -L+1)$.

The value of any arc towards a vertex $(t, i, l)$, with $t \le T$ is $\sum_{j=0}^{i} \Psi_{t,j}$, and
the resource used is $\sum_{j=1}^{i} D_j$.

**Property 8 (Polynomial number of vertices of G<sub>H</sub>).*** The number of vertices of G<sub>H</sub> is polynomial with respect to the size of the instance.

Proof. See Appendix A.3. □

**Property 9.** Any path in graph $G_H$ satisfies order constraints, ramping con-
straints and min-up/down constraints.

Proof. See Appendix A.4. □
Paths in graph $G_H$ satisfy order constraints, ramping constraints and min-up/down constraints (see Property 9) but may not satisfy the window constraints of the 1-HUC problem. Therefore, solving the AWCLPP on $G_H$ provides an optimal solution to the 1-HUC problem.

Note that the NMCKP structure of the 1-HUC involves identical weights due to operating points being the same over the time periods. It follows that the weakened dominance rule 3 inside the BORWin algorithm should eliminate many symmetric paths as mentioned in Remark 1 of Section 4.4.

The construction of graph $G_H$ is illustrated in **Figure 9** from **Example 4**.

**Example 4.** Consider an instance of the 1-HUC problem for $T = 5$ time periods. Accounting for the idle operating point, the unit operates on 3 operating points: ($D_0 = 0, P_0 = 0$), ($D_1 = 6, P_1 = 8$), ($D_2 = 5, P_2 = 6$). The ramping rates are $R_u = R_d = 6$ and the duration of the min-up/down constraints is $L = 3$. The bounds are $\underline{D} = (0, 0, 7, 18)$ and $\bar{D} = (11, 18, 18, 18)$. The value of operating points are: $\Psi_{.,1} = (0, 2.8, 1)$, $\Psi_{.,2} = (0, -6.8, -6.2)$, $\Psi_{.,3} = (0, 0.4, -0.8)$, $\Psi_{.,4} = (0, -11.6, -9.8)$ and $\Psi_{.,5} = (0, 2.0, 0.4)$.

**Figure 9** represents the graph $G_H$ associated with this instance. The vertices appear in black if they can be reached from $s$, and in gray otherwise. Dotted lines separate the vertices with respect to each operating point. For readability purposes, the values and the resource of the arcs are not represented in this graph. As the value only depends on the time period $t$ and the operating point $i$ they are the same for any arc heading to any vertex $(t, i, l)$ no matter the value of $l$. **Table 2** gives the value of each combination of $t$ and $i$. Similarly, the resource only depends on the operating point $i$ which is the same for any arc heading to any vertex $(t, i, l)$ no matter the value of $t$ or $l$. For operating point 0, the resource is 0; for operating point 1, the resource is 6 and for operating points 2, the resource is 11.

<table><caption>Table 2: Values of the arcs of graph $G_H$ depicted in **Figure 9**</caption><thead><tr><th></th><th>$i=0$</th><th>$i=1$</th><th>$i=2$</th></tr></thead><tbody><tr><th>$t=1$</th><td>0</td><td>2.8</td><td>3.8</td></tr><tr><th>$t=2$</th><td>0</td><td>-6.8</td><td>-13.0</td></tr><tr><th>$t=3$</th><td>0</td><td>0.4</td><td>-0.4</td></tr><tr><th>$t=4$</th><td>0</td><td>-11.6</td><td>-21.4</td></tr><tr><th>$t=5$</th><td>0</td><td>2.0</td><td>2.4</td></tr></tbody></table>

**Remark 2.** The 1-HUC problem is solved in practice on a daily basis, and the plant is not stopped between two consecutive days. This means that one needs to consider the last decision of the previous day when solving the 1-HUC problem. This can be taken into account by modifying source vertex $s$ as follows. Consider the path for the previous day going through vertex $(T, i, l)$. One can initialize $s = (0, i, l)$. As such, the plant can be operating continuously from one day to another, without violating any constraint. Note however that modifying
<figure><img src="image_11.png" /><figcaption>Figure 9: Graph $G_H$ of Example 4</figcaption></figure>

vertex $s$ in such a manner does not modify the structure of the graph. Hence, in the following we consider $s=(0,0,0)$ without loss of generality.

# 6 Experimental results

All presented results are computed on a single thread of an Intel Core i7-9850H CPU @ 2.60GHz processor of 12 cores, with Linux as operating system. All algorithms are developed with C++ and version 12.8 of CPLEX is used. The code for the BORWin algorithm is available online <fnref n="1" />.

A generic Hydro Instance Generator (HIG) has been provided by Dimitri Thomopulos and is available online <fnref n="2" />. However, preliminary results in [20] indicate that 1-HUC instances created with HIG can be relatively straightforward for CPLEX to solve: when applied to our mathematical model, CPLEX solves most of these instances in under a second. Preliminary results have also shown that when the price of the energy $\Lambda_t$ is very similar from one time period to another, instances of the 1-HUC are harder to solve. These preliminary results are consistent with the observations on instances of the Knapsack Problem, which are more difficult to solve when their values are highly correlated to their weight

<footnote n="1">¹https://github.com/Eegann/BORWin</footnote>

<footnote n="2">²https://www.lix.polytechnique.fr/Labo/Dimitri.Thomopulos/libraries/HIG.html</footnote>
[28].

For this study, we consider instead two sets of instances derived from real-world EDF's plants and reservoirs, as they are less easy to solve with CPLEX. In the first set of 83 instances, denoted as set A, the initial volume and some of the minimum and maximum volume per time period have been adjusted to ensure that at least one of the bounds on the window is active for at least one time period, as in [20]. The second set of 83 instances, denoted as set B, is built as follows. For each instance of the first set, an instance of the second set is created with $\Lambda_t$ being a random value in $[0.95 \cdot \Lambda_1; 1.05 \cdot \Lambda_1]$.

For our computational analysis we compare four approaches: model $M_{HUC}$ solved by CPLEX, RCSPP algorithm as described in [1], HA* algorithm [21] and BORWin.

**Figure 10** (resp. **Figure 11**) shows, for each approach, the number of instances solved with respect to the time for instance set A (resp. instance set B). **Table 3** to **Table 6** show the value of the solutions and the time required by each approach for each instance considered. For CPLEX, we also provide the number of nodes developed, denoted as \#node, as well as the optimality gap, being opt (resp inf, sub) if the solution returned is optimal (resp. infeasible, suboptimal). We also added the number of iterations of the second phase for BORWin, denoted as \#iter.

Clearly, these figures show that HA* and the RCSPP algorithms are not suitable to solve the 1-HUC problem. On the contrary, BORWin appears to be very well suited as it is the most efficient approach as soon as the computational times exceed 3 seconds. Moreover, in each set, BORWin solved 15 more instances than CPLEX which is the current approach at EDF. These results also confirm the preliminary results, as it appears that instances of set B are harder to solve than the ones of set A.

HA* algorithm is not suitable due to its upper bound, which does not take into account ramping or min-up/down constraints, hence being too loose to efficiently guide the enumeration. The RCSPP algorithm is inefficient as the dominance rule is seriously weakened due to the lower bound, as stated in **Section 5.2**. When it comes to solving the MILP with CPLEX, there are 12 instances of the first set, and 5 of the second set, where the solution returned is infeasible due to numerical errors, as it violates one of the window constraints. This violation is in most cases below 0.1%, but can reach up to 10%. For instance 64 in **Table 4**, the volume of the upstream reservoir violates all upper bounds from time period 29 to 96. At time period *T*, the volume reaches 29175.04 whereas the upper bound $\bar{V}_T^1$ is 26380. Such numerical errors have been observed, and a study has shown that these errors are due to floating-point precision of the solver [8, 34]. In addition to the infeasible solutions, there are 2 instances of the first set, and 6 of the second set where the instances are suboptimal. Instance 48 from set B shows a case where the value of solution obtained when solving the MILP with CPLEX is 0.009% below the value of the optimal solution obtained with BORWin. This is consistent with the optimality gap of CPLEX, which is $10^{-4}$ by default. Note that it is also possible that solving the MILP with
CPLEX yields a solution that is suboptimal and also infeasible. This is the case for instance 57 from set A.

<figure><img src="image_12.png" /><figcaption>Figure 10: Number of instances solved by each approach with respect to the time for instance set A</figcaption></figure>

# 7 Conclusion

In this paper, we proposed the BORWin algorithm to solve exactly any mixed integer maximization problem featuring special structure (P) characterized by the presence of several additional constraints. The first phase provides a family of lower bounds for (P) based on a bi-objective relaxation of the additional constraints. It is shown that the obtained bounds strongly relate to Lagrangian dual bounds. In the case where the special structure within (P) is an acyclic longest-path, problem (P) can be identified to a window constrained acyclic longest-path problem. For such problems, the second phase exploits these upper bounds to perform an efficient label extension procedure. Moreover, if (P) has other underlying structures for which efficient algorithms exist, it is shown that complementary upper bounds can be used to still accelerate the second phase. A typical example is when the additional constraints have a knapsack structure. Experimental results are provided for the 1-HUC, which features both longest-path and nested multiple-choice knapsack structures. On the easiest instances solved by Cplex in less than a second, BORWin remains a bit slower as it takes up to 3 seconds. However, on more difficult instances, it shows that BORWin algorithm outperforms other approaches in the sense that it is able to solve
<figure><img src="image_13.png" /><figcaption>Figure 11: Number of instances solved by each approach with respect to the time for instance set B</figcaption></figure>

significantly more instances within time limits.

As a perspective, BORWin algorithm could be used for other applications showing a similar structure, for example smart charging of one electric vehicle under battery capacity constraints. Another perspective would be to speed-up BORWin on the easiest instances by hybridization with other approaches, for example with an efficient MILP solver. The resulting algorithm could then be used as a pricing algorithm within a decomposition framework to solve large-scale instances of problems involving many blocks with structure (P). For example, this is the case for HUC instances with many reservoirs and power-plants interconnected in a water valley, or smart charging of a large fleet of electric vehicles coupled by grid constraints.

Finally, BORWin algorithm opens new optimization perspectives at EDF, as it could be integrated in operational tools to replace MILP solvers for single hydro units optimization. Moreover, window constraints appear in many other industrial contexts at EDF (optimization of gas units, optimization of electricity storage, ...) and BORWin algorithm could prove very useful to help speed-up classical RCSPP algorithms currently used.

## References

[1] Wim van Ackooij, Claudia d'Ambrosio, Leo Liberti, Raouia Taktak, Dimitri Thomopulos, and Sonia Toubaline. "Shortest path problem variants for
the hydro unit commitment problem”. In: *Electronic Notes in Discrete Mathematics* 69 (2018), pp. 309–316.

[2] Wim van Ackooij, Claudia d'Ambrosio, Dimitri Thomopulos, and Renan Spencer Trindade. “Decomposition and shortest path problem formulation for solving the hydro unit commitment and scheduling in a hydro valley”. In: *European Journal of Operational Research* 291.3 (2021), pp. 935–943.

[3] Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby, and Mahdi Jalili. “Enhanced methods for the weight constrained shortest path problem”. In: *Networks* (2024).

[4] Ronald D Armstrong, Prabhakant Sinha, and Andris A Zoltners. “The Multiple-Choice Nested Knapsack Model”. In: *Management Science* (1982), pp. 34–43.

[5] Chris Barrett, Keith Bisset, Martin Holzer, Goran Konjevod, Madhav Marathe, and Dorothea Wagner. “Engineering label-constrained shortest-path algorithms”. In: *Algorithmic Aspects in Information and Management: 4th International Conference (ICALIM 2004)*, Springer. 2004, pp. 27–37.

[6] John E Beasley and Nicos Christofides. “An algorithm for the resource constrained shortest path problem”. In: *Networks* 19.4 (1989), pp. 379–394.

[7] Richard Bellman. “On a routing problem”. In: *Quarterly of applied mathematics* 16.1 (1958), pp. 87–90.

[8] Pascale Bendotti and F Févotte. “Impact de l’arithmétique flottante sur la résolution de programmes linéaires”. In: *10èmes Journées Polyèdres et Optimisation Combinatoire*. 2016.

[9] Pascale Bendotti, Pierre Fouilhoux, and Cécile Rottner. “The min-up/min-down unit commitment polytope”. In: *Journal of Combinatorial Optimization* 36 (2018), pp. 1024–1058.

[10] Merve Bodur, Shabbir Ahmed, Natashia Boland, and George L Nemhauser. “Decomposition of loosely coupled integer programs: a multiobjective perspective”. In: *Mathematical Programming* 196.1 (2022), pp. 427–477.

[11] Natashia Boland, John Dethridge, and Irina Dumitrescu. “Accelerated label setting algorithms for the elementary resource constrained shortest path problem”. In: *Operations Research Letters* 34.1 (2006), pp. 58–68.

[12] Noel Bryson. “Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint”. In: *Computers & operations research* 18.2 (1991), pp. 129–140.

[13] W Matthew Carlyle, Johannes O Royset, and R Kevin Wood. “Lagrangian relaxation and enumeration for solving constrained shortest-path problems”. In: *Networks: an international journal* 52.4 (2008), pp. 256–270.

[14] Irina Dumitrescu and Natashia Boland. “Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem”. In: *Networks: An International Journal* 42.3 (2003), pp. 135–153.
[15] Rüdiger Ehlers. "Computing the complete pareto front". In: arXiv preprint arXiv:1512.05207 (2015).

[16] David Eppstein. "Finding the k shortest paths". In: SIAM Journal on computing 28.2 (1998), pp. 652–673.

[17] Ulrich Faigle and Satoru Fujishige. "A general model for matroids and the greedy algorithm". In: Mathematical programming 119.2 (2009), pp. 353–369.

[18] Grace Hechme-Doukopoulos, Sandrine Brignol-Charousset, Jérôme Malick, and Claude Lemaréchal. "The short-term electricity production management problem at EDF". In: Optima Newsletter 84 (2010), pp. 2–6.

[19] Alexandre Heintzmann. "Models and algorithms for the Hydro Unit Commitment problem". PhD thesis. Université de Toulouse', 2024. URL: https://theses.hal.science/tel-04640064.

[20] Alexandre Heintzmann, Christian Artigues, Pascale Bendotti, Sandra Ulrich Ngueveu, and Cécile Rottner. *Dynamic programming for the single unit hydro unit commitment problem*. Tech. rep. HAL-03916388, 2022.

[21] Alexandre Heintzmann, Christian Artigues, Pascale Bendotti, Sandra Ulrich Ngueveu, and Cécile Rottner. "Efficient exact A\* algorithm for the single plant Hydro Unit Commitment problem". In: 2023 18th Conference on Computer Science and Intel IEEE. 2023, pp. 533–543.

[22] Alexandre Heintzmann, Pascale Bendotti, and Cécile Rottner. "Handling polyhedral symmetries with a dedicated Branch\&Cut: application to a knapsack variant". In: Proceedings of the INFORMS Optimization Society Conference 2024 (2024).

[23] Stefan Irnich and Guy Desaulniers. "Shortest Path Problems with Resource Constraints". In: Column Generation. Ed. by Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon. Boston, MA: Springer US, 2005, pp. 33–65. ISBN: 978-0-387-25486-9. DOI: 10.1007/0-387-25486-2_2. URL: https://doi.org/10.1007/0-387-25486-2_2.

[24] Xuefeng Jin and Shunzheng Yu. "A two-stage method for doubly resource constrained elementary shortest path problems". In: Knowledge-Based Systems 293 (2024), p. 111661.

[25] Markus Kruber, Axel Parmentier, and Pascal Benchimol. *Resource constrained shortest path algorithm for 2018*. DOI: 10.48550/ARXIV.1809.00548. URL: https://arxiv.org/abs/1809.00548.

[26] Leonardo Lozano and Andrés L Medaglia. "On an exact method for the constrained shortest path problem". In: Computers & Operations Research 40.1 (2013), pp. 378–384.

[27] Juan I Pérez-Díaz, José R Wilhelmi, and Luis A Arévalo. "Optimal short-term operation schedule of a hydropower plant in a competitive electricity market". In: Energy Conversion and Management 51.12 (2010), pp. 2955–2966.
[28] David Pisinger. "Where are the hard knapsack problems?" In: *Computers & Operations Research* 32.9 (2005), pp. 2271-2284.

[29] Luigi Di Puglia Pugliese and Francesca Guerriero. "A survey of resource constrained shortest path problems: Exact solution approaches". In: *Networks* 62.3 (2013), pp. 183-200.

[30] Deepak Rajan, Samer Takriti, et al. "Minimum up/down polytopes of the unit commitment problem with start-up costs". In: *IBM Res. Rep* 23628 (2005), pp. 1-14.

[31] Arnaud Renaud. "Daily generation management at Electricité de France: from planning towards real time". In: *IEEE Transactions on Automatic Control* 38.7 (1993), pp. 1080-1093.

[32] Celso C Ribeiro and Michel Minoux. "A heuristic approach to hard constrained shortest path problems". In: *Discrete Applied Mathematics* 10.2 (1985), pp. 125-137.

[33] Cécile Rottner. "Generalized min-up/min-down polytopes". In: *Discrete Optimization* 55 (2025), p. 100866.

[34] Youcef Sahraoui, Pascale Bendotti, and Claudia d'Ambrosio. "Real-world hydro-power unit-commitment: Dealing with numerical errors and feasibility issues". In: *Energy* 184 (2019), pp. 91-104.

[35] Luis Santos, Joao Coutinho-Rodrigues, and John R Current. "An improved solution algorithm for the constrained shortest path problem". In: *Transportation Research Part B: Methodological* 41.7 (2007), pp. 756-771.

[36] Lara Turner. "Variants of the shortest path problem". In: *Algorithmic Operations Research* 6.2 (2011), pp. 91-104.

[37] Ekunda Lukata Ulungu and Jacques Teghem. "The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems". In: *Foundations of computing and decision sciences* 20.2 (1995), pp. 149-165.

[38] Thibaut Vidal, Daniel Gribel, and Patrick Jaillet. "Separable convex optimization with nested lower and upper constraints". In: *INFORMS Journal on Optimization* 1.1 (2019), pp. 71-90.

[39] Marc Visée, Jacques Teghem, Marc Pirlot, and Ekunda L Ulungu. "Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem". In: *Journal of Global Optimization* 12.2 (1998), pp. 139-155.

[40] Xiaoyan Zhu and Wilbert E Wilhelm. "Three-stage approaches for optimizing some variations of the resource constrained shortest-path subproblem in a column generation context". In: *European journal of operational research* 183.2 (2007), pp. 564-577.
# A Proofs

## A.1 Proof of Property 2

*Proof.* Consider a solution $x_3$ of (BOR) and suppose that $\mu_\delta(x_3) > \mu_\delta(x_1)$.

Consider the case $V_1(x_1) < V_1(x_3) < V_1(x_2)$ illustrated by **Figure 12a**. In such a case, $x_1$ and $x_2$ cannot be two consecutive solutions in $S$ by definition. Indeed, either $x_3$, or a Pareto-supported solution dominating $x_3$ is between $x_1$ and $x_2$ in $S$.

Consider the case $V_1(x_1) < V_1(x_2) < V_1(x_3)$ illustrated by **Figure 12b**. Note in this case that $V_2(x_1) \ge V_2(x_2) \ge V_2(x_3)$ otherwise solutions $x_1$ and $x_2$ would not be Pareto-supported. Let $\delta'$ be such that $\mu_{\delta'}(x_1) = \mu_{\delta'}(x_3)$. We suppose that $\mu_{\delta'}(x_2) \ge \mu_{\delta'}(x_1)$ to show a contradiction. We then know the following:

$$ 
\begin{aligned}
V_1(x_1) + \delta \cdot V_2(x_1) &< V_1(x_3) + \delta \cdot V_2(x_3) \\
V_1(x_1) + \delta' \cdot V_2(x_1) &\le V_1(x_2) + \delta' \cdot V_2(x_2)
\end{aligned}
$$

We can deduce $\delta \cdot (V_2(x_1) - V_2(x_3)) < (V_1(x_3) - V_1(x_1))$ and $\delta' \cdot (V_2(x_1) - V_2(x_2)) \le (V_1(x_2) - V_1(x_1))$. Using equalities:

$$ 
\begin{aligned}
V_1(x_1) + \delta \cdot V_2(x_1) &= V_1(x_2) + \delta \cdot V_2(x_2) \\
V_1(x_1) + \delta' \cdot V_2(x_1) &= V_1(x_3) + \delta' \cdot V_2(x_3)
\end{aligned}
$$

we obtain from the inequality featuring $\delta$:

$$ \frac{V_2(x_1) - V_2(x_3)}{V_2(x_1) - V_2(x_2)} < \frac{V_1(x_3) - V_1(x_1)}{V_1(x_2) - V_1(x_1)} $$

and from the inequality featuring $\delta'$:

$$ \frac{V_2(x_1) - V_2(x_3)}{V_2(x_1) - V_2(x_2)} \ge \frac{V_1(x_3) - V_1(x_1)}{V_1(x_2) - V_1(x_1)} $$

which is a contradiction. Hence $V_1(x_1) < V_1(x_2) < V_1(x_3)$ implies that $\mu_{\delta'}(x_2) < \mu_{\delta'}(x_1) = \mu_{\delta'}(x_3)$. **Lemma 1** shows that in such a case $x_2$ cannot be Pareto-supported, which is a contradiction with $x_2 \in S$.

A similar contradiction can be obtained in the case $V_1(x_3) < V_1(x_1) < V_1(x_2)$. □

## A.2 Proof of Theorem 1

*Proof.* Consider another pair $(x'_1, x'_2)$ of consecutive solutions in $S$, and $\delta'$ such that $\mu_{\delta'}(x'_1) = \mu_{\delta'}(x'_2)$. Illustrations can be found in **Figure 13a** and **Figure 13b**.
<figure><img src="image_14.png" /><figcaption>Figure 12: Illustrations for Property 2</figcaption></figure>

Suppose $\bar{V}_1(x'_1, \delta') < \bar{V}_1(x_1, \delta)$, i.e.,

$$\mu_{\delta'}(x'_1) - \mu_{\delta}(x_1) < (\delta' - \delta) \cdot \beta$$

Using Property 2, we have for any solution $x$ of (BOR):

$$\mu_{\delta'}(x) = V_1(x) + \delta' V_2(x) \leq \mu_{\delta'}(x'_1)$$

Replacing $V_1(x)$ by $\mu_{\delta}(x) - \delta V_2(x)$, we obtain

$$(\delta' - \delta) \cdot V_2(x) \leq \mu_{\delta'}(x'_1) - \mu_{\delta}(x)$$

Therefore, applying to $x = x_1$ and $x = x_2$, and using $\mu_{\delta}(x_1) = \mu_{\delta}(x_2)$:

$$(\delta' - \delta) \cdot V_2(x_1) \leq \mu_{\delta'}(x'_1) - \mu_{\delta}(x_1) < (\delta' - \delta) \cdot \beta$$

$$(\delta' - \delta) \cdot V_2(x_2) \leq \mu_{\delta'}(x'_1) - \mu_{\delta}(x_1) < (\delta' - \delta) \cdot \beta$$

As $V_2(x_2) < \beta \leq V_2(x_1)$, then there is a contradiction. □

### A.3 Proof of Property 8

*Proof.* There are $(N+1) \cdot (2L-1)$ vertices per time period. Hence, there are $T \cdot (N+1) \cdot (2L-1)+2$ vertices in $G_H$ in total. As $L \leq T$, we deduce that the number of vertices is at most $T \cdot (N+1) \cdot (2T-1)+2$

From the definition of the HUC problem, there are data for each operating points, such as $D_i$, but also for each time period, such as $\alpha_t$. Hence the size of the instance is of $O(T+N)$.

As the number of vertices is of $O(T^2 \cdot N)$ the number of vertices of $G_H$ is polynomial with respect to the size of the instance. □
<figure><img src="image_15.png" /><figcaption>Figure 13: Illustrations for Theorem 1</figcaption></figure>

## A.4 Proof of Property 9

*Proof.* Consider an arc between $(t, i, l)$ and $(t+1, i', l')$. Clearly, in the case $i = i'$, the ramping constraints are satisfied if such an arc exists in $G_H$. In the case $i < i'$, such an arc only exists if $\sum_{j=i+1}^i D_j \le R_d$ by construction of $G_H$. In the case $i > i'$, such an arc only exists if $\sum_{j=i'}^{i-1} D_j \le R_u$ by construction of $G_H$. Consequently, ramping constraints are always satisfied.

By construction of $G_H$, from a vertex $(t, i, l)$, the only way to reach operating point $i' > i$ is through the arc towards $(t+1, i', L-1)$. Also by construction of $G_H$, from $(t+1, i', L-1, u)$, one needs to go through all vertices $(t+1+\tau, i', L-1-\tau)$, with $\tau \in \{1, \dots, L-2\}$, and $(t+L, i', 0)$ in order to reach operating point $i'' < i'$. In total, a path must go through at least $1+L-2+1 = L$ vertices with operating point $i'$ before heading to a vertex with operating point $i'' < i'$. Hence, the min-up constraint is satisfied. We can prove in a similar way that the min-down constraints are satisfied. $\square$

## B Numerical results

In this appendix, detailed experimental results are presented (see Section 6). Note that in Tables 3 and 5, instance 21 shows an optimal solution value equal to zero. Indeed, in this instance the initial reservoir volume is equal to the minimum volume of each time period and there is no intake. Therefore, all the water flows must trivially be zero in any solution.
<table><caption>Table 3: Performance of model $M_{HUC}$ solved with CPLEX, the RCSPP algorithm, HA* and BORWin on instances 1 to 42 of set A</caption><thead><tr><th rowspan="2">instance</th><th rowspan="2">value</th><th colspan="3">CPLEX</th><th colspan="2">RCSPP</th><th colspan="2">HA*</th><th colspan="3">BORWin</th></tr><tr><th>gap</th><th>time</th><th>#nodes</th><th>value</th><th>time</th><th>value</th><th>time</th><th>value</th><th>#iter</th><th>time</th></tr></thead><tbody><tr><td>1</td><td>-27092.4</td><td>14.0</td><td>24213</td><td>-</td><td>3969.29</td><td>-</td><td>3600.33</td><td>-27092.4</td><td>2950</td><td>1.43</td></tr><tr><td>2</td><td>42334.7</td><td>1.0</td><td>9653</td><td>42334.7</td><td>3.77</td><td>-</td><td>3600.41</td><td>42334.7</td><td>2482</td><td>1.4</td></tr><tr><td>3</td><td>2480.68</td><td>104.0</td><td>97567</td><td>-</td><td>3842.11</td><td>-</td><td>3600.36</td><td>2480.68</td><td>5475</td><td>3.49</td></tr><tr><td>4</td><td>1556.68</td><td>0.0</td><td>531</td><td>-</td><td>3806.62</td><td>-</td><td>3600.48</td><td>1556.68</td><td>316</td><td>0.51</td></tr><tr><td>5</td><td>108120.0</td><td>0.0</td><td>863</td><td>-</td><td>3620.11</td><td>-</td><td>3600.34</td><td>108120.0</td><td>860</td><td>1.64</td></tr><tr><td>6</td><td>-2550.61</td><td>0.0</td><td>630</td><td>-</td><td>3963.0</td><td>-</td><td>3600.44</td><td>-2550.61</td><td>310</td><td>0.87</td></tr><tr><td>7</td><td>3031.07</td><td>0.0</td><td>77</td><td>-</td><td>3857.97</td><td>-</td><td>3600.3</td><td>3031.07</td><td>2753</td><td>2.64</td></tr><tr><td>8</td><td>13903.4</td><td>inf</td><td>2487</td><td>-</td><td>3654.9</td><td>-</td><td>3600.28</td><td>13903.4</td><td>9644</td><td>12.12</td></tr><tr><td>9</td><td>-81458.9</td><td>inf</td><td>22.0</td><td>9845</td><td>-</td><td>3791.48</td><td>-</td><td>3600.2</td><td>-81458.9</td><td>4507</td><td>5.87</td></tr><tr><td>10</td><td>-622046.0</td><td>0.17</td><td>3599.0</td><td>164270</td><td>-</td><td>3618.49</td><td>-</td><td>3600.2</td><td>-622046.0</td><td>784</td><td>3.22</td></tr><tr><td>11</td><td>41736.5</td><td>0.0</td><td>0</td><td>41736.5</td><td>112.82</td><td>-</td><td>3600.52</td><td>41736.5</td><td>17</td><td>1.56</td></tr><tr><td>12</td><td>-32130.1</td><td>opt</td><td>87.0</td><td>10279</td><td>-</td><td>3798.79</td><td>-</td><td>3600.14</td><td>-32130.1</td><td>582</td><td>3.86</td></tr><tr><td>13</td><td>-185784.0</td><td>1.58</td><td>3599.0</td><td>184953</td><td>-</td><td>3699.51</td><td>-</td><td>3600.19</td><td>-185784.0</td><td>264</td><td>2.43</td></tr><tr><td>14</td><td>19048.7</td><td>opt</td><td>3.0</td><td>2537</td><td>19048.7</td><td>29.5</td><td>-</td><td>3600.39</td><td>19048.7</td><td>2421</td><td>0.77</td></tr><tr><td>15</td><td>4876.22</td><td>opt</td><td>0.0</td><td>0</td><td>4876.22</td><td>0.01</td><td>4876.22</td><td>0.07</td><td>4876.22</td><td>7</td><td>0.08</td></tr><tr><td>16</td><td>12856.2</td><td>opt</td><td>0.0</td><td>1155</td><td>12856.2</td><td>0.06</td><td>12856.2</td><td>1738.4</td><td>12856.2</td><td>1832</td><td>1.17</td></tr><tr><td>17</td><td>14970.0</td><td>opt</td><td>0.0</td><td>435</td><td>14970.0</td><td>0.34</td><td>14970.0</td><td>606.87</td><td>14970.0</td><td>1143</td><td>0.37</td></tr><tr><td>18</td><td>12647.3</td><td>opt</td><td>0.0</td><td>1801</td><td>12647.3</td><td>0.07</td><td>-</td><td>3600.33</td><td>12647.3</td><td>1845</td><td>0.66</td></tr><tr><td>19</td><td>9276.1</td><td>opt</td><td>0.0</td><td>159</td><td>9276.1</td><td>0.04</td><td>9276.1</td><td>157.2</td><td>9276.1</td><td>815</td><td>0.31</td></tr><tr><td>20</td><td>12600.0</td><td>opt</td><td>0.0</td><td>45</td><td>12600.0</td><td>0.31</td><td>12600.0</td><td>69.8</td><td>12600.0</td><td>601</td><td>0.34</td></tr><tr><td>21</td><td>0.0</td><td>opt</td><td>0.0</td><td>0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.0</td><td>1</td><td>0.01</td></tr><tr><td>22</td><td>21996.5</td><td>opt</td><td>0.0</td><td>0</td><td>21996.5</td><td>0.04</td><td>21996.5</td><td>0.01</td><td>21996.5</td><td>0</td><td>0.0</td></tr><tr><td>23</td><td>96870.5</td><td>opt</td><td>14.0</td><td>32704</td><td>96870.5</td><td>9.82</td><td>96870.5</td><td>3167.85</td><td>96870.5</td><td>2897</td><td>3.02</td></tr><tr><td>24</td><td>18974.6</td><td>opt</td><td>0.0</td><td>0</td><td>18974.6</td><td>0.02</td><td>18974.6</td><td>0.01</td><td>18974.6</td><td>0</td><td>0.0</td></tr><tr><td>25</td><td>197441.0</td><td>opt</td><td>0.0</td><td>0</td><td>197441.0</td><td>2.0</td><td>197441.0</td><td>477.82</td><td>197441.0</td><td>2058</td><td>2.12</td></tr><tr><td>26</td><td>21588.0</td><td>opt</td><td>0.0</td><td>0</td><td>21588.0</td><td>0.04</td><td>21588.0</td><td>0.01</td><td>21588.0</td><td>5</td><td>0.36</td></tr><tr><td>27</td><td>95900.6</td><td>opt</td><td>0.0</td><td>0</td><td>95900.6</td><td>0.02</td><td>95900.6</td><td>0.01</td><td>95900.6</td><td>0</td><td>0.01</td></tr><tr><td>28</td><td>102450.0</td><td>opt</td><td>0.0</td><td>0</td><td>102450.0</td><td>0.02</td><td>102450.0</td><td>0.01</td><td>102450.0</td><td>0</td><td>0.01</td></tr><tr><td>29</td><td>72778.7</td><td>inf</td><td>4.0</td><td>11675</td><td>-</td><td>3690.14</td><td>-</td><td>3600.52</td><td>72778.7</td><td>31422</td><td>28.62</td></tr><tr><td>30</td><td>-5397.97</td><td>opt</td><td>0.0</td><td>0</td><td>-5397.97</td><td>0.01</td><td>-5397.97</td><td>0.01</td><td>-5397.97</td><td>0</td><td>0.0</td></tr><tr><td>31</td><td>705.98</td><td>opt</td><td>0.0</td><td>0</td><td>705.98</td><td>0.01</td><td>705.98</td><td>0.01</td><td>705.98</td><td>6</td><td>0.06</td></tr><tr><td>32</td><td>24792.1</td><td>opt</td><td>0.0</td><td>0</td><td>24792.1</td><td>0.01</td><td>24792.1</td><td>0.01</td><td>24792.1</td><td>0</td><td>0.0</td></tr><tr><td>33</td><td>3079.3</td><td>opt</td><td>0.0</td><td>0</td><td>3079.3</td><td>0.05</td><td>3079.3</td><td>0.01</td><td>3079.3</td><td>0</td><td>0.0</td></tr><tr><td>34</td><td>62604.5</td><td>opt</td><td>0.0</td><td>0</td><td>62604.5</td><td>355.76</td><td>62604.5</td><td>1147.09</td><td>62604.5</td><td>344</td><td>0.64</td></tr><tr><td>35</td><td>100832.0</td><td>opt</td><td>0.0</td><td>0</td><td>100832.0</td><td>0.02</td><td>100832.0</td><td>0.01</td><td>100832.0</td><td>0</td><td>0.01</td></tr><tr><td>36</td><td>28104.4</td><td>opt</td><td>0.0</td><td>0</td><td>28104.4</td><td>0.49</td><td>28104.4</td><td>0.21</td><td>28104.4</td><td>17</td><td>0.21</td></tr><tr><td>37</td><td>421369.0</td><td>opt</td><td>0.0</td><td>177</td><td>-</td><td>3723.65</td><td>-</td><td>3600.41</td><td>421369.0</td><td>95</td><td>0.46</td></tr><tr><td>38</td><td>-4281.16</td><td>opt</td><td>0.0</td><td>0</td><td>-4281.16</td><td>95.53</td><td>-</td><td>3600.49</td><td>-4281.16</td><td>1776</td><td>1.47</td></tr><tr><td>39</td><td>-31910.4</td><td>opt</td><td>0.0</td><td>4955</td><td>-</td><td>3658.38</td><td>-</td><td>3600.35</td><td>-31910.4</td><td>3130</td><td>3.14</td></tr><tr><td>40</td><td>18323.5</td><td>opt</td><td>0.0</td><td>71</td><td>18323.5</td><td>42.47</td><td>-</td><td>3600.58</td><td>18323.5</td><td>594</td><td>0.84</td></tr><tr><td>41</td><td>-2480.26</td><td>opt</td><td>0.0</td><td>0</td><td>-2480.26</td><td>0.0</td><td>-2480.26</td><td>0.01</td><td>-2480.26</td><td>26</td><td>0.11</td></tr><tr><td>42</td><td>4529.62</td><td>opt</td><td>0.0</td><td>0</td><td>4529.62</td><td>0.03</td><td>4529.62</td><td>0.01</td><td>4529.62</td><td>0</td><td>0.0</td></tr></tbody></table>
<table><caption>Table 4: Performance of model $M_{HUC}$ solved with CPLEX, the RCSPP algorithm, HA* and BORWin on instances 43 to 83 of set A</caption><thead><tr><th rowspan="2">instance</th><th rowspan="2">value</th><th colspan="3">CPLEX</th><th colspan="2">RCSPP</th><th colspan="2">HA*</th><th colspan="3">BORWin</th></tr><tr><th>gap</th><th>time</th><th>#nodes</th><th>value</th><th>time</th><th>value</th><th>time</th><th>value</th><th>#iter</th><th>time</th></tr></thead><tbody><tr><td>43</td><td>269 050.0</td><td>0.0</td><td>0</td><td>269 050.0</td><td>0.03</td><td>269 050.0</td><td>0.01</td><td>269 050.0</td><td>0</td><td>0.0</td></tr><tr><td>44</td><td>919 601.0</td><td>5.0</td><td>23903</td><td>-</td><td>4535.04</td><td>-</td><td>3600.5</td><td>919 605.0</td><td>2198</td><td>1.19</td></tr><tr><td>45</td><td>287 722.0</td><td>0.0</td><td>26</td><td>-</td><td>3689.87</td><td>-</td><td>3600.36</td><td>287 722.0</td><td>72</td><td>0.68</td></tr><tr><td>46</td><td>52 834.5</td><td>0.0</td><td>0</td><td>52 834.5</td><td>0.07</td><td>52 834.5</td><td>0.04</td><td>52 834.5</td><td>0</td><td>0.01</td></tr><tr><td>47</td><td>459 095.0</td><td>0.0</td><td>0</td><td>459 095.0</td><td>0.04</td><td>459 095.0</td><td>0.01</td><td>459 095.0</td><td>0</td><td>0.0</td></tr><tr><td>48</td><td>462 869.0</td><td>inf</td><td>1.0</td><td>1571</td><td>-</td><td>3780.74</td><td>-</td><td>3600.45</td><td>462 869.0</td><td>693</td><td>0.82</td></tr><tr><td>49</td><td>42 341.8</td><td>opt</td><td>0.0</td><td>0</td><td>42 341.8</td><td>0.06</td><td>42 341.8</td><td>0.03</td><td>42 341.8</td><td>0</td><td>0.0</td></tr><tr><td>50</td><td>4905.83</td><td>opt</td><td>1.0</td><td>8813</td><td>-</td><td>3608.06</td><td>-</td><td>3600.43</td><td>4905.83</td><td>2614</td><td>2.18</td></tr><tr><td>51</td><td>40 192.6</td><td>opt</td><td>0.0</td><td>0</td><td>40 192.6</td><td>0.01</td><td>40 192.6</td><td>0.02</td><td>40 192.6</td><td>0</td><td>0.0</td></tr><tr><td>52</td><td>48 378.6</td><td>opt</td><td>0.0</td><td>280</td><td>-</td><td>3678.46</td><td>-</td><td>3600.39</td><td>48 378.6</td><td>784</td><td>0.55</td></tr><tr><td>53</td><td>28 142.9</td><td>opt</td><td>0.0</td><td>0</td><td>28 142.9</td><td>1.75</td><td>28 142.9</td><td>0.19</td><td>28 142.9</td><td>9</td><td>0.03</td></tr><tr><td>54</td><td>3 838 650.0</td><td>sub</td><td>0.0</td><td>0</td><td>3 838 990.0</td><td>75.46</td><td>-</td><td>3600.46</td><td>3 838 990.0</td><td>1687</td><td>0.78</td></tr><tr><td>55</td><td>9577.87</td><td>opt</td><td>0.0</td><td>425</td><td>-</td><td>3606.21</td><td>-</td><td>3600.73</td><td>9577.87</td><td>900</td><td>0.8</td></tr><tr><td>56</td><td>28 471.9</td><td>opt</td><td>0.0</td><td>0</td><td>28 471.9</td><td>0.01</td><td>28 471.9</td><td>0.03</td><td>28 471.9</td><td>0</td><td>0.01</td></tr><tr><td>57</td><td>3 931 900.0</td><td>inf</td><td>0.0</td><td>1177</td><td>-</td><td>3716.47</td><td>-</td><td>3600.29</td><td>3 931 900.0</td><td>287191</td><td>2468.04</td></tr><tr><td>58</td><td>750 878.0</td><td>opt</td><td>0.0</td><td>544</td><td>-</td><td>3637.65</td><td>-</td><td>3600.58</td><td>750 878.0</td><td>15667</td><td>24.59</td></tr><tr><td>59</td><td>19 159.0</td><td>opt</td><td>0.0</td><td>7</td><td>19 159.0</td><td>51.78</td><td>19 159.0</td><td>20.16</td><td>19 159.0</td><td>31</td><td>0.26</td></tr><tr><td>60</td><td>25 720.8</td><td>opt</td><td>0.0</td><td>0</td><td>25 720.8</td><td>0.05</td><td>25 720.8</td><td>0.01</td><td>25 720.8</td><td>0</td><td>0.0</td></tr><tr><td>61</td><td>-19 718.7</td><td>opt</td><td>0.0</td><td>713</td><td>-</td><td>3686.43</td><td>-</td><td>3600.6</td><td>-19 718.7</td><td>1555</td><td>0.88</td></tr><tr><td>62</td><td>12 003.3</td><td>opt</td><td>0.0</td><td>30</td><td>12 003.3</td><td>438.36</td><td>12 003.3</td><td>21.86</td><td>12 003.3</td><td>109</td><td>0.49</td></tr><tr><td>63</td><td>935 608.0</td><td>opt</td><td>0.0</td><td>0</td><td>935 608.0</td><td>0.06</td><td>935 608.0</td><td>0.02</td><td>935 608.0</td><td>0</td><td>0.0</td></tr><tr><td>64</td><td>124 600.0</td><td>opt</td><td>2.0</td><td>8219</td><td>-</td><td>3624.53</td><td>-</td><td>3600.48</td><td>124 600.0</td><td>15577</td><td>45.85</td></tr><tr><td>65</td><td>379 220.0</td><td>opt</td><td>0.0</td><td>0</td><td>379 220.0</td><td>0.01</td><td>379 220.0</td><td>0.01</td><td>379 220.0</td><td>0</td><td>0.0</td></tr><tr><td>66</td><td>164 134.0</td><td>opt</td><td>2.0</td><td>10774</td><td>164 134.0</td><td>2586.77</td><td>-</td><td>3600.61</td><td>164 134.0</td><td>5171</td><td>4.63</td></tr><tr><td>67</td><td>703 224.0</td><td>opt</td><td>0.0</td><td>0</td><td>703 224.0</td><td>0.02</td><td>703 224.0</td><td>0.02</td><td>703 224.0</td><td>0</td><td>0.0</td></tr><tr><td>68</td><td>94 517.5</td><td>opt</td><td>0.0</td><td>51</td><td>94 517.5</td><td>0.02</td><td>94 517.5</td><td>0.03</td><td>94 517.5</td><td>52</td><td>0.42</td></tr><tr><td>69</td><td>65 259.0</td><td>inf</td><td>3.0</td><td>3410</td><td>-</td><td>3672.31</td><td>-</td><td>3600.29</td><td>65 259.0</td><td>5138</td><td>4.73</td></tr><tr><td>70</td><td>-2612.74</td><td>opt</td><td>0.0</td><td>0</td><td>-2612.74</td><td>0.0</td><td>-2612.74</td><td>0.01</td><td>-2612.74</td><td>0</td><td>0.0</td></tr><tr><td>71</td><td>667 875.0</td><td>inf</td><td>1.0</td><td>1478</td><td>-</td><td>3750.4</td><td>-</td><td>3600.43</td><td>667 875.0</td><td>1458</td><td>2.83</td></tr><tr><td>72</td><td>-627 719.0</td><td>opt</td><td>0.0</td><td>0</td><td>-</td><td>3719.42</td><td>-</td><td>3600.33</td><td>-627 719.0</td><td>84</td><td>0.8</td></tr><tr><td>73</td><td>48 011.4</td><td>inf</td><td>0.0</td><td>24</td><td>-</td><td>3603.42</td><td>-</td><td>3600.45</td><td>48 011.4</td><td>352</td><td>0.97</td></tr><tr><td>74</td><td>71 518.2</td><td>opt</td><td>0.0</td><td>371</td><td>-</td><td>3610.12</td><td>-</td><td>3600.52</td><td>71 518.2</td><td>678</td><td>1.24</td></tr><tr><td>75</td><td>16 119.0</td><td>opt</td><td>0.0</td><td>0</td><td>16 119.0</td><td>4.08</td><td>16 119.0</td><td>1.42</td><td>16 119.0</td><td>239</td><td>0.17</td></tr><tr><td>76</td><td>4976.64</td><td>opt</td><td>0.0</td><td>0</td><td>4976.64</td><td>0.07</td><td>4976.64</td><td>0.02</td><td>4976.64</td><td>0</td><td>0.01</td></tr><tr><td>77</td><td>-3343.57</td><td>opt</td><td>0.0</td><td>186</td><td>-3343.57</td><td>779.71</td><td>-3343.57</td><td>1525.54</td><td>-3343.57</td><td>222</td><td>0.17</td></tr><tr><td>78</td><td>-3209.93</td><td>opt</td><td>0.0</td><td>0</td><td>-3209.93</td><td>0.0</td><td>-3209.93</td><td>0.01</td><td>-3209.93</td><td>0</td><td>0.0</td></tr><tr><td>79</td><td>64 146.1</td><td>opt</td><td>0.0</td><td>0</td><td>-</td><td>3742.06</td><td>-</td><td>3600.29</td><td>64 146.1</td><td>3982</td><td>2.82</td></tr><tr><td>80</td><td>15 155.4</td><td>inf</td><td>0.0</td><td>0</td><td>15 155.4</td><td>147.59</td><td>15 155.4</td><td>58.44</td><td>15 155.4</td><td>287</td><td>0.26</td></tr><tr><td>81</td><td>84 971.2</td><td>opt</td><td>0.0</td><td>1000</td><td>-</td><td>3711.35</td><td>-</td><td>3600.43</td><td>84 971.2</td><td>252119</td><td>3148.39</td></tr><tr><td>82</td><td>33 343.4</td><td>opt</td><td>0.0</td><td>0</td><td>-</td><td>3661.97</td><td>-</td><td>3600.54</td><td>33 343.4</td><td>227</td><td>0.31</td></tr><tr><td>83</td><td>775.58</td><td>opt</td><td>0.0</td><td>25</td><td>775.58</td><td>0.01</td><td>775.58</td><td>0.18</td><td>775.58</td><td>142</td><td>0.18</td></tr></tbody></table>
<table><caption>Table 5: Performance of model $M_{HUC}$ solved with CPLEX, the RCSPP algorithm, HA* and BORWin on instances 1 to 42 of set B</caption><thead><tr><th rowspan="2">instance</th><th colspan="3">CPLEX</th><th colspan="2">RCSPP</th><th colspan="2">HA*</th><th colspan="3">BORWin</th></tr><tr><th>value</th><th>gap</th><th>time</th><th>#nodes</th><th>value</th><th>time</th><th>value</th><th>time</th><th>value</th><th>#iter</th><th>time</th></tr></thead><tbody><tr><td>1</td><td>-45097.8</td><td>0.24</td><td>3599.0</td><td>5159794</td><td>-</td><td>3728.16</td><td>-</td><td>3600.2</td><td>-45097.8</td><td>230460</td><td>2318.99</td></tr><tr><td>2</td><td>30816.8</td><td>opt</td><td>462.0</td><td>535149</td><td>30816.8</td><td>2.66</td><td>-</td><td>3600.33</td><td>30816.8</td><td>4385</td><td>2.73</td></tr><tr><td>3</td><td>-12364.3</td><td>0.87</td><td>3599.0</td><td>6511928</td><td>-</td><td>3657.08</td><td>-</td><td>3600.29</td><td>-12364.3</td><td>185759</td><td>1325.15</td></tr><tr><td>4</td><td>-4771.67</td><td>opt</td><td>88.0</td><td>51047</td><td>-</td><td>3635.03</td><td>-</td><td>3600.44</td><td>-4771.67</td><td>13212</td><td>73.31</td></tr><tr><td>5</td><td>100037.0</td><td>opt</td><td>0.0</td><td>23</td><td>-</td><td>3627.04</td><td>-</td><td>3600.55</td><td>100037.0</td><td>6</td><td>0.79</td></tr><tr><td>6</td><td>-8330.37</td><td>opt</td><td>182.0</td><td>95280</td><td>-</td><td>3625.38</td><td>-</td><td>3600.56</td><td>-8330.37</td><td>21368</td><td>58.23</td></tr><tr><td>7</td><td>-25268.1</td><td>opt</td><td>0.0</td><td>494</td><td>-</td><td>3641.08</td><td>-</td><td>3600.57</td><td>-25268.1</td><td>12275</td><td>25.31</td></tr><tr><td>8</td><td>-15274.7</td><td>inf</td><td>0.0</td><td>105</td><td>-</td><td>3786.47</td><td>-15274.7</td><td>198.96</td><td>-15274.7</td><td>1943</td><td>3.93</td></tr><tr><td>9</td><td>-134802.0</td><td>0.01</td><td>3599.0</td><td>797938</td><td>-</td><td>3676.52</td><td>-</td><td>3600.33</td><td>-134802.0</td><td>5155</td><td>3601.74</td></tr><tr><td>10</td><td>-495393.0</td><td>opt</td><td>907.0</td><td>119597</td><td>-</td><td>3628.56</td><td>-</td><td>3600.21</td><td>-495393.0</td><td>3428</td><td>7.31</td></tr><tr><td>11</td><td>22498.4</td><td>opt</td><td>1.0</td><td>1079</td><td>22498.4</td><td>50.23</td><td>-</td><td>3600.42</td><td>22498.4</td><td>185</td><td>2.41</td></tr><tr><td>12</td><td>-15704.4</td><td>opt</td><td>91.0</td><td>19017</td><td>-</td><td>3744.61</td><td>-</td><td>3600.31</td><td>-15704.4</td><td>26</td><td>5.27</td></tr><tr><td>13</td><td>-362953.0</td><td>0.01</td><td>3599.0</td><td>749964</td><td>-</td><td>4030.62</td><td>-</td><td>3600.26</td><td>-362953.0</td><td>106576</td><td>3601.59</td></tr><tr><td>14</td><td>20036.7</td><td>opt</td><td>812.0</td><td>680819</td><td>20036.7</td><td>28.34</td><td>-</td><td>3600.42</td><td>20036.7</td><td>4734</td><td>1.65</td></tr><tr><td>15</td><td>3060.83</td><td>opt</td><td>0.0</td><td>38</td><td>3060.83</td><td>0.02</td><td>3060.83</td><td>1648.99</td><td>3060.83</td><td>1214</td><td>0.47</td></tr><tr><td>16</td><td>9849.72</td><td>opt</td><td>12.0</td><td>34012</td><td>9849.72</td><td>0.07</td><td>-</td><td>3600.39</td><td>9849.72</td><td>2722</td><td>1.3</td></tr><tr><td>17</td><td>8633.68</td><td>opt</td><td>2.0</td><td>9440</td><td>8633.68</td><td>0.17</td><td>-</td><td>3600.51</td><td>8633.68</td><td>10660</td><td>6.11</td></tr><tr><td>18</td><td>10167.2</td><td>0.4</td><td>3599.0</td><td>1124478</td><td>10167.2</td><td>0.07</td><td>-</td><td>3600.51</td><td>10167.2</td><td>7908</td><td>3.63</td></tr><tr><td>19</td><td>8617.41</td><td>opt</td><td>1.0</td><td>5022</td><td>8617.41</td><td>0.04</td><td>8617.41</td><td>3360.88</td><td>8617.41</td><td>1965</td><td>0.91</td></tr><tr><td>20</td><td>8781.47</td><td>opt</td><td>13.0</td><td>34045</td><td>8781.47</td><td>0.64</td><td>-</td><td>3600.52</td><td>8781.47</td><td>4018</td><td>1.74</td></tr><tr><td>21</td><td>0.0</td><td>opt</td><td>0.0</td><td>0</td><td>0</td><td>0.0</td><td>0.0</td><td>0.01</td><td>0.0</td><td>1</td><td>0.01</td></tr><tr><td>22</td><td>21996.5</td><td>opt</td><td>0.0</td><td>0</td><td>21996.5</td><td>0.05</td><td>21996.5</td><td>0.01</td><td>21996.5</td><td>0</td><td>0.0</td></tr><tr><td>23</td><td>95051.4</td><td>0.63</td><td>3599.0</td><td>833133</td><td>95051.4</td><td>30.72</td><td>-</td><td>3600.4</td><td>95051.4</td><td>10440</td><td>31.82</td></tr><tr><td>24</td><td>18974.6</td><td>opt</td><td>0.0</td><td>0</td><td>18974.6</td><td>0.02</td><td>18974.6</td><td>0.01</td><td>18974.6</td><td>0</td><td>0.0</td></tr><tr><td>25</td><td>196839.0</td><td>opt</td><td>0.0</td><td>0</td><td>196839.0</td><td>1.83</td><td>196839.0</td><td>758.65</td><td>196839.0</td><td>1879</td><td>1.94</td></tr><tr><td>26</td><td>21459.5</td><td>opt</td><td>0.0</td><td>0</td><td>21459.5</td><td>0.04</td><td>21459.5</td><td>0.01</td><td>21459.5</td><td>2</td><td>0.19</td></tr><tr><td>27</td><td>95900.6</td><td>opt</td><td>0.0</td><td>0</td><td>95900.6</td><td>0.03</td><td>95900.6</td><td>0.01</td><td>95900.6</td><td>0</td><td>0.0</td></tr><tr><td>28</td><td>102450.0</td><td>opt</td><td>0.0</td><td>0</td><td>102450.0</td><td>0.03</td><td>102450.0</td><td>0.01</td><td>102450.0</td><td>0</td><td>0.0</td></tr><tr><td>29</td><td>62292.3</td><td>inf</td><td>2.0</td><td>6388</td><td>-</td><td>3626.06</td><td>-</td><td>3600.41</td><td>62292.3</td><td>55078</td><td>93.38</td></tr><tr><td>30</td><td>-5397.97</td><td>opt</td><td>0.0</td><td>0</td><td>-5397.97</td><td>0.01</td><td>-5397.97</td><td>0.01</td><td>-5397.97</td><td>0</td><td>0.0</td></tr><tr><td>31</td><td>99.34</td><td>opt</td><td>0.0</td><td>0</td><td>99.34</td><td>0.01</td><td>99.34</td><td>0.02</td><td>99.34</td><td>97</td><td>0.3</td></tr><tr><td>32</td><td>24792.1</td><td>opt</td><td>0.0</td><td>0</td><td>24792.1</td><td>0.01</td><td>24792.1</td><td>0.01</td><td>24792.1</td><td>0</td><td>0.0</td></tr><tr><td>33</td><td>3079.3</td><td>opt</td><td>0.0</td><td>0</td><td>3079.3</td><td>0.06</td><td>3079.3</td><td>0.01</td><td>3079.3</td><td>0</td><td>0.0</td></tr><tr><td>34</td><td>59431.0</td><td>opt</td><td>0.0</td><td>0</td><td>59431.0</td><td>153.67</td><td>-</td><td>3600.5</td><td>59431.0</td><td>3689</td><td>2.18</td></tr><tr><td>35</td><td>100832.0</td><td>opt</td><td>0.0</td><td>0</td><td>100832.0</td><td>0.03</td><td>100832.0</td><td>0.01</td><td>100832.0</td><td>0</td><td>0.0</td></tr><tr><td>36</td><td>27052.8</td><td>opt</td><td>0.0</td><td>0</td><td>27052.8</td><td>0.44</td><td>-</td><td>3600.66</td><td>27052.8</td><td>427</td><td>0.48</td></tr><tr><td>37</td><td>406009.0</td><td>sub</td><td>1.0</td><td>670</td><td>-</td><td>3662.9</td><td>-</td><td>3600.22</td><td>406023.0</td><td>134167</td><td>3601.37</td></tr><tr><td>38</td><td>-4316.46</td><td>opt</td><td>0.0</td><td>0</td><td>-4316.46</td><td>85.35</td><td>-</td><td>3600.57</td><td>-4316.46</td><td>5271</td><td>3.26</td></tr><tr><td>39</td><td>-42097.1</td><td>opt</td><td>4.0</td><td>17021</td><td>-</td><td>3695.39</td><td>-</td><td>3600.55</td><td>-42097.1</td><td>3445</td><td>2.55</td></tr><tr><td>40</td><td>15916.1</td><td>opt</td><td>0.0</td><td>124</td><td>15916.1</td><td>79.01</td><td>-</td><td>3600.5</td><td>15916.1</td><td>2444</td><td>2.87</td></tr><tr><td>41</td><td>-3187.16</td><td>opt</td><td>0.0</td><td>0</td><td>-3187.16</td><td>0.0</td><td>-3187.16</td><td>0.01</td><td>-3187.16</td><td>97</td><td>0.15</td></tr><tr><td>42</td><td>4529.62</td><td>opt</td><td>0.0</td><td>0</td><td>4529.62</td><td>0.04</td><td>4529.62</td><td>0.01</td><td>4529.62</td><td>0</td><td>0.0</td></tr></tbody></table>
<table><caption>Table 6: Performance of model $M_{HUC}$ solved with CPLEX, the RCSPP algorithm, HA* and BORWin on instances 43 to 83 of set B</caption><thead><tr><th rowspan="2">instance</th><th rowspan="2">value</th><th colspan="3">CPLEX</th><th colspan="2">RCSPP</th><th colspan="2">HA*</th><th colspan="3">BORWin</th></tr><tr><th>gap</th><th>time</th><th>#nodes</th><th>value</th><th>time</th><th>value</th><th>time</th><th>value</th><th>#iter</th><th>time</th></tr></thead><tbody><tr><td>43</td><td>269 050.0</td><td>0.0</td><td>0</td><td>0</td><td>269 050.0</td><td>0.04</td><td>269 050.0</td><td>0.01</td><td>269 050.0</td><td>0</td><td>0.0</td></tr><tr><td>44</td><td>917 201.0</td><td>0.06</td><td>3599.0</td><td>8558238</td><td>-</td><td>3866.17</td><td>-</td><td>3600.4</td><td>917 035.0</td><td>190950</td><td>3601.38</td></tr><tr><td>45</td><td>282 424.0</td><td>sub</td><td>3.0</td><td>5610</td><td>-</td><td>3627.51</td><td>-</td><td>3600.49</td><td>282 425.0</td><td>3858</td><td>2.95</td></tr><tr><td>46</td><td>52 834.5</td><td>opt</td><td>0.0</td><td>0</td><td>52 834.5</td><td>0.06</td><td>52 834.5</td><td>0.03</td><td>52 834.5</td><td>0</td><td>0.01</td></tr><tr><td>47</td><td>459 095.0</td><td>opt</td><td>0.0</td><td>0</td><td>459 095.0</td><td>0.05</td><td>459 095.0</td><td>0.01</td><td>459 095.0</td><td>0</td><td>0.0</td></tr><tr><td>48</td><td>452 277.0</td><td>0.04</td><td>3599.0</td><td>5319419</td><td>-</td><td>3625.98</td><td>-</td><td>3600.47</td><td>452 318.0</td><td>123282</td><td>2254.47</td></tr><tr><td>49</td><td>42 341.8</td><td>opt</td><td>0.0</td><td>0</td><td>42 341.8</td><td>0.06</td><td>42 341.8</td><td>0.02</td><td>42 341.8</td><td>0</td><td>0.0</td></tr><tr><td>50</td><td>-5494.62</td><td>4.65</td><td>3599.0</td><td>1298359</td><td>-</td><td>3671.95</td><td>-</td><td>3600.47</td><td>-5494.62</td><td>91615</td><td>527.29</td></tr><tr><td>51</td><td>40 192.6</td><td>opt</td><td>0.0</td><td>0</td><td>40 192.6</td><td>0.01</td><td>40 192.6</td><td>0.02</td><td>40 192.6</td><td>0</td><td>0.0</td></tr><tr><td>52</td><td>42 283.9</td><td>opt</td><td>10.0</td><td>34235</td><td>-</td><td>3641.65</td><td>-</td><td>3600.54</td><td>42 283.9</td><td>6194</td><td>4.61</td></tr><tr><td>53</td><td>27 442.4</td><td>opt</td><td>0.0</td><td>0</td><td>27 442.4</td><td>0.66</td><td>27 442.4</td><td>0.1</td><td>27 442.4</td><td>31</td><td>0.04</td></tr><tr><td>54</td><td>3 798 460.0</td><td>sub</td><td>0.0</td><td>0</td><td>3 798 740.0</td><td>20.38</td><td>-</td><td>3600.47</td><td>3 798 740.0</td><td>31065</td><td>22.19</td></tr><tr><td>55</td><td>-1957.72</td><td>opt</td><td>2322.0</td><td>898717</td><td>-</td><td>3626.03</td><td>-</td><td>3600.54</td><td>-1957.72</td><td>7688</td><td>19.39</td></tr><tr><td>56</td><td>28 471.9</td><td>opt</td><td>0.0</td><td>0</td><td>28 471.9</td><td>0.01</td><td>28 471.9</td><td>0.02</td><td>28 471.9</td><td>0</td><td>0.01</td></tr><tr><td>57</td><td>3 922 410.0</td><td>sub</td><td>0.0</td><td>352</td><td>-</td><td>3831.41</td><td>-</td><td>3600.29</td><td>3 922 560.0</td><td>76710</td><td>395.57</td></tr><tr><td>58</td><td>716 594.0</td><td>opt</td><td>2930.0</td><td>844090</td><td>-</td><td>3692.37</td><td>-</td><td>3600.62</td><td>714 666.0</td><td>193649</td><td>3601.47</td></tr><tr><td>59</td><td>17 577.3</td><td>opt</td><td>2.0</td><td>1768</td><td>17 577.3</td><td>5.06</td><td>17 577.3</td><td>52.03</td><td>17 577.3</td><td>514</td><td>1.34</td></tr><tr><td>60</td><td>25 720.8</td><td>opt</td><td>0.0</td><td>0</td><td>25 720.8</td><td>0.04</td><td>25 720.8</td><td>0.01</td><td>25 720.8</td><td>0</td><td>0.0</td></tr><tr><td>61</td><td>-34801.1</td><td>inf</td><td>9.0</td><td>40790</td><td>-</td><td>3680.74</td><td>-</td><td>3600.56</td><td>-34801.1</td><td>14291</td><td>23.78</td></tr><tr><td>62</td><td>10 607.8</td><td>opt</td><td>16.0</td><td>13431</td><td>10 607.8</td><td>290.81</td><td>10 607.8</td><td>2028.97</td><td>10 607.8</td><td>3113</td><td>8.36</td></tr><tr><td>63</td><td>935 608.0</td><td>opt</td><td>0.0</td><td>0</td><td>935 608.0</td><td>0.05</td><td>935 608.0</td><td>0.02</td><td>935 608.0</td><td>0</td><td>0.0</td></tr><tr><td>64</td><td>95 093.1</td><td>inf</td><td>0.0</td><td>0</td><td>95 093.1</td><td>0.01</td><td>95 093.1</td><td>0.01</td><td>95 093.1</td><td>286</td><td>0.53</td></tr><tr><td>65</td><td>379 220.0</td><td>opt</td><td>0.0</td><td>0</td><td>379 220.0</td><td>0.01</td><td>379 220.0</td><td>0.01</td><td>379 220.0</td><td>0</td><td>0.0</td></tr><tr><td>66</td><td>138 473.0</td><td>0.37</td><td>3599.0</td><td>651399</td><td>138 473.0</td><td>325.18</td><td>-</td><td>3600.7</td><td>138 473.0</td><td>48951</td><td>381.27</td></tr><tr><td>67</td><td>703 224.0</td><td>opt</td><td>0.0</td><td>0</td><td>703 224.0</td><td>0.02</td><td>703 224.0</td><td>0.02</td><td>703 224.0</td><td>0</td><td>0.0</td></tr><tr><td>68</td><td>94 516.4</td><td>opt</td><td>0.0</td><td>57</td><td>94 516.4</td><td>0.02</td><td>94 516.4</td><td>0.02</td><td>94 516.4</td><td>32</td><td>0.62</td></tr><tr><td>69</td><td>66 301.3</td><td>inf</td><td>7.0</td><td>4272</td><td>-</td><td>3659.77</td><td>-</td><td>3600.33</td><td>66 301.3</td><td>2960</td><td>3.43</td></tr><tr><td>70</td><td>-2612.74</td><td>opt</td><td>0.0</td><td>0</td><td>-2612.74</td><td>0.0</td><td>-2612.74</td><td>0.01</td><td>-2612.74</td><td>0</td><td>0.0</td></tr><tr><td>71</td><td>618 927.0</td><td>opt</td><td>16.0</td><td>16554</td><td>-</td><td>3665.96</td><td>-</td><td>3600.52</td><td>618 927.0</td><td>24436</td><td>111.57</td></tr><tr><td>72</td><td>-842 932.0</td><td>sub</td><td>2.0</td><td>588</td><td>-</td><td>3608.11</td><td>-</td><td>3600.32</td><td>-842 891.0</td><td>2503</td><td>4.41</td></tr><tr><td>73</td><td>30 603.6</td><td>opt</td><td>27.0</td><td>39539</td><td>-</td><td>3652.74</td><td>-</td><td>3600.37</td><td>30 603.6</td><td>23572</td><td>48.14</td></tr><tr><td>74</td><td>68 651.0</td><td>0.1</td><td>3599.0</td><td>5690332</td><td>-</td><td>3663.35</td><td>-</td><td>3600.73</td><td>68 651.0</td><td>8209</td><td>15.63</td></tr><tr><td>75</td><td>15 102.9</td><td>opt</td><td>0.0</td><td>0</td><td>15 102.9</td><td>4.68</td><td>-</td><td>3600.54</td><td>15 102.9</td><td>4086</td><td>3.91</td></tr><tr><td>76</td><td>4976.64</td><td>opt</td><td>0.0</td><td>0</td><td>4976.64</td><td>0.06</td><td>4976.64</td><td>0.02</td><td>4976.64</td><td>0</td><td>0.0</td></tr><tr><td>77</td><td>-6975.34</td><td>opt</td><td>1.0</td><td>1676</td><td>-6975.34</td><td>57.44</td><td>-</td><td>3600.63</td><td>-6975.34</td><td>1202</td><td>1.35</td></tr><tr><td>78</td><td>-3209.93</td><td>opt</td><td>0.0</td><td>0</td><td>-3209.93</td><td>0.0</td><td>-3209.93</td><td>0.01</td><td>-3209.93</td><td>0</td><td>0.0</td></tr><tr><td>79</td><td>57 148.6</td><td>opt</td><td>524.0</td><td>446548</td><td>-</td><td>3671.69</td><td>-</td><td>3600.48</td><td>57 148.6</td><td>176537</td><td>1347.51</td></tr><tr><td>80</td><td>14 650.7</td><td>opt</td><td>0.0</td><td>0</td><td>14 650.7</td><td>31.81</td><td>-</td><td>3600.64</td><td>14 650.7</td><td>6600</td><td>5.74</td></tr><tr><td>81</td><td>69 986.4</td><td>opt</td><td>32.0</td><td>73328</td><td>-</td><td>3705.61</td><td>-</td><td>3600.38</td><td>69 986.4</td><td>147543</td><td>1148.09</td></tr><tr><td>82</td><td>31 375.2</td><td>sub</td><td>0.0</td><td>0</td><td>-</td><td>3609.26</td><td>-</td><td>3600.6</td><td>31 375.9</td><td>95735</td><td>476.4</td></tr><tr><td>83</td><td>164.95</td><td>opt</td><td>0.0</td><td>600</td><td>164.95</td><td>0.01</td><td>164.95</td><td>1.59</td><td>164.95</td><td>492</td><td>0.47</td></tr></tbody></table>