An exact approach for aggregated formulations

Publication: Research - peer-reviewConference abstract for conference – Annual report year: 2012

Standard

An exact approach for aggregated formulations. / Gamst, Mette; Spoorendonk, Simon.

2012. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.

Publication: Research - peer-reviewConference abstract for conference – Annual report year: 2012

Harvard

Gamst, M & Spoorendonk, S 2012, 'An exact approach for aggregated formulations' 21st International Symposium on Mathematical Programming, Berlin, Germany, 19/08/12 - 24/08/12,

APA

Gamst, M., & Spoorendonk, S. (2012). An exact approach for aggregated formulations. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.

CBE

Gamst M, Spoorendonk S. 2012. An exact approach for aggregated formulations. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.

MLA

Vancouver

Gamst M, Spoorendonk S. An exact approach for aggregated formulations. 2012. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.

Author

Gamst, Mette; Spoorendonk, Simon / An exact approach for aggregated formulations.

2012. Abstract from 21st International Symposium on Mathematical Programming, Berlin, Germany.

Publication: Research - peer-reviewConference abstract for conference – Annual report year: 2012

Bibtex

@misc{ae8aee2bff3f401aa7fb398b6d6c3fde,
title = "An exact approach for aggregated formulations",
author = "Mette Gamst and Simon Spoorendonk",
year = "2012",
type = "ConferencePaper <importModel: ConferenceImportModel>",

}

RIS

TY - ABST

T1 - An exact approach for aggregated formulations

A1 - Gamst,Mette

A1 - Spoorendonk,Simon

AU - Gamst,Mette

AU - Spoorendonk,Simon

PY - 2012

Y1 - 2012

N2 - Aggregating formulations is a powerful trick for transforming problems into taking more tractable forms. An example is Dantzig-Wolfe decomposition, which shows superior performance across many applications especially when part of a branch-and-price algorithm. Variable aggregation, however, may lead to mathematical formulations with a different solution space than that for the original formulation, i.e., the aggregated formulation may be a relaxation of the original problem. In a branch-and-bound context, variable aggregation can also lead to a formulation where branching is not trivial, for example when optimality cannot be guaranteed by branching on the aggregated variables. In this presentation, we propose a general method for solving aggregated formulations, such that the solution is optimal to the original problem. The method is based on applying Benders’ decomposition on a combination of the original and aggregated formulations. Put in a branch-and-bound context, branching can be performed on the original variables to ensure optimality. We show how to apply the method on well-known optimization problems.

AB - Aggregating formulations is a powerful trick for transforming problems into taking more tractable forms. An example is Dantzig-Wolfe decomposition, which shows superior performance across many applications especially when part of a branch-and-price algorithm. Variable aggregation, however, may lead to mathematical formulations with a different solution space than that for the original formulation, i.e., the aggregated formulation may be a relaxation of the original problem. In a branch-and-bound context, variable aggregation can also lead to a formulation where branching is not trivial, for example when optimality cannot be guaranteed by branching on the aggregated variables. In this presentation, we propose a general method for solving aggregated formulations, such that the solution is optimal to the original problem. The method is based on applying Benders’ decomposition on a combination of the original and aggregated formulations. Put in a branch-and-bound context, branching can be performed on the original variables to ensure optimality. We show how to apply the method on well-known optimization problems.

ER -