An integer programming column generation principle for heuristic search methods

• Author: Elina Rönnberg,Yixin Zhao,Torbjörn Larsson
• Date: 01 January 2020
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12521

Intl. Trans. in Op. Res. 27 (2020) 665–695

DOI: 10.1111/itor.12521

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An integer programming column generation principle

for heuristic search methods

Yixin Zhaoa, Torbj¨

orn Larssonband Elina R¨

onnbergb

aSchool of Automation, Nanjing University of Science and Technology, China

bDepartment of Mathematics, Link¨

oping University, Sweden

E-mail: yixin.zhao@njust.edu.cn [Zhao]; torbjorn.larsson@liu.se [Larsson]; elina.ronnberg@liu.se [R¨

onnberg]

Received 15 December 2016; receivedin revised form 4 January 2018; accepted 20 January 2018

Abstract

There is an increasing interest in integrating column generation and heuristic approaches to efficiently solve

large-scale discrete optimisation problems. We contribute in this direction. Based on the insights from La-

grangian duality theory, we present an auxiliary problem that can be used for finding near-optimal solutions

to a discrete column-oriented model. The structure of this auxiliary problem makes it suitable for being

addressed with a heuristic search method involving column generation. To this end, we suggest a large

neighbourhood search strategy where the repair step is to solve a column generation type subproblem. The

suggested search strategy and mathematical models involved need to be tailored to the problemstructure. To

illustrate important design options and computational behaviour, four applications are studied: bin packing,

generalised assignment, a resource allocation problem and the fixed-charge transportation problem.

Keywords:integer programming; column generation; metaheuristics; matheuristics; large neighbourhood search

1. Introduction

Both column generation-based methods and heuristic solution strategies are successfully and fre-

quently used approaches within the field of discrete optimisation. There is an increased interest

in combining these approaches to efficiently solve large-scale discrete optimisation problems (for

an overview, see Raidl, 2015). For application-specific examples, see Filho and Lorena (2000),

Pirkwieser and Raidl (2010), Massen et al. (2012), and Parragh and Schmid (2013).

One possible way to combine linear programming column generation and a heuristic for solving

a discrete problem is of course to applyany suitable heuristic to the restricted master problem where

only a subset of variables is present. One drawback of such strategies is that, since the search space

is very limited, feasibility might be difficult to obtain (L¨

ubbecke and Desrosiers, 2005). Another

drawback is thatthe columns that are generated with the purpose of solving the linear programming

relaxation of the problem might not be suitable for being part of an integer solution.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

666 Y. Zhao et al. / Intl. Trans. in Op. Res.27 (2020) 665–695

In this paper, the focus is on strategies that include the generation of new columns as part of the

heuristic method since such strategies allow a more extensive search. In general, it is problematic

to apply a heuristic principle directly to a discrete column-oriented model since the columns are

not explicitly at hand and typically made available by solving a column generation subproblem

derived based on linear programming properties. Also, since not all columns are at hand, it is hard

to define an explicit neighbourhood with respect to the complete model. Another challenge is that a

natural component of a heuristic search is to restrict the values of certain variables and, in a column

generation context, the complication of avoiding regeneration of columns when fixing variables to

zero is well known. The corresponding issue appears also in a branch-and-price context, where

it is overcome by instead imposing bounds on variables of the compact formulation. For further

reading, see L¨

ubbecke and Desrosiers (2005).

A generic mean to extend the search beyond the columns needed for solving a liner programming

relaxation of a restricted master problem is to design a method that facilitates the generation of

more columns during the search. Examples of such methods are diving heuristics (Joncour et al.,

2010; Sadykov et al., 2015) and the method for solving set partitioning problems byBredstr ¨

om et al.

(2014), which are both used in a branch-and-price context. Another example is SearchCol (Alvelos

et al., 2010).

Diving heuristics can in short be described as a depth-first search in a branch-and-price tree,where

the nodes to visit are carefully selected. A diving heuristic graduallyobtains integer-valued variables

by fixations according to the branching, aims for profitable solutions by prioritising columns that

are part of linear programming optimal solutions in the nodes, and escapes local optima through

partial backtracking. Diving heuristics have, for example, been implemented for crew rostering

(Gamache et al., 1999), network design (Holmberg and Yuan, 2000), vehicle routing (G¨

unl¨

uk et al.,

2006), and lot-sizing (Degraeve and Jans, 2007) problems.

The method by Bredstr¨

om et al. (2014) is developed for a branch-and-price context where they

tweak the column generation processused for solving a linear programming relaxationof a restricted

master problem such that it also has high chances of finding columns that can be part of a high-

quality integer solution. This is achieved by adding a surrogate constraint to the master problemand

applying a subgradient technique to a Lagrangian dual formulation of the master problem where

they heuristically adjust the multipliers to favour columns that are needed for forming an integer

solution. The multiplier adjustment is constructed such that the method converges to a standard

subgradient method, hence ensuring convergence to solving the linear programming relaxation of

the restricted master problem.

The SearchCol strategy (Alvelos et al., 2010) is developed for problems with a Cartesian product

structure. The method iterates between column generation for a linear programming relaxation

of a restricted master problem and a metaheuristic search on the columns available. The method

does not involve the use of a branch-and-bound tree; instead the outcome of the heuristic search

is used to select a restriction to impose on the column generation subproblems in the next it-

eration. As opposed to heuristics involved in a branch-and-price search, this type of method is

by nature a combinatorial method through the use of a metaheuristic search, and the use of

linear programming column generation serves as a guide in finding profitable columns. The restric-

tions on the subproblems have the role of guiding and diversifying the search. An approach of

SearchCol type has, for example, been implemented for two- and three-stage bin packing problems

(Alvelos et al., 2014).

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies