A general model-and-run solver for multistage robust discrete linear optimization Michael Hartisch1and Ulf Lorenz2

2025-04-30 0 0 763.58KB 50 页 10玖币

侵权投诉

A general model-and-run solver for multistage

robust discrete linear optimization

Michael Hartisch1and Ulf Lorenz2

1Network and Data Science Management, University of Siegen, Germany

2Technology Management, University of Siegen, Germany

Abstract

The necessity to deal with uncertain data is a major challenge in de-

cision making. Robust optimization emerged as one of the predominant

paradigms to produce solutions that hedge against uncertainty. In order

to obtain an even more realistic description of the underlying problem

where the decision maker can react to newly disclosed information, multi-

stage models can be used. However, due to their computational diﬃculty,

multistage problems beyond two stages have received less attention and

are often only addressed using approximation rather than optimization

schemes. Even less attention is paid to the consideration of decision-

dependent uncertainty in a multistage setting.

We explore multistage robust optimization via quantiﬁed linear pro-

grams, which are linear programs with ordered variables that are either

existentially or universally quantiﬁed. Building upon a (mostly) dis-

crete setting where the uncertain parameters—the universally quantiﬁed

variables—are only restricted by their bounds, we present an augmented

version that allows stating the discrete uncertainty set via a linear con-

straint system that also can be aﬀected by decision variables. We present

a general search-based solution approach and introduce our solver Yasol

that is able to deal with multistage robust linear discrete optimization

problems, with ﬁnal mixed-integer recourse actions and a discrete un-

certainty set, which even can be decision-dependent. In doing so, we

provide a convenient model-and-run approach, that can serve as baseline

for computational experiments in the ﬁeld of multistage robust optimiza-

tion, providing optimal solutions for problems with an arbitrary number

of decision stages.

1 Introduction

1.1 Motivation and Main Contribution

Neither for the complexity class NP nor for PSPACE polynomial-time algorithms

are known. The formal term polynomial time is usually translated to the more

intuitive meaning fast or tractable. However, if researchers were to interpret

hardness results as no-hope results and take the resulting intractability literally,

the beauty of the MIP solver world would not exist. It has become obvious that

suﬃciently many instances of various NP-complete problems can be solved by

arXiv:2210.11132v1 [math.OC] 20 Oct 2022

single solvers and have even market relevance. Thus, technological progress and

intensive research has been able to produce remarkable tools, which is why we

should not be deterred from tackling even more (theoretically) hard problems

algorithmically. The observed phenomenon is neither limited to NP-complete

problems, nor to feasibility problems, but can quite smoothly be extended to

PSPACE-complete optimization problems. From search perspective the gap be-

tween NP and PSPACE seems not necessarily larger than the gap between Pand

NP.

To underline the intuitive statement above, we present the solver Yasol,

which name—Yet another solver—is a little homage to some “Yet another ...”

unix programs and helpful apps of the 1990s. It is a tree search based solver for

multistage robust linear optimization problems and it operates on an extension

of mixed integer linear programs. The instances this solver can deal with are so

called quantiﬁed integer linear programs (abbr. QIP) where continuous variables

are permitted in the ﬁnal decision stage, and even with an extension where

interrelations between decision variables and the uncertainty set occur (abbr.

QIP+). They can be introduced from diﬀerent perspectives: On the one hand,

QIP are extended mixed integer linear programs (MIP) where the variables are

ordered explicitly and each variable is assigned a quantiﬁer (∃or ∀), adding a

multistage robust perspective to MIP. On the other hand, QIP can be viewed

as an extension of quantiﬁed boolean formula (QBF), with additional objective

function and further allowing general integer (and some continuous) variables

and arbitrary linear constraints, rather than binary variables and clauses, adding

the optimization perspective to a generalized QBF. Additionally, QIP can be

viewed as a mathematical game between an existential and a universal player

that—while having to obey a set of (linear) rules—try to maximize and minimize

the same objective function, respectively. In the context of robust optimization

QIP and its extensions provide a convenient framework for multistage robust

optimization problems with discrete polyhedral and even decision-dependent

uncertainty set.

Tackling QIP and QIP+ instances algorithmically has thrived on the pio-

neering work of the MIP, QBF and game tree search community: Optimality

proofs and several ideas for ﬁnding solutions can be adapted from MIP and

QBF solving, while relying on heuristic and algorithmic game tree search con-

cepts. In this paper we describe how we can adapt the theoretical, heuristic

and algorithmic ﬁndings and approaches from these various research ﬁelds and

we present QIP and QIP+ speciﬁc results, which are then merged together to

obtain an easily accessible model-and-run solver for a large variety of multistage

robust optimization problems. Along this path, the contributions of this paper

are as follows:

•We provide an in depth introduction and analysis of QIP and focus on

the augmented version QIP+ that allows modeling of multistage robust

optimization problems with decision-dependent uncertainty.

•We introduce our solver Yasol that is able to deal with multistage robust

linear discrete optimization problems, with mixed-integer recourse actions

only in the ﬁnal decision stage and discrete uncertainty, which even can

be decision-dependent.

•We present a general search based approach for such problems, which

stands in contrast to the commonly used reformulation, decomposition

and approximation techniques used in multistage optimization.

•We discuss enhanced solution techniques and give insight into specialized

heuristics.

•Using the example of the multilevel critical node problem [BCLT21] we

showcase that quantiﬁed programming provides a convenient and straight-

forward modeling framework and we demonstrate that our model-and-run

solver serves as suitable baseline for multistage robust optimization prob-

lems.

After considering the related literature we introduce the concept of quantiﬁed

programming and present an augmented version allowing decision-dependent

uncertainty in Section 2. In Section 3 we introduce our solver and explain the

underlying solution process. Further techniques integrated into the solution

process are discussed in Section 4. Before we conclude, we show how quantiﬁed

programs can be used to model the multilevel critical node problem [BCLT21]

in Section 5 and demonstrate the performance of our solver on these instances

in Section 6.

1.2 Related Work

Quantiﬁed Programming Quantiﬁed constraint satisfaction problems have

been studied since at least 1995 [GPS95]. In 2003, Subramani revived the idea

of universal variables in constraint satisfaction problems and coined the term

Quantiﬁed Linear Program (QLP) [Sub03]. His QLP did not have an objective

function and the universal variables could only take values in their associated

intervals. In the following year he extended this approach by integer variables

and called them Quantiﬁed Integer Programs (QIPs) [Sub04]. Later Wolf and

Lorenz added a linear objective function [LW15] and enhanced the problem

to: “Does a solution exist and if yes which one is the best.” In [HELW16] the

extension of QIP allowing a second constraint system restraining the universally

quantiﬁed variables to a polytope was introduced. This was further extended to

allow decision-dependent uncertainty sets in [HL19]. In both papers, polynomial

time reductions are presented, linking the extensions closely to the originating

QIP. In a computational study the strength of using QIP for robust discrete

optimization problems was illustrated [GH21], being able to optimally solve

problems with up to nine stages.

As we deal with a (mainly) discrete domain, there is a tight connection to the

quantiﬁed boolean formula problem (QBF), which can be interpreted as a multi-

stage robust satisﬁability problem with only binary variables which are restricted

via logical clauses. In particular as our solver uses an internal binary represen-

tation of discrete variables, many techniques known from solving QBF can be

adapted to help during the search process. Within the last few years several

new techniques for solving QBF were developed and enhanced, such as clause

selection [JMS15b], clause elimination [HJL+15], quantiﬁed blocked clause elim-

ination [LBB+15], counter example guide abstraction reﬁnement [JKMSC16],

dependency learning [PSS19a], long-distance Q-resolution [PSS19b] as well as

several preprocessing [WRMB17, LE19] and even machine learning techniques

[Jan18, LRSL19]. With the recent surge of new research a number of general

solvers evolved and emerged [RT15, LE17, Ten19] within a vivid competitive

environment [PS19, LSvG16]. It is noteworthy that also research on speciﬁc

optimization settings within the QBF framework was conducted [IJMS16].

Multistage Robust Optimization The notion of quantiﬁed variables, ask-

ing for a strategy that hedges against all possible realizations of universally

quantiﬁed variables is closely linked to robust optimization problems. In [GH21]

it was shown how quantiﬁed programming is directly linked to multistage ro-

bust optimization. Robust optimization problems are mathematical optimiza-

tion problems with uncertain data, where a solution is sought that is immune

to all realizations of the uncertain data within the anticipated uncertainty set

[BTN02, GMT14]. A compact overview of prevailing uncertainty sets and ro-

bustness concepts can be found in [GYdH15, GS16]. By allowing wait-and-see

variables, instead of demanding a single static solution, several robust two-

and multi-stage approaches arose in recent years [BTGGN04, LLMS09, DI15,

YGdH19], whereat the vast majority of research is restricted to a two-stage

setting.

Besides directly tackling the robust counterpart, which is also referred to

as deterministic equivalent program (DEP) [Wet74] or full expansion [JMS15a]

in related areas, several other solution approaches for multistage problems ex-

ist. Dynamic programming techniques can be used [Sha11], but often suﬀer

from the curse of dimensionality. Other solution methods include variations of

Bender’s decomposition [TTE09] and Fourier–Motzkin elimination [ZDHS18].

Additionally, iterative splitting of the uncertainty set is used to solve robust

multistage problems in [PdH16] and a partition-and-bound algorithm is pre-

sented in [BD16]. By considering speciﬁc robust counterparts a solution can

be approximated and sometimes even guaranteed [BTGGN04, BTGS09, CZ09].

Furthermore, several approximation schemes based on (aﬃne) decision rules can

be found in the literature (e.g. [BIP10, KWG11, BG15, GKW19]).

In robust optimization it is frequently assumed that the occurring uncer-

tainty is embedded in a predetermined uncertainty set, i.e. it is assumed to be

exogenous. We use the term decision-dependent uncertainty for problems in

which realizations of uncertain variables can be manipulated by decisions made

by the planner. Others use the term endogenous uncertainty (e.g. [LG18, ZF20])

or terms like variable uncertainty (e.g. [P.14]) or adjustable uncertainty set

[ZKG+17]. We refer to [Har20] for a more exhaustive discussion.

In the general context of optimization under uncertainty several solvers,

modeling tools and software packages for robust optimization [GS11, Dun16,

WM21] even with endogenous uncertainty [VJE20] as well as stochastic and dis-

tributionally robust optimization [CSX20] have been developed. Furthermore,

for the special case of combinatorial three-stage fortiﬁcation games a general

exact solution framework was presented in [LLM+21]. The other mentioned

solvers for robust optimization problems that can also cope with multistage set-

tings, however, rely on approximation schemes—in particular decision rules—for

adjustable variables and therefore cannot—in general—guarantee the optimal-

ity of the proposed solution. To the best of our knowledge, there exists no

general solver that is able to solve problems within a multistage robust dis-

crete linear optimization setting—let alone a setting with decision-dependent

uncertainty—to optimality.

2 Problem Deﬁnition

This section deals with the mathematical object of interest. First we present

the so called quantiﬁed linear program with minimax objective [LW15] and

with integer variables, which builds the bridge to well known mathematical pro-

gramming. This is structured in so called stages and is called QIP, where we

additionally allow continuous variables in the last decision stage. The second

problem statement, which we call QIP+, generalizes and extends the QIP prob-

lem, allowing decision-dependent and polyhedral uncertainty in the multistage

discrete setting.

Throughout the paper we use the notation [n] = {1, . . . , n}to denote index

sets. Furthermore, vectors are always written in bold font and the transpose

sign for the scalar product between vectors is dropped for ease of notation.

2.1 The problem QIP

The main component of a QIP is a linear constraint system1A∃x

x≤b

b∃. Each

variable is either existentially or universally quantiﬁed. An example may be

∃x1∈ {0,1} ∀x2∈ {0,1} ∃x3∈[−2,2] : 





−10 −4 2

−10 4 −2

10 4 1

10 −4−1







·



x3

≤











and the question to this instance is: ”Is there an x1such that for all x2there

is an x3such that all constraints hold?”. Of course, the variables must have

well-deﬁned domains, and there may be sequences of variables of the same kind.

Such a sequence of variables of one kind, either existential or universal variables,

belong to the same so called variable block.A major restriction in this paper is

that continuous variables may only occur in a ﬁnal existential variable block. All

other variables have to be integer with ﬁnite upper and lower bounds. Diﬀerent

than in conventional MIP, the quantiﬁer alternations enforce a variable order

that has to be considered.

Moreover, it is possible to incorporate an objective function. However, this

objective has a minimax character, i.e. if an optimizer strives at large objective

values, he has to consider a universal ’player’ minimizing over her domain. For

our example it may look as follows:

max

x1∈{0,1}x1+ min

x2∈{0,1}+x2+ max

x3∈[−2,2] −x3

Following the example above, a solution is no longer a vector of length three,

but it is a tree of depth three that describes how to act and react with x1and

x3, depending on possible assignments of x2. Such a tree-like solution is called

astrategy. One possible solution strategy with minimax value 1 is x1= 0,

then—depending on the opponent’s move—either x2= 0 and x3=−2 resulting

in objective value 2, or x2= 1 and x3= 0 with objective value 1, as depicted in

strategy 1 in Figure 1. The minimax-value 1 of this strategy is deﬁned via the

1The meaning of the superscript ∃quantiﬁer will become clear later. For the moment, it

is only a label.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Ageneralmodel-and-runsolverformultistagerobustdiscretelinearoptimizationMichaelHartisch1andUlfLorenz21NetworkandDataScienceManagement,UniversityofSiegen,Germany2TechnologyManagement,UniversityofSiegen,GermanyAbstractThenecessitytodealwithuncertaindataisamajorchallengeinde-cisionmaking.Robustoptimiza...

展开>> 收起<<

A general model-and-run solver for multistage robust discrete linear optimization Michael Hartisch1and Ulf Lorenz2.pdf

共50页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A general model-and-run solver for multistage robust discrete linear optimization Michael Hartisch1and Ulf Lorenz2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: