Combining penalty‐based and Gauss–Seidel methods for solving stochastic mixed‐integer problems

• Author: B. Dandurand,J. Christiansen,A. Eberhard,F. Oliveira
• Date: 01 January 2020
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12525

Intl. Trans. in Op. Res. 27 (2020) 494–524

DOI: 10.1111/itor.12525

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Combining penalty-based and Gauss–Seidel methods

for solving stochastic mixed-integer problems

F. O l i v e i ra a, b , J. Christiansenb, B. Dandurandband A. Eberhardb

aDepartment of Mathematical Sciences, School of Science – RMIT University, Melbourne, VIC,Australia

bSystems Analysis Laboratory, Department of Mathematics and Systems Analysis, Aalto University, FI-00076 AALTO,

Finland

E-mail: fabricio.oliveira@aalto.fi [Oliveira]; s3507717@student.rmit.edu.au [Christiansen];

brian.dandurand@rmit.edu.au [Dandurand]; andy.eb@rmit.edu.au[Eberhard]

Received 27 October 2016; receivedin revised form 30 January 2018; accepted 2 February 2018

Abstract

In this paper, we propose a novel decomposition approach (named PBGS) for stochastic mixed-integer

programming (SMIP) problems, which is inspired by the combination of penalty-based Lagrangian and

block Gauss–Seidel methods. The PBGS method is developed such that the inherent decomposable structure

that SMIP problems present can be exploited in a computationally efficient manner. The performance of

the proposed method is compared with the progressive hedging (PH) method, which also can be viewed as

a Lagrangian-based method for obtaining solutions for SMIP problems. Numerical experiments performed

using instances from the literature illustratethe efficiency of the proposed method in terms of computational

performance and solution quality.

Keywords: stochastic programming; decomposition methods; Lagrangian duality; penalty-based method; Gauss–Seidel

method

1. Introduction

Inspired by the recent advances and the increased availability of parallel computation resources,

there has been a recent surge of methods that are capable of exploiting the structure of large-scale

mathematical programming problems to achieve increased efficiency.

One relevant class of problems that can benefit from this paradigm is stochastic mixed-integer

programming (SMIP) problems. The modeling framework for this class of problems is versatile as it

simultaneously allows forthe representation of integer-valued decisions and uncertainty in the input

data. However, they are frequently challenging in terms of computational tractability due to their

inherent NP-hard nature and their large scale that arises from their scenario-based representations.

Parallel computation is particularly appropriate for solving SMIP problems, since their special

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.

F. Oliveira et al. / Intl. Trans. in Op. Res.27 (2020) 494–524 495

structure (i.e., their partial separation by decision stage and by outcome scenario) makes them

easier to decompose into smaller subproblems, which may then be solved simultaneously.

The opportunities arising from approaching SMIP problems by means of decomposition has

prompted the development of severaldifferent theoretical and algorithmic approaches.For example,

the integer L-shaped method (Laporte and Louveaux, 1993) employs Benders’ decomposition

to achieve stage-wise decomposition of SMIP problems. Other algorithms employ Lagrangian

duality to achieve scenario-wise decomposition, such as the dual decomposition algorithm (Carøe

and Schultz, 1999), which uses Lagrangian dual bounds in a branch-and-bound framework, or

progressive hedging (PH; Rockafellar and Wets, 1991; Løkketangen and Woodruff, 1996; Watson

and Woodruff, 2011; Veliz et al., 2015), which applies an alternating direction type method to the

augmented Lagrangian dual problem. Recent studies and applications of these methods include

Ahmed (2013), Lubin et al. (2013), Guo et al. (2015), Angulo et al. (2016), Gade et al. (2016), and

the references therein.

All of the above methods are based on the concept of duality, and therefore they must consider

the duality gap that may exist between the optimal values of the original (primal) problem and the

dual problem. This duality gap is frequently nonzero in the context of nonconvex problems, such

as those with integer decision variables. If the duality gap for a particular problem is large, any

algorithm based on that dual is unlikely to be effective (Chen and Chen, 2010).

Several possible approaches to modifying Lagrangian duality to deal with the duality gap that

arises in nonconvex problems have been considered in the literature. These approaches include

l1-like penalty functions (Chen and Chen, 2010), indicator augmenting functions (Lalitha, 2010),

nonlinear Lagrangian functions (Yang and Huang, 2001), and semi-Lagrangian duality (Beltran

et al., 2006). With the exception of nonlinear Lagrangian functions, these approaches have not

yet been widely exploited in terms of experimental investigation and practical applications despite

numerous theoretical developments available in the literature.

In this paper, we propose an alternative approach to deal with SMIP problems that build upon

recent theoretical results from Boland and Eberhard (2015) and Feizollahi et al. (2017) showing

that duality gaps can be diminished with the use of finite-valued penalties for a specific class

of penalty functions. We show that one can obtain reasonable penalty functions using positive

bases and that parallelization can be obtained by the application of a block Gauss–Seidel (GS)

approach. The combination of these two frameworks allows us to develop an efficient heuristic that

is capable of providing solutions for large-scale SMIP problems. In terms of objective value quality

and computational time, the developed approach is shown to be competitive with the existing

approaches such as PH, which, despite its heuristic nature in the context of SMIP, has been relied

upon as an efficient solution method (see, e.g., Ryan et al., 2013; Veliz et al., 2015; Perboli et al.,

2017). Furthermore, the theoretical basis for PH does not apply for problems containing integer

variables. On the other hand, there exists some supporting theory for the penalty-based block

Gauss-Seidel (PBGS) method that we present in this paper. This partial theory has the potential to

inform directions for the further improvement of heuristic methods of this kind.

This paper is structured as follows. In Section 2, we coverthe technical background, which is used

in the development of the proposed method. Section 3 describes the development of the penalty-

based block GS method while, in Section 4, we discuss computational aspects of the algorithm.

Section 5 providesresults of our numerical experiments. Finally, in Section 6, we provideconclusions

and directions for further development of this research.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies