Machine Learning for K-adaptability in Two-stage Robust Optimization

2025-05-02 0 0 8.7MB 35 页 10玖币

侵权投诉

MACHINE LEARNING FOR K-ADAPTABILITY

IN TWO-STAGE ROBUST OPTIMIZATION

Esther Julien

TU Delft

e.a.t.julien@tudelft.nl

Krzysztof Postek

Independent

Researcher

¸S. ˙

Ilker Birbil

University of Amsterdam

s.i.birbil@uva.nl

October 16, 2024

ABSTRACT

Two-stage robust optimization problems constitute one of the hardest optimization problem classes.

One of the solution approaches to this class of problems is

-adaptability. This approach simultane-

ously seeks the best partitioning of the uncertainty set of scenarios into

subsets, and optimizes

decisions corresponding to each of these subsets. In general case, it is solved using the

-adaptability

branch-and-bound algorithm, which requires exploration of exponentially-growing solution trees. To

accelerate ﬁnding high-quality solutions in such trees, we propose a machine learning-based node

selection strategy. In particular, we construct a feature engineering scheme based on general two-stage

robust optimization insights that allows us to train our machine learning tool on a database of resolved

B&B trees, and to apply it as-is to problems of different sizes and/or types. We experimentally show

that using our learned node selection strategy outperforms a vanilla, random node selection strategy

when tested on problems of the same type as the training problems, also in case the

-value or the

problem size differs from the training ones.

Keywords node selection; clustering; two-stage robust optimization; K-adaptability; machine learning; tree search

1 Introduction

Many optimization problems are affected by data uncertainty caused by errors in the forecast, implementation, or

measurement. Robust optimization (RO) is one of the key paradigms to solve such problems, where the goal is to ﬁnd

an optimal solution among the ones that remain feasible for all data realizations within an uncertainty set [Ben-Tal

et al., 2009]. This set includes all reasonable data outcomes.

A speciﬁc class of RO problems comprises two-stage robust optimization (2SRO) problems in which some decisions

are implemented before the uncertain data is known (here-and-now decisions), and other decisions are implemented

after the data is revealed (wait-and-see decisions). Such a problem can be formulated as

min

x∈X max

z∈Z min

y∈Y c(z)⊺x+d(z)⊺y:T(z)x+W(z)y≤h(z),∀z∈ Z,(1)

where

x∈ X ⊆ RNx

and

y∈ Y ⊆ RNy

are the here-and-now and wait-and-see decisions, respectively, and

the vector of initially unknown data belonging to the uncertainty set

Z ⊆ RNz

. Solving problem

(1)

is difﬁcult in

general, since

might include an inﬁnite number of scenarios, and hence different values of

might be optimal for

different realizations of

. In fact, ﬁnding optimal

is an NP-hard problem [Guslitzer, 2002]. To address this difﬁculty,

several approaches have been proposed. The ﬁrst one is to use so-called decision rules which explicitly formulate the

second-stage decision

as a function of

, and hence the function parameters become ﬁrst-stage decisions next to

;

see Ben-Tal et al. [2004]. Another approach is to partition

into subsets and to assign a separate copy of

to each

of the subsets. The partitioning is then iteratively reﬁned, and the decisions become increasingly customized to the

outcomes of z.

arXiv:2210.11152v3 [math.OC] 15 Oct 2024

Machine Learning for K-adaptability

In this paper, we consider a third approach to

(1)

known as

-adaptability. There, at most

possible wait-and-see

decisions

y1,...,yK

are allowed to be constructed, and the decision maker must select one of those. The values of the

possible yk’s become the ﬁrst-stage variables, and the problem boils down to

min

x∈X ,y∈YKmax

z∈Z min

k∈K c(z)⊺x+d(z)⊺yk:T(z)x+W(z)yk≤h(z),(2)

where

K={1, . . . , K}

and

YK=×K

k=1 Y

. Although the solution space of

(2)

is ﬁnite-dimensional, it remains an

NP-hard problem. For certain cases,

(2)

can be equivalently rewritten as a mixed integer linear programming (MILP)

model [Hanasusanto et al., 2015].

The above formulation requires that for given

x∈ X

and

z∈ Z

, there is at least one decision

k∈ K

satisfying

T(z)x+W(z)yk≤h(z)

, and among those one (or more) minimizing the objective. Looking at

(2)

from the point

of view

, we can say that for each

, we can identify a subset

for which a given

is optimal among

selected recourses. The union of sets

k∈ K

is equal to

although they need not be mutually disjoint (but a

mutually disjoint partition of

can be constructed). Consequently, solving

(2)

involves implicitly (i) clustering

and (ii) optimizing the per-cluster decision so that the objective function corresponding to the most difﬁcult cluster is

minimized. Such simultaneous clustering and per-cluster optimization also occur, for example in retail. A line of

products is to be designed to attract the largest possible group of customers. The customers are clustered into

groups,

and the nature of the products is guided by the cluster characteristics.

In this manuscript, we focus on the general MILP

-adaptability case for which the only existing solution approach

is the

-adaptability branch-and-bound (

-B&B) algorithm of Subramanyam et al. [2020]. Other methods to solve

the

-adaptability problem have been proposed by Hanasusanto et al. [2015] that deals with binary decisions, and

Ghahtarani et al. [2023] that assumes integer ﬁrst-stage decisions. The

-B&B algorithm, as opposed to the top-down

partitioning of

of Bertsimas and Dunning [2016] or Postek and den Hertog [2016], proceeds by gradually building

up discrete subsets

of scenarios. In most practical cases, a solution to

(2)

, where

y1,...,yK

are feasible for large

Z1,..., ¯

, is also feasible to the original problem. The problem, however, lies in knowing which scenarios should be

grouped together. In other words, a decision needs to be made on which scenarios of

should be responded to with the

same decision. How well this question is answered, determines the (sub)optimality of

y1,...,yK

. In Subramanyam

et al. [2020], a search tree is used to determine the best collection (see Section 2 for details). However, this approach

suffers from exponential growth.

We introduce a method for learning the best strategy to explore this tree. In particular, we learn which nodes to evaluate

next in depth-ﬁrst search dives to obtain good solutions faster. These predictions are made using a supervised machine

learning (ML) model. As the input does not range for different instance sizes, or values of

, as will be explained

in future sections, the ML model does not require difﬁcult architectures. Standard ML models, such as feed-forward

neural networks, random forests, or support vector machines can be used for this work.

Due to the supervised nature, some oracle is required to be imitated. In the design of this oracle, we are partly inspired

by Monte Carlo tree search (MCTS) [Browne et al., 2012], which is often used for exploring large trees. Namely, the

training data is obtained by exploring

-B&B trees via an adaptation of MCTS (see Section 3.4). The scores given to

the nodes in the MCTS-like exploration are stored and used as labels in our training data.

In the ﬁeld of solving MILPs, learning node selection to speed up exploring the B&B tree has been done, e.g., by He

et al. [2014]. Here, a node selection policy is designed by imitating an oracle. This oracle is constructed using the

optimal solutions of various MILP data sets. More recently, Khalil et al. [2022a] used a graph neural network to learn

node selection. Our method distinguishes itself from these approaches as we speciﬁcally use the nature of our problem.

Namely, in the design of the node selection strategy, we use the actual meaning of selecting a node; adding a scenario to

a subset. Therefore, we try to learn what characteristics (or features) scenarios that should belong to the same subset

have.

For an overview on ML for learning branching policies in B&B, see Bengio et al. [2020]. There has also been done a

vast amount of research on applying MCTS directly to solving combinatorial problems. In Sabharwal et al. [2012]

a special case of MCTS called Upper Conﬁdence bounds for Trees (UCT), is used for designing a node selection

strategy to explore B&B trees (for MIPs). In Khalil et al. [2022b] MCTS is used to ﬁnd the best backdoor (i.e., a

subset of variables used for branching) for solving MIPs. Loth et al. [2013] have used MCTS for enhancing constraint

programming solvers, which naturally use a search tree for solving combinatorial problems. For an elaborate overview

on modiﬁcations and applications of MCTS, we refer to ´

Swiechowski et al. [2022].

The remainder of the paper is structured as follows. In Section 2 we describe the inner workings of the

-adaptability

branch-and-bound to set the stage for our contribution. In Section 3 we outline our ML methodology along with the

data generation procedure. Section 4 discusses the results of a numerical study, and Section 5 concludes with some

remarks on future works.

Machine Learning for K-adaptability

2 Preliminaries

It is instructive to conceptualize a solution to

(2)

as a solution to a nested clustering and optimization-for-clusters

methodology. As already mentioned in Section 1, a feasible solution to

(2)

can be used to construct a partition of the

uncertainty set into subsets

Z1,...,ZK

such that

k=1 Zk=Z

. Here, decision

is applied in the second stage if

z∈ Zk. The decision framework associated with a given solution is illustrated in Figure 1.

Figure 1: A framework of the

-adaptability problem, where we split the uncertainty set (red box) in

K= 2

parts. Here,

represents the ﬁrst-stage decisions, and y1with y2those of the second-stage.

For such a ﬁxed partition the corresponding optimization problem becomes

min

x∈X ,y∈YKmax

k∈K max

z∈Zkc(z)⊺x+d(z)⊺yk(3)

s.t. T(z)x+W(z)yk≤h(z).

The optimal solution to

(2)

also corresponds to an optimal partitioning of

, and the optimal decisions of

(3)

with that

partitioning. Finding an optimal partition and the corresponding decisions has been shown to be NP-hard by Bertsimas

and Caramanis [2010]. For that reason, Subramanyam et al. [2020] have proposed the

-B&B algorithm. There, the

idea is to gradually build up a collection of ﬁnite subsets

Z1,..., ¯

, such that for each

k∈ K

an optimal solution to

(3) with Zk=¯

Zkis also an optimal solution to (2).

The algorithm follows a master-subproblem approach. The master problem solves

(2)

with

ﬁnite subsets of scenarios.

The subproblem ﬁnds the scenario for which the current master solution is not robust. The number

of possible

assignments of this new scenario to one of the existing subsets gives rise to using a search tree. Each tree node

corresponds to a partition of all scenarios found so far into

subsets. The goal is to ﬁnd the node with the best partition.

An illustration of the search tree is given in Figure 2. The tree grows exponentially and thus only (very) small-scale

problems can be solved in reasonable time. The method we propose in the next section learns a good node selection

strategy with the goal of converging to the optimal solution much faster than K-B&B.

Figure 2: Search tree for K-adaptability branch-and-bound (K= 2).

Machine Learning for K-adaptability

Master problem.This problem solves the

-adaptability problem

(2)

with respect to the currently found scenarios

grouped into ¯

Zk⊂ Z for all k∈ K. For a collection ¯

Z1,..., ¯

ZK, the problem formulation is deﬁned as follows:

min

θ∈R,x∈X ,y∈YKθ(4)

s.t. c(z)⊺x+d(z)⊺yk≤θ, ∀z∈¯

Zk,∀k∈ K,

T(z)x+W(z)yk≤h(z),∀z∈¯

Zk,∀k∈ K,

where

is the current estimate of the objective function value. We denote the optimal solution of

(4)

by the triplet

(θ∗,x∗,y∗).

Subproblem.The subproblem aims to ﬁnd a scenario

for which the current master solution is infeasible. That is, a

scenario is found such that for each k, at least one of the following is true:

• the current estimate of θ∗is too low, i.e.,c(z)⊺x∗+d(z)⊺y∗

k> θ∗;

• at least one of the original constraints is violated, i.e.,T(z)x∗+W(z)y∗

k>h(z).

If no such scenario exists, we deﬁne the solution

(θ∗,x∗,y∗)

as a robust solution. When such a scenario

z∗

does exist,

the solution is not robust and the newly-found scenario is assigned to one of the sets ¯

Z1,..., ¯

ZK.

Deﬁnition 1. A solution (θ∗,x∗,y∗

1,...,y∗

K)to (4) is robust if

∀z∈ Z,∃k∈ K :T(z)x∗+W(z)y∗

k≤h(z),c(z)⊺x∗+d(z)⊺y∗

k≤θ∗.

Example 1. Consider the following master problem

min

θ,x,y

s.t. θ∈R,x∈ {0,1}2,y∈ {0,1}2,

z⊺x+ [2z1,2z2]yk≤θ, ∀z∈¯

Zk,∀k∈ K,

yk≥1−z,∀z∈¯

Zk,∀k∈ K,

x+yk≥1,∀k∈ K,

where

z∈ {−1,0,1}2

and

K={1,2}

. We look at three solutions for different groupings of

z1= [1,1]⊺

z2= [0,1]⊺

and

z3= [0,0]⊺

. One of them is not robust, and the other ones are but have a different objective value due to

the partition. The ﬁrst partition we consider is

Z1={z1},¯

Z2={z2}

. The corresponding solution is

θ∗= 2

x∗= [1,1]⊺

y∗

1= [0,0]⊺

, and

y∗

2= [1,0]⊺

. This solution is not robust, since for

z3= [0,0]⊺

the following constraint

is violated for all k∈ K:

y1≱1−z3⇐⇒ 0

0≱1

1−0

0,y2≱1−z3⇐⇒ 1

0≱1

1−0

0.

Next, consider

Z1={z1,z2},¯

Z2={z3}

, with solution

θ∗= 3

x∗= [0,1]⊺

y∗

1= [1,0]⊺

y∗

2= [1,1]⊺

. There is no

that violates this solution, which makes it robust. The third partition is

Z1={z1,z3},¯

Z2={z2}

, with solution

θ∗= 4

x∗= [0,0]⊺

y∗

1= [1,1]⊺

, and

y∗

2= [1,1]⊺

. This solution is also robust. Their objective values are 3 and 4,

which shows that different partitions can signiﬁcantly inﬂuence solution quality.

Mathematically, we formulate the subproblem using the big-Mreformulation:

max

ζ,z,γ ζ(5)

s.t. ζ∈R,z∈ Z, γkl ∈ {0,1},(k, l)∈ K × L,

l∈L

γkl = 1,∀k∈ K,

ζ+M(γk0−1) ≤c(z)⊺x∗+d(z)⊺y∗

k−θ∗,∀k∈ K,

ζ+M(γkl −1) ≤tl(z)⊺x∗+wl(z)⊺y∗

k−hl(z),∀l∈ L,∀k∈ K,

where

is some big scalar and

is the index set of constraints. When

ζ≤0

, we have not found any violating scenario,

and the master solution is robust. Otherwise, the found

z∗

is added to one of

Z1,..., ¯

. Then, the master problem is

re-solved, so that a new solution (θ∗,x∗,y∗), which is guaranteed to be feasible for z∗as well, is found.

Machine Learning for K-adaptability

Throughout the process, the key issue is to which of

Z1,..., ¯

to assign

z∗

. As this cannot be determined in

advance, all options have to be considered. Figure 2 illustrates that from each tree node we create

child nodes, each

corresponding to adding z∗to the k-th subset:

τk={¯

Z1,..., ¯

Zk∪ {z∗},..., ¯

ZK},∀k∈ K,

where

τk

is the partition corresponding to the

-th child node of node

. If a node is found such that

θ∗

is greater than

or equal to the value of another robust solution, then this branch can be pruned as the objective value of the master

problem cannot improve if more scenarios are added.

The pseudocode of

-B&B is given in Algorithm 2 in the Appendix. The tree becomes very deep for 2SRO problems

where many scenarios are needed for a robust solution. Moreover, the tree becomes wider when

increases. Due

to these issues, solving the problem to optimality becomes computationally intractable in general. Our goal is to

investigate if ML can be used to make informed decisions regarding the assignment of newly found

z∗

to the discrete

subsets, so that a smaller search tree has to be explored in a shorter time before a high-quality robust solution is found.

3 ML methodology

We propose a method that enhances the node selection strategy of the K-B&B algorithm. It relies on four steps:

1. Decision on what and how we want to predict: Section 3.1.

2. Feature engineering: Section 3.2.

3. Label construction: Section 3.3.

4. Using partial K-B&B trees for training data generation: Section 3.4.

All these steps are combined into the K-B&B-NODESELECTION algorithm (Section 3.5).

3.1 Learning setup

As there is no clearly well-performing node selection strategy for

-B&B, we cannot simply try to imitate one. Instead,

we investigate what choices a good strategy would make. We will focus on learning how to make informed decisions

about the order of inspecting the children of a given node. The scope of our approach is illustrated with rounded-square

boxes in Figure 3.

Figure 3: The scope of node selection

To rank the child nodes in the order they ideally be explored, one of the ways is to have a certain form of child node

information whether selecting this node is good or bad. In other words, how likely is a node to guide us towards a

high-quality robust solution fast. Indeed, this shall be exactly the quantity that we predict with our model. To train such

a model, we will construct a dataset consisting of the following input-output pairs:

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

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

10 玖币 0人已下载

立即下载

摘要：

MACHINELEARNINGFORK-ADAPTABILITYINTWO-STAGEROBUSTOPTIMIZATIONEstherJulienTUDelfte.a.t.julien@tudelft.nlKrzysztofPostekIndependentResearcher¸S.˙IlkerBirbilUniversityofAmsterdams.i.birbil@uva.nlOctober16,2024ABSTRACTTwo-stagerobustoptimizationproblemsconstituteoneofthehardestoptimizationproblemclasses...

展开>> 收起<<

Machine Learning for K-adaptability in Two-stage Robust Optimization.pdf

共35页,预览5页

还剩页未读，继续阅读

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

Machine Learning for K-adaptability in Two-stage Robust Optimization

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: