arXiv:1606.09279v4 [] 30 Jan 2017

The matching relaxation for a class of generalized set
partitioning problems
Evellyn Cavalcante1 , Johan Oppen1 , Phillippe Samer1 , and Sebastián Urrutia2
1

Molde University College, P.O.box 2110, N-6402, Molde, Norway,

evellyn.cavalcante@gmail.com, johan.oppen@himolde.no, phillippes@gmail.com
2

Universidade Federal de Minas Gerais, Av. Antônio Carlos 6627, 31270-010, Belo Horizonte, MG, Brazil,
surrutia@dcc.ufmg.br

January 29, 2017

Abstract
This paper introduces a discrete relaxation for the class of combinatorial optimization problems which can be described by a set partitioning formulation under packing
constraints. We present two combinatorial relaxations based on computing maximum
weighted matchings in suitable graphs. Besides providing dual bounds, the relaxations
are also used on a variable reduction technique and a matheuristic. We show how that general method can be tailored to sample applications and, in particular, perform a successful
computational evaluation with benchmark instances of a problem in maritime logistics.
Keywords: dual bounds, matchings, set partitioning, integer programming.
Remark: a preliminary, four-page abstract of this work was presented at 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization.
Acknowledgement: this work was carried out within the Port-Ship Coordinated
Planning project, supported by the Norwegian Research Council under project number
227084/O70.

1

1

Introduction
Consider the following problem, which the reader might recognize from a range of applica-

tion domains. A set of n tasks is to be performed, and the problem solver has to decide for an
execution mode to them. To each individual task corresponds a particular set of acceptable
execution modes to perform it. Moreover, each execution mode comprises a well-defined cost
and resource usage (possibly many, e.g. time, space, tools, human workers). Since the finite
resources are to be shared among tasks, the problem solver also counts on an oracle capable
of determining in constant time whether a selection of execution modes to different tasks is
compatible. Any solution prescribing the assignment of incompatible execution modes is thus
rendered infeasible.
We concern the class of problems which, at its core, can be cast as follows. Given sets
of acceptable assignments to each individual task, and compatibility information among any
selection of assignments, find a compatible setting for the n tasks of minimum total cost. To
clearly outline our contributions and the scope of our investigation, we first give a precise
formulation of the class of problems we concern, which we refer to as the generalized set
partitioning problem (GSPP).
The base GSPP

Let T be the set of tasks, and R = R1 × R2 × . . . × Rk be the set of

tuples identifying resource usage, i.e. combinations of an option for resource R1 , an option
for resource R2 , and so forth. Also define Ωi as the set of feasible assignments to task i: each
element in Ωi assigns a subset of resources in R (characterizing an execution mode) to complete
an individual task. We denote Ω = {x : x ∈ Ωi , i = 1, . . . , n}. Binary decision variables y ∈
B|Ω| thus indicate which individual assignments are used in the solution. Let cj ∈ Q denote
the cost of an assignment yj to an individual task, consisting of a computable function of
the total resource usage on that individual assignment alone. Finally, the coefficient matrices
are as follows. A ∈ B|T |×|Ω| associates each column with a single task: aij is equal to one if
yj refers to an assignment for task i; otherwise, it is equal to zero. B ∈ B|R|×|Ω| represents
resource usage tuples: brj is one iff the given combination r ∈ R of individual resources is used
in the assignment yj . Then, we build on the following integer programming (IP) formulation:
2

z = min


X


cj yj : y ∈ Pgspp ∩ B|Ω|




,

(1)



j∈Ω

where Pgspp denotes the polyhedral region defined by:
X

aij yj = 1

∀i ∈ T

(2)

X

brj yj ≤ 1

∀r ∈ R

(3)

yj ≤ 1

∀j ∈ Ω

(4)

yj ≥ 0

∀j ∈ Ω

(5)

j∈Ω

j∈Ω

Set partitioning constraints (2) ensure that all tasks are served by exactly one assignment,
while set packing in (3) forbids overlapping of assignments in each resource combination slot.
We note that, if incompatibilities among tasks reduce to pairwise relations, the latter class
of inequalities could be replaced by any set packing relaxation, such as edge inequalities:
xu + xv ≤ 1, for each edge (u, v) in a conflict graph (Atamtürk et al., 2000). Constraints (4)
and (5) correspond to the linear relaxation of the binary programming formulation.
This formulation has connections to different disciplines in combinatorial optimization. It
is similar to some variations of the assignment problem (Pentico, 2007). It can be seen as the
scheduling of jobs on parallel machines minimizing total processing time, as we illustrate in
Section 4.1 with a problem studied by Lalla-Ruiz and Voß (2016b). And the formulation is
also an instance of the mixed set covering, packing and partitioning problem, investigated by
Kuo and Leung (2016), following a longer tradition of studying perfect and ideal 0–1 matrices.
The authors perform the first polyhedral investigation of the mixed problem, and argue on
its relevance and number of applications, notwithstanding the fact that it has drawn little
attention in the literature so far. For the interested reader, we indicate in Section 6 more
related problems and situate the above GSPP structure in the set partitioning literature.
Our contributions

The previous formulation can have a huge (though polynomial) number

of variables. This is in consonance with the compromise between: (i) the complexity in the
3

representation of each execution mode to a task, i.e. the level of details included, and (ii) the
computing time to solve the resulting problem.
The main idea of this paper is to show that one can use interesting, combinatorial constructions over the variables to find lower bounds to (1). Moreover, since the bounds are
purely combinatorial, we suggest that its computation might be faster than linear programming (LP) relaxation ones, although possibly weaker. Even if the combinatorial bounds prove
to be weaker, we argue that the construction itself might be interesting as a building block,
e.g. in algorithmic approaches which depend on the computation of dual bounds, as we
illustrate with a variable probing method and a matheuristic in Section 3.
To summarize, the contributions of this paper are:
• We claim attention to the GSPP structure (1) − (5) as interesting in its own right, and
that there exists a range of applications of it in the recent literature. Furthermore, the
key ideas we present can be extended to accommodate application-specific details, as
we illustrate in Section 4.
• In Section 2, we introduce two graph representations relaxing part of the assignments
in Ω, and show that weighted matchings in each of them yield lower bounds to problem
(1), and that one of the constructions is stronger than the other.
• From an algorithmic standpoint, the combinatorial constructions allow for an embedding
in a model-based heuristic framework (or matheuristic), presented in Section 3. We
argue that the algorithm could only be conceived because of the efficient constructions,
as opposed to the corresponding time to solve LP relaxations.
• Preliminary computational experiments with that matheuristic, using benchmark instances from a logistics problem, indicate that it is able to find near-optimal solutions
in reduced time (Section 5).

2

Matching relaxations of the GSPP
In this section, we present the main contributions of the paper.
4

For the sake of clearness, we highlight from the problem definition in the Introduction
three conditions for our key ideas to work. First, we assume that each individual assignment
yj has a cost cj which is independent of the assignments to other tasks, so that its contribution
to the objective function is computable when assuming yj is used in the solution. We also
assume that it is possible to determine in constant time whether a selection of individual
assignments is compatible. Finally, the GSPP structure we study is limited to formulations
with a polynomial number of variables, such that the set Ω can be enumerated before solving
the resulting IP. While this immediately rules out a series of applications (typically solved
by column generation algorithms), we hope that our discussions and numerical results in the
remainder of the paper could settle the relevance of the class of problems we concern.
We start by introducing two relaxations for the GSPP formulation, which yield dual
bounds to the optimal value of the objective z in (1). Note that the most naı̈ve approach
would be to discard all the packing constraints in (3) and simply pick the cheapest individual
assignment to each task, which would provide a most trivial lower bound. In the following,
we aim to discard less of those constraints. We construct two simple, undirected graphs,
representing a subset of the enumerated assignments. Throughout the text, we use the linear
map c : Ω → Q from the space of assignments to their costs, such that c(yj ) = cj .
We define the graph G1 (T, E1 ), with a vertex for each task. The set E1 includes an edge
(i, j) if the individual assignments of best cost for tasks i and j are not compatible with each
other. Let c′j denote the minimum cost assignment for task j; that is, c′j = min{c(yj ) : yj ∈
Ωj }. Analogously, let c′′j be the second minimum cost assignment for j. The cost c1 (i, j) of
an edge in G1 is defined by the least difference among such costs, for the corresponding tasks
i and j. That is: c1 (i, j) , min{(c′′i − c′i ), (c′′j − c′j )}. Then, the following bound on the cost
of any feasible solution holds.
Theorem 1. Let M ⊆ E1 denote a maximum weighted matching in G1 , and w(M ) =
P
P
′
e∈M c1 (e) be its weight. Then LB1 , w(M ) +
j∈T cj is a lower bound to the optimal
value z in (1).
Proof. The selection of the best individual assignments for each task corresponds to relaxing
all the constraints in (3). Therefore, this is a trivial lower bound to the cost of any feasible
5

solution, and amounts to

P

j∈V

c′j .

Starting with the trivial selection of best individual assignments, the weight of an edge
(i, j) ∈ E1 corresponds to the minimum cost increase due to exchanging one such assignment
for the second best. Clearly, this new pair of assignments for tasks i and j can still be
infeasible, but the sum of their costs is a lower bound to the cost of any compatible assignment
for these tasks.
Note that we cannot imply that the accumulated costs of edges incident to a same vertex
are necessary, because the graph does not provide information about which of the extremes
of an edge assumes the second best assignment; it is even possible that, following such an
exchange, other edges might not exist. However, one can consider any matching in G1 , corresponding to disjoint pairs of tasks whose best assignments are not compatible. Therefore,
P
′
the weight of any matching is a required cost increase over
j∈T cj , implied by the pairwise incompatibility of the corresponding individual assignments. In particular, a maximum
weighted matching corresponds to the strongest such bound in G1 .
Our second dual bound strengthens the information on the cost of compatible assignments
between pairs of tasks. Let G2 (T, E2 ) denote a complete graph, with a vertex for each task.
Define the cost c2 (i, j) of an edge in E2 as the cheapest compatible assignments for tasks i
and j, that is: c2 (i, j) , min{c(yi ) + c(yj ) : yi ∈ Ωi , yj ∈ Ωj , yi and yj are compatible}. Then,
we have the following result.
Theorem 2. Let M ⊆ E2 be a maximum weighted matching in G2 . Then, LB2 ,

P

e∈M c2 (e)

is a lower bound to the optimal value z in (1).
Proof. The weight of a single edge (i, j) ∈ E2 is the sum of the minimum cost assignments for
tasks i and j, complying with the compatibility constraints among them. That is: these two
assignments alone are compatible. A selection of edges not sharing a vertex (i.e. a matching)
thus corresponds to pairing up tasks and determining their best compatible assignments,
which is required in any solution satisfying packing constraints (3). Therefore, the weight of
any matching in G2 is a lower bound to the cost of a feasible solution, since this clearly relaxes
constraints regarding the compatibility of unpaired tasks. A maximum weighted matching
6

thus provides the strongest such bound in G2 .
Although this result holds for any number of tasks, it would be unnecessarily weaker for
odd |T |, since some vertex would not be covered by the matching, thus not contributing to the
lower bound. To circumvent this, in the case that |T | is odd, we simply add to G2 an artificial
vertex s, with edges to every other vertex i, with costs c2 (s, i) = min{c(yi ) : yi ∈ Ωi }.
We conclude with a result on the relative strength of the bounds obtained in the two
relaxations. Note that, in the simple case where all the best individual assignments are
pairwise compatible with each other, we verify: (i) the graph G1 has no edges, and the bound
P
LB1 corresponds to trivial bound j∈T c′j ; (ii) any perfect matching M in the graph G2
has maximum weight, amounting to the sum of costs of the best individual assignments.
P
P
P
Therefore, the bounds are equal: LB2 = (i,j)∈M c2 (i, j) = (i,j)∈M (c′i + c′j ) = u∈T c′u =
LB1 . We show below that the second bound is actually stronger than the first.
Theorem 3. The lower bound attained from graph G2 (T, E2 ) is stronger than that from graph
G1 (T, E1 ); i.e. for any given problem instance, LB2 ≥ LB1 holds, and LB2 > LB1 for at
least one case.
Proof. First, we remark that specific cases where LB2 > LB1 are intuitive. It suffices to
have a pair of vertices for which there are no compatible assignments employing the cheapest
execution mode for one of them.
In the following, we suppose there were an instance where LB1 > LB2 . We build a
matching in G2 with cost at least LB1 , showing that the hypothesis is absurd. We assume
without loss of generality that the number of vertices |T | is even, since, as described above,
we suggest including an artificial vertex in the corresponding graph instances with odd |T | to
get a stronger bound.
For any edge (i, j) ∈ E1 , we can compare the cost functions in G1 and G2 ; recall that
the latter graph is complete. By definition, c1 (i, j) corresponds to the minimum cost increase
implied by the incompatibility of the best individual assignments for i and j, while c2 (i, j)
corresponds to the actual sum of the costs of the best compatible assignments. It follows

7

that:
c2 (i, j) ≥ c′i + c′j + c1 (i, j)

(6)

Let M1 ⊆ E1 be a maximum weighted matching in G1 , which thus yields the lower bound
LB1 from that graph. We define the analogous set of edges in G2 as M2 = {(i, j) ∈ E2 :
there exists the edge (i, j) ∈ M1 }. The set M2 is a matching in G2 , by construction.
We distinguish two cases. If M1 is perfect, then M2 is perfect as well since both graphs
have the same vertex set. We can infer about their weights:

w(M2 ) =

X

c2 (i, j) ≥

X

(c′i + c′j + c1 (i, j)) =

c1 (i, j) +

X

c′u = LB1 , (7)

u∈T

(i,j)∈M1

(i,j)∈M2

(i,j)∈M2

X

where the first inequality holds by (6), and the second equality is true because the matchings
are perfect.
If M1 is not perfect, there are pairs of vertices (x, y) not covered by M1 . By hypothesis,
M1 has maximum weight; hence (x, y) 6∈ E1 , i.e. the individual assignments of least cost for
x and y are compatible. Therefore, the edge in G2 corresponding to each such pair (x, y) has
cost c2 (x, y) = c′x + c′y . We can extend M2 to a perfect matching M2′ in G2 by arbitrarily
connecting pairs of vertices not yet covered by M2 . Let C denote the set of edges selected this
P
P
way, such that M2′ , M2 ∪ C, and (x,y)∈C c2 (x, y) = (x,y)∈C c′x + c′y . Then, analogously to
the previous case, we have:
w(M2′ ) =

c2 (i, j) +

X

(c′i + c′j + c1 (i, j)) +

X

c1 (i, j) +

X

c2 (x, y)

(x,y)∈C

(i,j)∈M2

=

c2 (x, y)

(x,y)∈C

(i,j)∈M2

≥

X

X

X

c′u

u∈T

(i,j)∈M2

= LB1 ,

(8)

where the last equalities hold because M2′ covers all vertices.
Therefore, the matchings in G2 built in both cases (7) and (8) have weight at least LB1 ,

8

providing a lower bound on LB2 , which is defined as the maximum weight of a matching in
G2 . Since we start with a general input instance, the hypothesis that LB1 > LB2 could hold
is absurd, and we always verify that LB2 ≥ LB1 .

3

Embedding the relaxation in a matheuristic algorithm
This section extends our key idea, the matching relaxation of the GSPP structure, into

algorithmic results. First, we derive in Section 3.1 a preprocessing method to probe and
discard variables that imply a suboptimal solution, as it is done in the work of Iris et al.
(2015) in the context of a port logistics problem. Next, we present in Section 3.2 a matheuristic
algorithm to find approximate solutions to the problem in reduced computational time.

3.1

Preprocessing method for variable reduction

The previous results yield lower bounds on the optimal value z of problem (1), and can
also be extended to a preprocessing method. The goal is to fix at null value (or, equivalently,
remove) a number of decision variables in the resulting model after the enumeration of feasible
assignments, while preserving the optimal, exact solution.
It is worth remarking that, since this technique is applied prior to the model optimization,
such a proposal can be integrated with any approach based on enumerating the variables of
the GSPP formulation and solving the resulting model with an integer linear programming
algorithm. This strategy has already been adopted by Iris et al. (2015), using lower bounds
implied by probing the selection of a single assignment or a pair of assignments for two
different tasks. In Section 5, we compare their method with the one we propose.
The next result assumes that an upper bound to z is available. First, we temporarily
assume that a given assignment yk ∈ Ωk is fixed in the solution. We define the complete graph
G2,k (T \{k}, E2,k ). The corresponding edge costs c2,k regard the best compatible assignments

9

for two given tasks, which are also compatible with yk . That is:

c2,k (i, j) = min{c(yi ) + c(yj ) : yi ∈ Ωi , yj ∈ Ωj ,
yi and yj are compatible with each other and with yk }

Finally, we evaluate the increase on the lower bound LB2 from Theorem (2) implied by fixing
the assignment yk : if the new lower bound exceeds a known upper bound, we conclude that
this assignment cannot be part of an optimal solution. The result is summarized as follows.
Proposition 1. Let LB2,k denote the lower bound from Theorem 2 determined over G2,k .
Given any upper bound U B to z in (1), if c(yk )+LB2,k > U B, then there is no optimal solution
which includes the assignment yk ∈ Ωk , and the corresponding variable can be removed from
the model.
Therefore, we have an iterative algorithm for removing unnecessary variables in the model,
while preserving all optimal solutions of the problem. For each feasible assignment in the
GSPP formulation, one need only evaluate the new lower bound as depicted above.
Note that an analogous method could be derived from Theorem 1. Nevertheless, it follows
immediately from Theorem 3 that it cannot be stronger, i.e. it cannot remove a variable which
the result in Proposition 1 does not.

3.2

Combinatorial ranking matheuristic

We introduce next an algorithm belonging to the class of matheuristics, or model-based
heuristics, which integrate heuristics and mathematical programming methods (Maniezzo et al.,
2010; Ribeiro and Maniezzo, 2015). Specifically, we employ the combinatorial relaxation information to obtain a reduced model, which is optimized next with an integer linear programming solver. We remark that previous strategies in the matheuristics literature include
solving a reduced model, e.g. after the heuristic removal of variables (Fanjul-Peyro and Ruiz,
2011; Stefanello et al., 2015). Even in the context of a subproblem of the logistics application
that we use to illustrate our ideas (see Section 4.3), Mauri et al. (2008) present an evolutionary approach to generate columns using dual values in the LP relaxation as a fitness measure,
10

and Lalla-Ruiz and Voß (2016a) employ an exact solver to partially optimize components of
a previous solution using the popmusic metaheuristic.
First, note that every solution to the GSPP formulation consists of only |T | ≪ |Ω| assignments. One could wonder if there would be a fast method for classifying variables, such
that high quality solutions could be consistently achieved using only a fraction of the best
ranked variables. In this context, we discard the optimality certificate, and seek a high quality
solution in reduced computation time.
The core of the method we propose is depicted in Algorithm 1, which ranks and selects a
subset ΩF of variables from the GSPP formulation. The selection builds on the combinatorial
bound LB2,k from Proposition 1. The bound is denoted by ∆ in the algorithm, and computed
on the loop starting at line 3. The set of selected variables ΩF corresponds to a subset of
the polyhedron Pgspp , and optimizing over it provides an upper bound z̄ ≥ z to the original
problem (1). As we indicate in preliminary computational results (Section 5), this bound
can match the optimal value for benchmark instances of an application in port logistics even
when using a relatively small fraction of variables.
The algorithm parameters are as follows.
σ : the percentage of the best ranked variables to include in the final model;
µ : the minimum number of variables corresponding to each task, which the algorithm should
ensure (when available) in the final model.
The latter parameter µ ensures that each task has a number of assignment options (as
selected in the loop starting at line 13), while σ controls the selection of variables among
those implying the best dual bounds (loop starting at line 8). It would be natural to consider
algorithm variations, e.g. selecting an exact number of variables, or performing a statistical
study of the parameters. Both tasks could be approached in future work.
We remark that, since approaching a problem with this algorithm gives up on the optimality certificate, it is not necessary to reach a null duality gap in the resulting model to end the
algorithm. Such a strategy may be interesting to meet runtime requirements in challenging
applications.
11

Algorithm 1: combinatorial ranking
Input

: initial set of variables Ω, number of tasks |T |

Output

: set ΩF of variables selected for the final model

Parameters: minimum percentage σ of the best ranked variables, minimum number of
variables per task µ
1

ΩF ← ∅

2

∆(k) ← 0 for each yk ∈ Ω

3

foreach yk ∈ Ω do

4

Let G2,k be the graph of compatible assignments, defined in Proposition 1

5

Let M be a maximum weighted matching in G2,k

6

// lower bound implied by using this variable; see Prop.1
P
∆(k) ← c(yk ) + e∈M c2 (e)

7

Let L denote the list of variables in Ω, ordered by increasing values of ∆

8

while |ΩF |/|Ω| < σ do

9
10

Let d be the least ∆ value of a variable in L
foreach variable yk ∈ L with ∆(k) = d do

11

ΩF ← ΩF ∪ {yk }

12

L ← L\{yk }

13
14

foreach task i = 1, . . . , |T | do
while |{y ∈ ΩF : y is an assignment for i}| < µ and L contains a variable referring to i do

15

Let yi ∈ L be a variable referring to i, of least ∆

16

ΩF ← ΩF ∪ {yi }

17

L ← L\{yi }

18

return ΩF

We argue that Algorithm 1 is only useful because of the efficient combinatorial bound,
as opposed to the corresponding time to solve LP relaxations in the loop starting at line 3.
That is, instead of solving as many LP problems as |Ω| to determine the lower bounds ∆
implied by fixing each variable, we reduce the computational effort to (|Ω| iterations of) the
construction of graph G2,k and the solution of a weighted matching problem on a graph with
just |T | vertices.
In Section 5 we present the results of a successful computational experience this algorithm,
using benchmark instances from a maritime logistics application. Concerning the execution
time matter, even in the most difficult set of instances, solutions within 4% of the optimal value

12

are provided, with an average of 30% of the time required by methods recently introduced in
the literature. On the other hand, for the sake of illustration, even if it took 1 second to build
and solve the corresponding LP relaxation, a medium-size instance with 100.000 assignments
would already take over a day to finish.

4

Sample applications
In this section we aim to give straightforward examples from the literature, in which rele-

vant applications are formulated as different generalizations of a set partitioning problem. In
each case, we give a brief problem definition, transcribe its IP formulation from the literature,
and show at intuition level that they are amenable to the combinatorial constructions from
Sections 2 and 3.
The application in Section 4.1 is a job scheduling problem, whose formulation is in direct
correspondence with the GSPP structure that we present in the Introduction. As for the
applications in crew disruption management (Section 4.2) and port logistics (Section 4.3), we
highlight the interesting possibility to translate application features into small extensions of
the matching relaxation.

4.1

Job scheduling in parallel machines

Lalla-Ruiz and Voß (2016b) concern the following problem, denoted Parallel Machine
Scheduling with Step Deteriorating Jobs. Suppose that m identical, parallel machines are
available in a planning horizon h, and that n jobs are to be scheduled, each consuming a
processing time varying among two constants, as follows. If the assigned starting time is on a
deteriorating date di or before, the job takes a base processing time ai ; if it starts after that
date, it requires processing time ai + bi . For each job i = 1, . . . , n, constants ai , bi and di are
input parameters. The objective function is to minimize the sum of the completion times of
all jobs.
The base formulation used by those authors corresponds precisely to the GSPP structure
in (1) − (5), as we describe next. The set of columns is also denoted by Ω. Each column

13

corresponds to a variable xw , representing a feasible assignment to an individual job. Thus, an
assignment for job w in this problem encodes: the particular machine in which it is processed,
the starting and finishing times, and a fixed cost cw . Any selection of individual assignments
to different jobs is compatible if no machine is used at a same time slot by more than one job.
Lalla-Ruiz and Voß also define the index set P such that |P | = m × h, corresponding to
machine and time slot combinations; this corresponds to k = 2 resources in our base structure.
Then, using binary coefficient matrices A ∈ Bn×|Ω| and B ∈ B|P |×|Ω| defined likewise (2) and
(3) to express partitioning and packing constraints, they give the following formulation:

min

X

cw xw

(9)

w∈Ω

subject to:
X

Aiw xw = 1

i = 1, . . . , n

(10)

X

Bpw xw ≤ 1

∀p ∈ P

(11)

∀w ∈ Ω

(12)

w∈Ω

w∈Ω

xw ∈ {0, 1}

We thus conclude this is trivially equivalent to the GSPP structure under investigation
in this paper. Therefore, all among the combinatorial constructions of graph G2 and the
bound LB2 (Theorem 2), the variable probing test (Proposition 1), and the matheuristic in
Algorithm 1, carry over to this problem as presented before.
The next applications are more interesting, in the sense that the base GSPP structure
provides only a relaxation of the formulated problem, making space for application-specific
tweaks. Nevertheless, we highlight the fact that the base structure can, as it is, model such
relevant topics as the job scheduling problem above.

4.2

Crew disruption management

Rezanova and Ryan (2010) investigate the train driver recovery problem, which aims to
find the best assignment of tasks to replacement duties for train drivers, when the railway

14

operator has to recover from a disruption. In the occasion of internal or external failures (e.g.
due to track conditions, accidents, or passanger delays), such that the slack time built into
the timetable is not enough to restore the original plan, a recovery mission with the re-routing
or cancelling of trains is performed. Dealing with the propagation of disruptions within the
schedule makes the problem even more difficult for the operator.
The application itself includes a range of details which is beyond the scope of our discussion. While we limit the discussion below to the optimization of recovery duties, the elegant
work of Rezanova and Ryan concerns several auxiliary issues around that central matter,
and they evaluate their contributions in the context of real-life data from a Danish railway
operator.
We start with a so-called disruption neighbourhood: let K denote a subset of train drivers
whose duties include at least one disrupted train task within a given recovery period (which is
our planning horizon). The remaining drivers keep their former duties, and are not included
in the model. Also let N denote the set of all tasks originally assigned to drivers in K during
the period, while P k denotes the set of acceptable recovery duties for each driver k ∈ K. In
this model, each individual assignment (such a recovery duty p ∈ P k ) encodes a subset of
tasks in N and a fixed cost ckp , corresponding to a measure of its unattractiveness to driver k.
The goal of the train driver recovery problem is to find a selection of individual assignments
to each driver in K (i.e. a feasible recovery duty) of least total cost, such that each task in
N is covered exactly once. To this end, Rezanova and Ryan use binary decision variables xkp ,
set to one iff duty p ∈ P k is chosen. They also define a coefficient matrix analogous to B in
the packing constraints (3) of the GSPP structure: let A, with |N | lines and a column for
each duty of each driver, be such that akip is one if task i is covered by duty p ∈ P k , and zero
otherwise. Now we can repeat their formulation, in (13) − (16) below.
The transformation of this formulation into the GSPP structure we consider allows for
two possible relaxations. In each case, we describe what is relaxed, what corresponds to the
packing constraints, and compare the combinatorial constructions and bounds.

15

min

X X

k∈K

ckp xkp

(13)

p∈P k

subject to:
X

xkp = 1

∀k ∈ K

(14)

∀i ∈ N

(15)

∀p ∈ P k , ∀k ∈ K

(16)

p∈P k

X X

akip xkp = 1

k∈K p∈P k

xkp ∈ {0, 1}

A first, more natural, approach would be to relax equality constraints for tasks, allowing
arbitrary i ∈ N to remain uncovered in the solution. That is, we replace (15) by:
X X

akip xkp ≤ 1

∀i ∈ N

(17)

k∈K p∈P k

Then, formulation (13), (14), (16), (17) is a relaxation of the one by Rezanova and Ryan, and
it can also be viewed as an instance of the base GSPP structure with a single shared resource
(k = 1). In this case, the new, combinatorial relaxation yielding the bound in Theorem 2
consists of solving the weighted matching problem in a complete graph G2 , with a vertex for
each driver, such that the cost of an edge (i, j) corresponds to the cheapest, non-overlapping
duties for the drivers i and j. Here, non-overlapping means only that no task is included in
both duties of any pair of drivers. The bound thus sums up to pairing up drivers and finding
cheapest pairwise compatible combinations; some tasks will likely remain uncovered, others
might be included in duties of two or more (unpaired) drivers.
In the real world instances solved by those authors, we verify that |K| and |N | have
the same order of magnitude. Then, the reunion of all duties in P k should be larger than
these: matrix A should have many more columns than lines. Therefore, the improvement
of the bound described above, compared to simply removing all constraints in (15), could
be negligible. Interestingly, since the formulation has two partitioning constraints, one can

16

conceive an alternative approach, relaxing instead the equality in constraints (14) into:
X

xkp ≤ 1

∀k ∈ K

(18)

p∈P k

We therefore regard the integer program (13), (15), (16), (18) as a new relaxation, which
requires that all tasks are covered exactly once, while allowing some drivers to remain idle.
From this point, the new matching relaxation, attaining the bound from Theorem 2 for this
application, builds on a complete graph, with a vertex for each task. Now, the weight of an
edge (i, j) is determined by the cheapest pair of recovery duties covering both taks i and j
exactly once, in which no driver is assigned two different duties. That is, the compatibility
oracle would return the cost of either: (i) a single duty for the same driver, including both
tasks, or (ii) two duties, for different drivers, each covering one of the tasks but not the
other. We remark that imparting more application details on the oracle decision for pairwisecompatible assignments could increase the edge weights and, consequently, strengthen the
matching bound.

4.3

Port logistics

Our last sample application is also the subject matter of our preliminary computational
evaluation, in the next section. The Berth Allocation and Quay Crane Assignment Problem
(BACAP) aims to allocate a berthing time, a position in the quay, and a number of quay
cranes (QCs) for arriving vessels in a seaport container terminal. Feasible assignments in
the BACAP need to fulfil requirements on desired berthing period and position, and an
agreement on the use of QCs. General reviews and a taxonomy to compare related work
can be found in the surveys of Stahlbock and Voß (2008), Bierwirth and Meisel (2010), and
Bierwirth and Meisel (2015).
We follow the presentation by Iris et al. (2015), who give a precise description of the
application characteristics, and places their model for the BACAP in a convincing place in
related literature. Let V be the set of vessels, T be the set of time slots in the planning
horizon, L be the set of berthing positions in the quay, and Q be the number of available

17

QCs. Also define the set of berthing time/position combinations P = T × L; this corresponds
to k = 2 shared resources in our base GSPP structure. They define the set Ω as we have used
throughout this paper: the complete set of feasible individual allocations. In this case, each
element in Ω encondes a position in the quay, time slots and a number of cranes to serve a
given vessel, besides its cost cj , which depend on QC usage, deviations from parameters on
the desired position on the quay and expected starting and finishing times for the service.
Binary decision variables y ∈ B|Ω| indicate which individual assignments are used in the
solution. Finally, the coefficient matrices are in accordance with those in our description of
the base GSPP, as we describe next. A ∈ B|V |×|Ω| associates each column with a single vessel:
aij is equal to one if column j refers to an assignment for vessel i; otherwise, it is equal to
zero. B ∈ B|P |×|Ω| represents berths as combinations of time intervals and quay positions:
bpj is one iff the given pair of (time, space) positions corresponding to p ∈ P is used in the
assignment yj . An element of Q ∈ Z|T |×|Ω| determines how many QCs are used by yj in time
period t. Then, the BACAP formulation described by Iris et al. (2015) corresponds to:

min

X

cj yj

(19)

j∈Ω

subject to:
X

aij yj = 1

∀i ∈ V

(20)

X

bpj yj ≤ 1

∀p ∈ P

(21)

X

qtj yj ≤ Q

∀t ∈ T

(22)

∀j ∈ Ω

(23)

j∈Ω

j∈Ω

j∈Ω

yj ∈ {0, 1}

Set partition constraints (20) ensure that all vessels are served by exactly one assignment,
while set packing in (21) forbid overlapping of vessel assignments in each single time/space
slot. Inequalities (22) guarantee that QCs availability in the terminal is respected.
It is clear, then, that one need only relax the inequalities (22) on the QC availability
bound to view the formulation by Iris et al. as an instance of the GSPP structure we concern.
18

The matching relaxation from Theorem 2 can thus be determined on a complete graph, with
a vertex for each vessel, where the cost of an edge amounts to the weight of a cheapest,
compatible pair of assignments to the corresponding vessels.
Finally, we remark that two assignments for different vessels in the BACAP are denoted
compatible if they have no overlap in berthing time and space. Equivalently, representing the
two assignments in a Cartesian plane (with time and space coordinates), they are compatible
iff the corresponding rectangles do not intersect each other. We can further tighten the
definition of compatibility in this application by limiting the combined number of cranes used
by two given assignments to the maximum available in the quay.

5

A computational case study
The goals of the computational evaluation we present are twofold. First, we want to com-

pare the linear programming and the matching relaxations to evaluate the trade-off between
the strength of the bound and the time to compute it. Second, we seek to assess the strength
of the solutions provided by the matheuristic we introduced. Toward these ends, we have
implemented a series of algorithms concerning the last application we described, the Berth
Allocation and Quay Crane Assignment Problem (BACAP). We consider the same benchmark
instances used by Meisel and Bierwirth (2009) and Iris et al. (2015) to evaluate the efficiency
of the proposed algorithms. There are ten instances of three different sizes, with 20 (small),
30 (medium) and 40 (large) vessels.
All algorithms were implemented in C++ language using Gurobi solver version 6.5. To
compute maximum weighted matchings, with the blossom shrinking algorithm by Edmonds
(Edmonds, 1965), we use the efficient implementation available in the open source Library for
Efficient Modeling and Optimization in Networks (LEMON) (Dezső et al., 2011). The time
complexity of that implementation is O(mn log n) in the worst case, where n is the number
of graph vertices and m is the number of edges.
All experiments were run in a machine with an Intel Core i7 4790K (4.00 GHz) CPU
and 16GB of RAM. The solver runtime used in the matheuristic experiments was limited to

19

1800 seconds. The experiments corresponding to the techniques proposed by Iris et al. (2015)
were not time limited. It is important to highlight that all results we present concerning
the work by those authors were evaluated with our own implementation of their algorithms.
Moreover, the numbers concerning their results may have slight variations when compared
to the original work, which we have concluded to be explained by numeric precision matters.
Also, the number of execution threads allowed for Gurobi to solve the model corresponding
to that work is set to 2 in the case of instances with 20 or 30 vessels, while a single thread is
allowed to solve instances with 40 vessels. Since the Gurobi solver needs copies of the complete
model for each execution thread, we verified improved performance using this setting because
no virtual memory is needed.
First, we compare the lower bounds and the runtime to compute the combinatorial relaxation, against the LP relaxation. Table 1 presents the corresponding bounds in columns 3 and
4. Column 5 indicates the percentual difference of the combinatorial bound with respect to
the LP relaxation one. Columns 6 and 7 present the execution time required by each method.
The combinatorial bound can match the LP relaxation value for two instances, but it is
consistently weaker and the difference also grows with the input size. Nevertheless, while
building the model and solving its LP relaxation consumes significant time, building the
graphs representing compatible assignment and solving the corresponding weighted matching
problem is performed very fast, in comparison.
One can thus argue that, when choosing a lower bound to use in the variable reduction
technique or in the matheuristic algorithm, the computational performance of the matching
relaxation is the crucial factor. Since a lower bound must be computed after probing each
variable, and even the smallest instances have tens of thousands of variables, the runtime of
the LP relaxation becomes prohibitive in this context.
Next, we executed different experiments to evaluate the matheuristic algorithm. We
stress again that the matheuristic approach waives the optimality certificate of a solution in
the sake of a reduced computation time. In the following, we verify this outcome and assess
the strength of the solutions attained, in comparison with the exact method in the literature.
Several parameter combinations were tested, with σ ∈ {0.0, 0.1, 0.2, 0.3} and µ ∈

20

Table 1: Results attained with the combinatorial and the linear programming relaxations
Instance
|V |

20

30

40

Lower Bounds

Time (s)

LP

Matching

Difference

LP

Matching

relaxation

relaxation

(%)

relaxation

relaxation

1

885.0

698.0

21.1%

5.61

0.01

2

562.0

562.0

0.0%

0.16

0.00

3

816.5

646.0

20.9%

6.69

0.02

4

762.0

620.0

18.6%

7.37

0.02

5

592.0

516.0

12.8%

1.62

0.01

6

592.0

592.0

0.0%

1.23

0.00

7

722.0

646.0

10.5%

2.77

0.00

8

582.0

532.0

8.6%

4.02

0.00

9

782.0

620.0

20.7%

6.47

0.01

10

930.7

700.0

24.8%

9.34

0.02

LBgapI20

13.8%

ID

11

1,408.8

922.0

34.6%

29.98

0.06

12

891.3

800.0

10.2%

5.23

0.01

13

1,091.7

894.0

18.1%

7.64

0.02

14

1,036.5

880.0

15.1%

12.19

0.02

15

1,600.1

1,046.0

34.6%

36.58

0.09

16

1,137.0

1,008.0

11.3%

7.56

0.01

17

1,084.0

894.0

17.5%

9.07

0.02

18

1,245.0

860.0

30.9%

31.71

0.07

19

1,705.0

1,052.0

38.3%

44.07

0.08

20

1,354.4

22.13

0.03

94.29

0.22

1,008.0

25.6%

LBgapI30

23.6%

21

2,058.8

1,150.0

44.1%

22

1,680.0

1,288.0

23.3%

36.68

0.12

23

2,380.7

1,250.0

47.5%

102.59

0.28

24

2,727.0

1,544.0

43.4%

118.38

0.38

25

1,559.9

1,102.0

29.4%

44.00

0.13

26

2,364.1

1,294.0

45.3%

97.34

0.31

27

1,965.8

1,222.0

37.8%

58.83

0.18

28

2,533.3

1,412.0

44.3%

122.40

0.41

29

2,071.8

1,404.0

32.2%

65.54

0.16

30

1,872.5

1,240.0

33.8%

73.21

0.21

LBgapI40

38.1%

LBgapI|V | stands for the arithmetic mean of the percentual difference in the bounds
for instances with |V | vessels.

{500, 1000, 1500, 2000}. Preliminary evaluations with µ = 0 and different choices for σ had
a poor performance, leading to such an extreme reduction that the resulting model was infeasible for at least one instance, i.e. the corresponding polyhedron does not include a single
integer point. This is important to justify the final step in our algorithm (requiring at least µ
21

variables corresponding to each vessel). The four parameter combinations with σ ∈ {0.0, 0.1}
and µ ∈ {500, 1000} also led to an infeasible model for at least one instance. The remaining
combinations always found an integer feasible solution.
We report in Table 2 the results with the configuration (σ = 0.1, µ = 2000), which yields
the least average GAPOPT , between the best primal solutions and the known optima. For
each instance, we present the optimal solution value z, the percentage of variables after the
matheuristic filter (ΩF ), followed by the cost z̄ and the total GAPOPT (from the optimal value
z) of the best solution found through the matheuristic. In the next columns, we present the
partial runtime of applying our variable reduction technique (TC ) and the one by Iris et al.
(2015) (TI ), as well as the total runtime (i.e. the sum of the times for the reduction and for
solving the mathematical model using Gurobi): TCF and TIF , respectively. Lastly, we show
the runtime improvement of our proposal (TE ) compared to the one from the literature.
It can be seen from these results that the proposed methodology is able to find the known
optimal solution in 83% of instances, while the gap is below 4% for those solutions which are
not optimal. Note that the runtime efficiency of our methodology is inferior to the literature
in half of the instances with 20 vessels and in one of the medium instances. Nevertheless,
these results do not have a significant impact because the corresponding execution times are
at most 44 seconds, and the time difference between the methods does not exceed 2 seconds.
For example, while instance 2 is solved instantaneously by the technique from the literature,
it spends 1.09 seconds using the matheuristic. Therefore, our proposal looses on the average
efficiency for small instances.
On the other hand, observing the results for medium and large instances in the benchmark,
it is clear that the matheuristic times are significantly smaller than those from the exact
method presented by Iris et al. (2015). The known optimal solution is found in all instances
with 30 vessels, spending on average 59% of the time spent by the exact method. For more
difficult instances, with 40 vessels, the optimal solution is obtained in half of the cases, while
very good solutions can be achieved using about 30% of the time consumed by the baseline
method.
Considering instance 23, for example, the optimal solution is obtained 8 times faster by the

22

Table 2: Results concerning quality of solutions and runtime
Instance

Matheuristic results

Runtime
Matheuristic

|V |

20

30

40

ID

z

1

89.00

2

56.20

3

85.70

4

81.80

5

ΩF (%)

Efficiency
Iris et al. (2015)

z̄

GapOPT (%)

TC (s)

TCF (s)

TI (s)

TIF (s)

TE (%)

60.84

89.00

0.00

32.44

56.65

14.84

64.28

88.13

100.00

56.20

0.00

1.01

1.09

0.09

0.16

681.25

59.09

85.70

0.00

9.63

73.19

0.79

114.73

63.79

47.86

81.80

0.00

8.58

39.24

2.22

60.22

65.16

59.20

99.13

59.20

0.00

2.62

7.99

0.16

7.59

105.27

6

59.20

100.00

59.20

0.00

1.53

6.73

0.16

5.09

132.22

7

75.20

94.32

75.20

0.00

6.42

21.33

2.56

19.92

107.08
103.22

8

61.40

73.20

61.40

0.00

5.39

22.10

0.95

21.41

9

79.00

52.22

79.00

0.00

16.37

45.45

3.77

54.32

83.67

10

101.00

45.56

101.00

0.00

26.05

76.27

3.13

214.43

35.57

T E20

101.34

11

143.20

31.43

143.20

0.00

60.66

186.16

7.64

421.91

44.12

12

92.00

87.55

92.00

0.00

13.59

43.93

0.85

43.67

100.60

13

110.00

66.45

110.00

0.00

24.53

64.00

3.01

85.90

74.51

14

107.40

50.85

107.40

0.00

28.50

111.48

6.73

164.24

67.88

15

168.40

26.53

168.40

0.00

70.46

236.08

10.64

665.77

35.46

16

121.60

72.09

121.60

0.00

57.76

144.80

22.03

153.33

94.44

17

109.40

61.39

109.40

0.00

28.97

73.98

4.30

85.56

86.47

18

135.00

28.24

135.00

0.00

56.29

253.90

10.72

651.13

38.99

19

176.20

23.18

176.20

0.00

86.51

252.40

27.41

737.74

34.21

20

139.80

38.27

139.80

0.00

70.84

204.72

28.60

346.50

59.08

T E30

59.01
22.04

21

246.80

16.20

252.60

2.30

235.29

2035.52

20.90

9237.00

22

178.40

30.14

178.40

0.00

171.43

449.33

45.42

694.91

64.66

23

266.30

15.39

266.30

0.00

322.13

1771.94

131.24

14516.88

12.21

24

307.00

15.39

318.20

3.52

1788.03

3588.11

538.36

11071.74

32.41

25

164.60

28.63

164.60

0.00

105.97

457.75

8.21

1049.86

43.60

26

258.20

16.31

261.90

1.41

274.46

2074.55

89.55

4337.52

47.83

27

205.40

19.92

205.40

0.00

171.92

454.28

17.81

1520.09

29.89

28

294.20

16.04

301.30

2.36

518.37

2318.46

66.65

42988.26

5.39

29

227.60

19.96

229.70

0.91

680.40

2480.52

567.79

2563.04

96.78

30

210.10

18.57

210.10

0.00

223.22

1470.65

46.59

4354.89

33.77

T E40

30.14

TCF
ΩM
ΩF =
; ΩM denotes the number of variables after the matheuristic filter; TE =
; T E|V | corresponds to the geometric
Ω3
TIF
mean of TE for instances with |V | vessels.

matheuristic algorithm. In instance 28, the matheuristic consumes less than 6% of literature
algorithm runtime to find a solution within less than 3% of the optimal value. These results
suggest that classifying the variables with the combinatorial bound is an effective selection

23

criterion: the model size decreases drastically, the solution runtime reduces consistently in
instances with more challenging dimensions, while keeping solutions up to 4% of the optimum.

6

Further related work and concluding remarks
The first paragraph in Section 1 of a classic review by Balas and Padberg (1976) reads:
“Among all special structures in (pure) integer programming, there are three
which have the most wide-spread applications: set partitioning, set covering and
the traveling salesman (or minimum length Hamiltonian cycle) problem; and if we
were to rank the three, set partitioning would be a likely candidate for number
one.”

We remark that, over forty years later, the set partitioning problem is still a central structure in integer programming, as illustrated by the several interesting applications mentioned
throughout this paper. That early work of Balas and Padberg is a thorough introduction to
the concepts and problems related to set partitioning, as well as the main polyhedral results
and exact algorithms up to that date. While surveying the literature on this fundamental
problem is beyond the scope of our paper, we still mention particular works that are more
directly related to ours or particularly inspiring.
The awarded thesis by Borndörfer (1998) provides an extended review of polyhedral and
algorithmic aspects related to the underlying set packing and covering relaxations. It also
documents the components and implementation issues of a branch and cut algorithm for set
partitioning, extending in numerous directions the approach of Hoffman and Padberg (1993)
to an application in airline crew scheduling. Finally, it describes a real world application of
vehicle routing in the context of public transportation for handicapped people, building on
a decomposition of the problem in two steps, both of which require optimizing over a set
partitioning structure. In the next two paragraphs we highlight the remarkable effort of that
author in extending the results on polytopes with more substantial body of knowledge to
larger classes of problems.

24

Borndörfer and Weismantel (2001) present an affine transformation technique (aggregation) to leverage cutting planes from combinatorial relaxations of an IP formulation. Their
polyhedral investigation stems from from a generalization of projection to introduce an algorithmic approach. A so-called aggregation scheme allows one to transfer (expand) known
classes of valid inequalities in a suitable projection space (e.g. the polytope of another combinatorial structure) to the original polyhedron representing an IP. Besides constructing interesting aggregation schemes leading to set packing and knapsack relaxations, the authors
describe conditions under which the separation problem for the new classes of inequalities
(valid) can be solved in polynomial time. Several of these results are further investigated and
contrasted within the framework of disjunctive cuts by Letchford (2001).
Borndörfer (2004) also describes the combinatorial packing problem (CPP), investigating a
structure closely related to the class of set partitioning problems that we study. The problem
consists of solving a number of individual combinatorial optimization problems on a same
ground set, such that no element is contained in the solution of more than one problem. A
number of interesting problems can be subsumed as CPP examples, including minimum cost
flows, steiner trees packing, and the generalized assignment problem.
Finally, we mention a few more problems that are closely related to the GSPP structure
that we investigate here. In the work of Campello and Maculan (1987), the set partitioning problem is generalized by a single upper bound on positive linear combinations of the
variables, instead of the set packing constraints of the GSPP we study. They also consider
a different cardinality constraint, and propose a Lagrangean relaxation scheme to determine lower bounds. Another interesting Lagrangean approach worth mentioning is that of
Cavalcante et al. (2008) to set partitioning. Their sophisticated relax-and-cut algorithm improves on the quality of previous known lower bounds, while also being competitive regarding
time efficiency. We humbly believe that extending their approach to the GSPP structure we
study and comparing combinatorial and Lagrangean bounds would be a rather interesting
work. As for Fisher and Kedia (1990), the set partitioning structure is generalized by set
covering constraints. The resulting problem is also interesting, properly formulating previous
applications in the literature, and the authors describe dual heuristics to it.

25

The long tradition in studying the polyhedra associated with 0–1 matrices encompasses
the GSPP structure that we consider. In particular, Sebő (1998) extended the theory of
perfect matrices in set packing formulations, and ideal matrices in set covering, to characterize
non-integral polyhedra in the mixed packing and covering problem (assuming the coefficient
matrices satisfy those former conditions). A central structure in his work is that of an oddhole graph. Almost twenty years later, Kuo and Leung (2016) start from that same graph
structure to investigate the mixed set covering, packing and partitioning problem.
They derive the mixed odd-hole inequality, and show that its inclusion completely characterizes the polytope corresponding to the mixed problem when the coefficient matrix induces
precisely that graph. Further classes of inequalities are introduced, and preliminary computational experiments indicate its effectiveness. As we remarked earlier, the base GSPP
formulation that we study is an instance of the mixed problem of Kuo and Leung. Nevertheless, the purely combinatorial constructions that we devised may be extended to include
different problem features that cannot be modelled by their formulation. That is precisely
what allowed us to strengthen the compatibility criterion with the number of available cranes
in the port logistics application of Iris et al. (2015).

References
A. Atamtürk, G. L. Nemhauser, and M. W. Savelsbergh. Conflict graphs in solving integer
programming problems. European Journal of Operational Research, 121(1):40–55, 2000.
URL http://dx.doi.org/10.1016/S0377-2217(99)00015-6.
E. Balas and M. W. Padberg. Set partitioning: A survey. SIAM review, 18(4):710–760, 1976.
C. Bierwirth and F. Meisel. A survey of berth allocation and quay crane scheduling problems
in container terminals. European Journal of Operational Research, 202(3):615 – 627, 2010.
ISSN 0377-2217. URL http://dx.doi.org/10.1016/j.ejor.2009.05.031.
C. Bierwirth and F. Meisel. A follow-up survey of berth allocation and quay crane scheduling

26

problems in container terminals. European Journal of Operational Research, 244(3):675 –
689, 2015. ISSN 0377-2217. URL http://dx.doi.org/10.1016/j.ejor.2014.12.030.
R. Borndörfer. Aspects of set packing, partitioning, and covering. PhD thesis, Doctoral
dissertation, Ph. D. thesis, Technischen Universität Berlin, Germany, 1998.
R. Borndörfer.
pages 19–32.

Combinatorial Packing Problems, in The Sharpest Cut, chapter 3,
Society for Industrial and Applied Mathematics (SIAM), 2004.

URL

http://locus.siam.org/doi/abs/10.1137/1.9780898718805.ch3.
R. Borndörfer and R. Weismantel.

Discrete relaxations of combinatorial programs.

Discrete Applied Mathematics, 112(1–3):11 – 26, 2001.

ISSN 0166-218X.

URL

http://dx.doi.org/10.1016/S0166-218X(00)00307-3.
R. E. Campello and N. F. Maculan.

Lagrangean relaxation for a lower bound

to a set partitioning problem with side constraints:
Discrete Applied Mathematics, 18(2):119 – 136, 1987.

properties and algorithms.
ISSN 0166-218X.

URL

http://dx.doi.org/10.1016/0166-218X(87)90015-1.
V. F. Cavalcante, C. C. de Souza, and A. Lucena. A relax-and-cut algorithm for the set
partitioning problem. Computers & Operations Research, 35(6):1963 – 1981, 2008. ISSN
0305-0548. URL http://dx.doi.org/10.1016/j.cor.2006.10.009.
B. Dezső, A. Jüttner, and P. Kovács. LEMON – an Open Source C++ Graph Template
Library. Electronic Notes in Theoretical Computer Science, 264(5):23 – 45, 2011. ISSN
1571-0661.
J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965.
URL http://cms.math.ca/10.4153/CJM-1965-045-4.
L. Fanjul-Peyro and R. Ruiz. Size-reduction heuristics for the unrelated parallel machines
scheduling problem. Computers & Operations Research, 38(1):301 – 309, 2011. ISSN 03050548. URL http://dx.doi.org/10.1016/j.cor.2010.05.005. Project Management and
Scheduling.
27

M. L. Fisher and P. Kedia.
lems using dual heuristics.

Optimal solution of set covering/partitioning probManagement Science, 36(6):674–688,

1990.

URL

http://dx.doi.org/10.1287/mnsc.36.6.674.
K. L. Hoffman and M. Padberg. Solving airline crew scheduling problems by branch-and-cut.
Management Science, 39(6):657–682, 1993.
C. Iris, D. Pacino, S. Ropke, and A. Larsen. Integrated berth allocation and quay crane
assignment problem: Set partitioning models and computational results. Transportation
Research Part E: Logistics and Transportation Review, 81:75 – 97, 2015. ISSN 1366-5545.
URL http://dx.doi.org/10.1016/j.tre.2015.06.008.
Y.-H. Kuo and J. M. Leung. On the mixed set covering, packing and partitioning polytope.

Discrete Optimization, 22, Part A:162 – 182, 2016.

ISSN 1572-5286.

URL

http://dx.doi.org/10.1016/j.disopt.2016.05.004.
E. Lalla-Ruiz and S. Voß. Popmusic as a matheuristic for the berth allocation problem.
Annals of Mathematics and Artificial Intelligence, 76(1):173–189, 2016a. ISSN 1573-7470.
URL http://dx.doi.org/10.1007/s10472-014-9444-4.
E. Lalla-Ruiz and S. Voß. Modeling the parallel machine scheduling problem with step deteriorating jobs. European Journal of Operational Research, 255(1):21 – 33, 2016b. ISSN
0377-2217.
A. N. Letchford.

On disjunctive cuts for combinatorial optimization.

nal of Combinatorial Optimization, 5(3):299–315, 2001.

ISSN 1573-2886.

JourURL

http://dx.doi.org/10.1023/A:1011493126498.
V. Maniezzo, T. Stützle, and S. Voß. Matheuristics: hybridizing metaheuristics and mathematical programming, volume 10 of Annals of Information Systems. Springer US, 2010.
ISBN 978-1-4419-1305-0. URL http://dx.doi.org/10.1007/978-1-4419-1306-7.
G. R. Mauri, A. C. M. Oliveira, and L. A. N. Lorena. A hybrid column generation approach for
the berth allocation problem. In J. van Hemert and C. Cotta, editors, Proc. EvoCOP 2008,
28

Naples, Italy, volume 4972 of Lecture Notes in Computer Science, pages 110–122. Springer
Berlin Heidelberg, 2008. URL http://dx.doi.org/10.1007/978-3-540-78604-7_10.
F. Meisel and C. Bierwirth.

Heuristics for the integration of crane productiv-

ity in the berth allocation problem.

Transportation Research Part E: Logis-

tics and Transportation Review, 45(1):196 – 209, 2009.

ISSN 1366-5545.

URL

http://dx.doi.org/10.1016/j.tre.2008.03.001.
D. W. Pentico. Assignment problems: A golden anniversary survey. European Journal of
Operational Research, 176(2):774–793, 2007.
N. J. Rezanova and D. M. Ryan. The train driver recovery problem—a set partitioning based
model and solution method. Computers & Operations Research, 37(5):845 – 856, 2010.
ISSN 0305-0548.
C. C. Ribeiro and V. Maniezzo. Preface to the special issue on matheuristics: Model-based
metaheuristics. International Transactions in Operational Research, 22(1):1–1, 2015. ISSN
1475-3995. URL http://dx.doi.org/10.1111/itor.12142.
A. Sebő. Characterizing noninteger polyhedra with 0–1 constraints. In Integer Programming
and Combinatorial Optimization: 6th International IPCO Conference, volume 1412 of Lecture Notes in Computer Science, pages 37–52. Springer Berlin Heidelberg, 1998. ISBN
978-3-540-69346-8. URL http://dx.doi.org/10.1007/3-540-69346-7_4.
R.

Stahlbock

nals:

A

and
literature

S.

Voß.
update.

Operations
OR

research

Spectrum,

at

30(1):1–52,

container

termi-

2008.

URL

http://link.springer.com/article/10.1007/s00291-007-0100-9.
F. Stefanello, O. C. B. de Araújo, and F. M. Müller. Matheuristics for the capacitated pmedian problem. International Transactions in Operational Research, 22(1):149–167, 2015.
ISSN 1475-3995. URL http://dx.doi.org/10.1111/itor.12103.

29

