3110https://www.ibm.com/developerworks/community/forums/atom/replies?topicUuid=77777777-0000-0000-0000-000014973273auxiliary continuous variable in Master Problem in example ilobendersatsp Replies2013-04-06T00:28:26.389ZIBM Connections - Discussion Forumurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014974338Re: auxiliary continuous variable in Master Problem in example ilobendersatsp2013-04-06T00:28:26.389ZSystemAdmin110000D4XKactive2013-04-06T00:28:26.389Z
Yes, it will produce the same result. <br />
Namely, optimal solution value equal to 0, if no violated cut exists, optimal solution value unbounded, if you have a violated cut. In this case, you can get an unbounded extreme ray as it is done in the example and construct the cut.<br />
Of course, you have to apply a bit of algebra to understand which is exactly the form of the cut (for this, I suggest you again to look at the paper that I mentioned in my previous comment), but the result is the same.<br />
<br />
Andrea
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014973621Re: auxiliary continuous variable in Master Problem in example ilobendersatsp2013-04-04T17:00:37.267ZSystemAdmin110000D4XKactive2013-04-04T17:00:37.267Z
Hi Andrea<br />
Thank you very much. Your explanation was very helpful. One more question. <br />
If I take the "row" dual, then construct a maximization problem for non-positive variables v <= 0. Is it supposed to produce the same result where the objective function is in minimization form and variables v are non-negative? <br />
Thanks again<br />
Roni
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014973429Re: auxiliary continuous variable in Master Problem in example ilobendersatsp2013-04-04T12:13:35.788ZSystemAdmin110000D4XKactive2013-04-04T12:13:35.788Z
Hi!<br />
<br />
Here's some comments and suggestions.<br />
Hope this will help.<br />
<br />
<i><b>> Can anyone please explain me the decomposition algorithm for this example?</b></i><br />
<br />
I will use the comments that are posted in the file ilobendersatsp.cpp and add some more details.<br />
<br />
The model we want to solve is a flow MILP model for the Asymmetric Traveling Salesman Problem (ATSP), that is:<br />
<br />
// ATSP instance defined on a directed graph G = (V, A)<br />
// - V = {0, ..., n-1}, V0 = V \ {0}<br />
// - A = {(i,j) : i in V, j in V, i != j }<br />
// - forall i in V: delta+(i) = {(i,j) in A : j in V}<br />
// - forall i in V: delta-(i) = {(j,i) in A : j in V}<br />
// - c(i,j) = traveling cost associated with (i,j) in A<br />
<br />
The MILP model is:<br />
<br />
// Flow MILP model<br />
//<br />
// Modeling variables:<br />
// forall (i,j) in A:<br />
// x(i,j) = 1, if arc (i,j) is selected<br />
// = 0, otherwise<br />
// forall k in V0, forall (i,j) in A:<br />
// y(k,i,j) = flow of the commodity k through arc (i,j)<br />
//<br />
// Objective:<br />
// minimize sum((i,j) in A) c(i,j) * x(i,j)<br />
//<br />
// Degree constraints:<br />
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1<br />
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1<br />
//<br />
// Binary constraints on arc variables:<br />
// forall (i,j) in A: x(i,j) in {0, 1}<br />
//<br />
// Flow constraints:<br />
// forall k in V0, forall i in V:<br />
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)<br />
// where q(k,i) = 1, if i = 0<br />
// = -1, if k == i<br />
// = 0, otherwise<br />
//<br />
// Capacity constraints:<br />
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)<br />
//<br />
// Nonnegativity of flow variables:<br />
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0<br />
<br />
Then you decompose the model into the master problem and the Benders' subproblem.<br />
<br />
The master problem is obtained by just "removing" all the flow and capacity constraints:<br />
<br />
// Master ILP<br />
//<br />
// Modeling variables:<br />
// forall (i,j) in A:<br />
// x(i,j) = 1, if arc (i,j) is selected<br />
// = 0, otherwise<br />
//<br />
// Objective:<br />
// minimize sum((i,j) in A) c(i,j) * x(i,j)<br />
//<br />
// Degree constraints:<br />
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1<br />
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1<br />
//<br />
// Binary constraints on arc variables:<br />
// forall (i,j) in A: x(i,j) in {0, 1}<br />
<br />
Of course, you will have to add to the master the Bender's cuts that will be separated on the fly through callbacks.<br />
The subproblem is the remaining part of the model (i.e., flow and capacity constraints):<br />
<br />
// Subproblem:<br />
//<br />
// minimize 0<br />
//<br />
// Flow constraints:<br />
// forall k in V0, forall i in V:<br />
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)<br />
// where q(k,i) = 1, if i = 0<br />
// = -1, if k == i<br />
// = 0, otherwise<br />
//<br />
// Capacity constraints:<br />
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)<br />
//<br />
// Nonnegativity of flow variables:<br />
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0<br />
<br />
This is a Linear Program, where y are the variables but x is fixed (at each separation step, x is the current solution provided by the master ILP). To separate cuts, you solve the dual model of the LP above (denoted as worker LP in the example):<br />
<br />
// Worker LP<br />
//<br />
// Modeling variables:<br />
// forall k in V0, i in V:<br />
// u(k,i) = dual variable associated with flow constraint (k,i)<br />
//<br />
// forall k in V0, forall (i,j) in A:<br />
// v(k,i,j) = dual variable associated with capacity constraint (k,i,j)<br />
//<br />
// Objective:<br />
// minimize sum(k in V0) sum((i,j) in A) x(i,j) * v(k,i,j)<br />
// - sum(k in V0) u(k,0) + sum(k in V0) u(k,k)<br />
//<br />
// Constraints:<br />
// forall k in V0, forall (i,j) in A: u(k,i) - u(k,j) <= v(k,i,j)<br />
//<br />
// Nonnegativity on variables v(k,i,j)<br />
// forall k in V0, forall (i,j) in A: v(k,i,j) >= 0<br />
<br />
Note that, if you take the "row" dual, then you will have a maximization problem and non-positive variables v <= 0.<br />
But you can adjust the sense of constraints and variables, in order to get a "more standard" form for the dual, like the workerLP above, where the objective function is in minimization form and variables v are non-negative. This is just for convenience.<br />
<br />
Note that the workerLP is defined on a polyhedral cone: no vertices, only the apex (0, 0, ..., 0), and rays.<br />
Thus, when you solve the workerLP, you have only two possibilities:<br />
1) Optimal solution has value 0 --> no violated cut exists<br />
2) Optimal solutio is unbounded --> you can get a so called "feasibility" Benders' cut from one of the unbounded rays:<br />
// Compute the cut from the unbounded ray. The cut is:<br />
// sum((i,j) in A) (sum(k in V0) v(k,i,j)) * x(i,j) >=<br />
// sum(k in V0) u(k,0) - u(k,k)<br />
<br />
In the general case, the workerLP may be a polyhedron (with both rays and vertices).<br />
A violated Benders'cut associated with a vertex of the workerLP is a so called "optimality" Benders' cut.<br />
<br />
<i>> While I was going through the example ilobendersatsp.cpp</i> <br />
<i>> I can't see any auxiliary continuous variable in the master problem.</i> <br />
<i>> Shouldn't be there an auxiliary continuous variable in the master problem?</i><br />
<br />
Not necessarily. You can have two situations in the original model that you want to decompose:<br />
<br />
1) The variables that you decompose appear in the objective function.<br />
Then you will end up with a master problem that contains an auxiliary continuous variable. This variable is precisely introduced to take into account the contribution to the objective function given by the variables you are decomposing.<br />
<br />
2) The variables that you decompose do not appear in the objective function (like in this example).<br />
Then you do not have any auxiliary variable in the master.<br />
<br />
Note also that, in case 1) above, the subproblem you decompose will have a non-empty objective function.<br />
This means that the workerLP will be defined on a polyhedron with both vertices and rays.<br />
In the case 2), instead (again, the one of this example), the subproblem has an empty objective function, and thus the workerLP is defined by construction on a cone with rays only.<br />
<br />
<b>> I would appreciate if you could lead me some article for this problem.</b><br />
<br />
On my opinion, the basics of Benders' decomposition (and something more) are well explained in the paper<br />
"Minimal Infeasible Subsystems and Benders' cuts", by Fischetti, Salvagning and Zanette (see http://www.dei.unipd.it/~fisch/papers/Benders_mis_extended_draft.pdf).<br />
So I suggest you to have a look at this paper. <br />
In particular, the basics are illustrated in Section 2, where you will find also an example that is precisely the ATSP, that is, the one used in in ilobendersatsp.cpp.<br />
<br />
<b>> I am also confused to see that dual subproblem in ilobendersatsp.cpp</b> <br />
<b>> is a minimization problem where in traditional bender decomposition problem</b> <br />
<b>> dual sub problem is a maximization problem.</b><br />
<br />
As I said before, the workerLP is translated to a minimization problem just for convenience.
none, view_forum, view_category