Scribd
Upload
29 views8 pages

ISYE6669 LP 10 21 1 - AndySun - FW

The document discusses exploiting special structures in large-scale optimization problems, specifically describing a central company model made up of multiple subsidiary units with both local and coupling constraints that can be written in a block angular structure, and how decomposition methods can eliminate the complicating coupling constraint to allow solving smaller distributed subproblems and then coordinating the results. The key learning objectives are about identifying special structures in large-scale optimization problems and designing new decomposition algorithms.

Uploaded by

nicholaszyli
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views8 pages

ISYE6669 LP 10 21 1 - AndySun - FW

The document discusses exploiting special structures in large-scale optimization problems, specifically describing a central company model made up of multiple subsidiary units with both local and coupling constraints that can be written in a block angular structure, and how decomposition methods can eliminate the complicating coupling constraint to allow solving smaller distributed subproblems and then coordinating the results. The key learning objectives are about identifying special structures in large-scale optimization problems and designing new decomposition algorithms.

Uploaded by

nicholaszyli
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Deterministic

Optimization
Large-Scale Optimization
Dantzig-Wolfe
Decomposition
Andy Sun
Assistant Professor
Stewart School of Industrial and Systems Engineering

Exploiting Special Structures of


Large-Scale Optimization
Large-Scale Optimization
Dantzig-Wolfe
Learning Objectives for this module
• Discover special structures of large-
scale optimization problems

• Design a new decomposition


algorithm that exploits special
structures of the optimization
problem
Central Company & Sub-Units
• Consider a large company that comprises 𝑛 subsidiary units.
• Each subsidiary unit 𝑖 has its own objective of their profit by planning
its own production subject to its own constraints
• Decision: 𝑥$ (e.g. how much to produce, store, sell, …)
• Local constraints: 𝐴$ 𝑥$ = 𝑏$ , 𝑥$ ≥ 0 (e.g. satisfy demand, etc)
• All units share a common resource and there is a budget on the
common resource (e.g. total monetary budget, total machine time, etc)
• The company want to maximize the total profit (sum of the sub-units’
profits), respecting their local constraints, and the total budget
constraint
Overall Problem
• The situation can be modeled as the following graph

Company
max 𝑐./ 𝑥. + ⋯ + 𝑐2/ 𝑥2

𝑇. 𝑥. + 𝑇3 𝑥3 + ⋯ + 𝑇2 𝑥2 = 𝑏5

Unit 1 Unit 1 Unit 𝑛


𝐴. 𝑥. = 𝑏. 𝐴3 𝑥3 = 𝑏3 𝐴2 𝑥2 = 𝑏2
𝑥. ≥ 0 𝑥3 ≥ 0 𝑥2 ≥ 0
Special Structure of Constraints
• The constraints can be written in a block matrix form:

• This structure is called the block angular structure


• This can be a large-scale optimization problem with big 𝑛
Exploiting Special Structure
• The constraint 𝑇. 𝑥. + 𝑇3 𝑥3 + ⋯ + 𝑇2 𝑥2 = 𝑏5 is called a coupling
constraint
• Because it couples all the sub-units together
• Such a constraint is also called a complicating constraint

• If we do not have the coupling constraint, then all sub-unit


constraints are separated

• If we can get rid off the complicating constraint, then the whole
problem become decoupled into 𝑛 separated, smaller problems
Distributed Optimization &
Coordination
• An important algorithmic idea is Coordination & Distributed
Optimization
• Somehow get rid off the coupling constraint

• Let each sub-unit solve its own problem in a distributed fashion

• Coordinate sub-units’ decisions so that the coupling constraint is


accounted for
Summary

• We learned:
– An important structure in large-scale
optimization: Block angular structure
– An outline of the coordinate & distributed
optimization algorithm

You might also like