Dantzig-Wolfe series of decomposition and reformulation algorithm to solve MILP
This repo has been archived On Aug 11, 2019. New update will be made to edxu96/MatrixOptim, which is the aggregation of robust optimization and decomposition.
According to the PhD thesis by James Richard Tebboth A Computational Study of Dantzig-Wolfe Decomposition:
Dantzig-Wolfe decomposition is an optimisation technique for solving large scale, block structured, linear programming (LP) problems. Problems from many different fields such as production planning, refinery optimisation, and resource allocation may be formulated as LP problems. Where there is some structure arising from repeated components in the problem, such as the handling of multi-periods, multi-locations, or multi-products, the problem may potentially be solved using Dantzig-Wolfe decomposition.
Dantzig-Wolfe decomposition will not rival mainstream techniques as an optimisation method for all LP problems. But we do show that Dantzig-Wolfe decomposition has some niche areas of application: certain large scale classes of primal block angular structured problems, and in particular where the context demands rapid results using parallel optimisation, or near optimal solutions with a guaranteed quality.
LP optimisation software use two main classes of methods. The simplex method is a gradient descent method that moves along the edge of the feasible region [Chv83, Dan63]. Interior point methods (IPM) move through the interior of the feasible region [Wri97].
DW-decomp is composed of three major parts:
- Dantzig-Wolfe Reformulation
- Dantzig-Wolfe Column Generation
- Stable Column Generation
More detailed explanation can be found in edxu96/DantzigWolfeDecomposition/wiki.
- Relaxed Mixed Integer Linear Programming Problems (Reformulation)
- Input A linear programming problem with complicating constraints.
- Output The solution of the linear programming problem obtained after using the Dantzig-Wolfe decomposition algorithm.
- Bounded Mixed Integer Linear Programming (with Extreme Points)
- Unbounded Mixed Integer Linear Programming (with Extreme Rays)
It must be combined with an efficient branch-and-cut algorithm to solve a MILP.
The code is in five files, which should be stored in your working directory:
DantzigWolfeDecomposition.jl
FuncDW.jl
FuncSub.jl
FuncMas.jl
FuncStab.jl
Load other necessary packages:
using JuMP
using CPLEX
using Gurobi
using GLPKMathProgInterface
using LinearAlgebra
using MathProgBase
using SparseArrays
There is only doDWDecomp
in the module:
using DantzigWolfeDecomposition
## Set parameter and start DW-Decomposition
dualPen = 10
dualPenMult = 0.1
dualPenThreshold = 0.01 - 1e-5
epsilon = 0.00001 # [maximum difference between two bounds]
whePrint = false # [whether to print detailed info]
whiSolver = 2 # 1: Gurobi, 2: CPLEX, 3: GLPK
doDWDecomp(
mat_a, vec_b, vec_c, # Data in LP Problem
vecSenseAll, indexMas, blocks, indexSub, numXPerSub, # Data for DW-Decomp
dualPen, dualPenMult, dualPenThreshold, # Para for Stable
epsilon, whePrint, whiSolver # Control Para
)
Attention: The support for GLPK
is not very well. The Gurobi
solver does better than CPLEX
. If you don't have Gurobi
or CPLEX
, you may need to comment out the two lines in the DantzigWolfeDecomposition.jl
file.
using CPLEX
using Gurobi
In Test/test.jl
, you can see the example to use doDWDecomp
to solve Generalized Assignment Problem.
Edward J. Xu is maintaining the project.
It's originally inspired by Professor Stefan Røpke, DTU Management.
- Tebboth, J. R., 2001. A computational study of Dantzig-Wolfe decomposition. University of Buckingham.