Mixing
![Google sheet SUMIFs() fixed range issue [on hold]](https://lh4.googleusercontent.com/-W8PbIQEr598/AAAAAAAAAAI/AAAAAAAAAB0/4hRLmDAMxgs/s72-c/photo.jpg?sz=32)
How to reformulate with Dantzig-Wolfe decomposition technique
$begingroup$
I am dealing with the following Binary ILP:
begin{equation*}
label{equation6}
minimize
sum_{i=1}^{m}sum_{j=1}^{n}sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt}
end{equation*}
subject to
begin{equation} label{equation3}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}x_{ijt}=1, quad (j=1....n)
end{equation}
begin{equation}
label{equation2}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}(t+p_{ij})x_{ijt}leq D, quad (j=1....n)
end{equation}
begin{equation}
label{equation5}
sum_{j=1}^{n}sum_{s=max(0,t-p_{ij})}^{t-1} RR_{j}x_{ijs} leq RC_{i}, quad (i=1....m, t=0....T)
end{equation}
begin{equation}
begin{aligned}
sum_{i=1}^{m}sum_{s=max(0,t-p_{ij})}^{T-p_{ij}} x_{ijs} +
& sum_{i=1}^{m}sum_{s=0}^{t-1} x_{ij's} leq 1,\
& (j=1....n', j'=n'+1....n, t=0....T)
end{aligned}
end{equation}
begin{equation*}
x_{ijt} in {0,1}
end{equation*}
where
Indices have following meaning
$ j $= Index of tasks to be scheduled $ (i = 1, . . . , n', n'+1,.....n) $.
$ i $ =Index of parallel machines $ (j = 1, . . . , m) $.
$ t $ =Index of time in the scheduling horizon $ (t = 0, . . . , T ) $.
Parameters (non-negative integer numbers) have following interpretations:
$ n $ = The total number of tasks. Actually, there are two sets of tasks. Set one comprises tasks from 1 to n' and set two comprises the tasks from n'+1 to n. This has already shown above in meaning of index $j$.
$ m $ = The total number of parallel machines.
$ RR_{j} $ = The amount of resource (Memory) required by task $ j $.
$ RC_{i} $ = the amount of Available resource (Memory) in machine $ i $.
$ p_{ij} $ = Processing time of task j on machine $ i $.
$ e_{ij} $ = Energy consumption while executing task $ j $ on machine $ i $
Decision variable has the following definition:
$ x_{ijt} $ = 1 if taks $ j $ is assigned on machine $ i $ at time $ t $ and 0 otherwise
A note on the problem description:
$n$ tasks are to be assigned on $m$ parallel machines over the time horizon $t$. The objective is to minimize the total energy consumption. There are total four constraints in the formulation. From top to down, Constraint 1 (assignment constraint) requires each task to be assigned to one machine only once. Constraint 2 (deadline constraint) requires that all tasks must finish their computation before the user specified deadline. Constraint 3 (capacity constraint) which requires that at any time period tasks assigned to any machine should not consume resources more than machine's capacity. The last constraint establishes the temporal dependency between the tasks in set one and tasks in set two.
Here is my question
I have implemented this IP in the IBM ILOG Cplex studio. This model is working fine and is producing accurate schedules. However, its taking too much time for a large number of tasks and machines as the number of variable and constraints increases accordingly. In order to improve the time efficiency:
Q1. Can I apply Dantzig-Wolfe decomposition to my formulation? Can anyone help to identify the master problem and other subproblem(s)?
Q2. Is there any possibility to apply Bender's decomposition?
optimization linear-programming integer-programming operations-research
asked Jan 27 at 6:05
user3606704user3606704
112
$endgroup$
add a comment |
$begingroup$
I am dealing with the following Binary ILP:
begin{equation*}
label{equation6}
minimize
sum_{i=1}^{m}sum_{j=1}^{n}sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt}
end{equation*}
subject to
begin{equation} label{equation3}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}x_{ijt}=1, quad (j=1....n)
end{equation}
begin{equation}
label{equation2}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}(t+p_{ij})x_{ijt}leq D, quad (j=1....n)
end{equation}
begin{equation}
label{equation5}
sum_{j=1}^{n}sum_{s=max(0,t-p_{ij})}^{t-1} RR_{j}x_{ijs} leq RC_{i}, quad (i=1....m, t=0....T)
end{equation}
begin{equation}
begin{aligned}
sum_{i=1}^{m}sum_{s=max(0,t-p_{ij})}^{T-p_{ij}} x_{ijs} +
& sum_{i=1}^{m}sum_{s=0}^{t-1} x_{ij's} leq 1,\
& (j=1....n', j'=n'+1....n, t=0....T)
end{aligned}
end{equation}
begin{equation*}
x_{ijt} in {0,1}
end{equation*}
where
Indices have following meaning
$ j $= Index of tasks to be scheduled $ (i = 1, . . . , n', n'+1,.....n) $.
$ i $ =Index of parallel machines $ (j = 1, . . . , m) $.
$ t $ =Index of time in the scheduling horizon $ (t = 0, . . . , T ) $.
Parameters (non-negative integer numbers) have following interpretations:
$ n $ = The total number of tasks. Actually, there are two sets of tasks. Set one comprises tasks from 1 to n' and set two comprises the tasks from n'+1 to n. This has already shown above in meaning of index $j$.
$ m $ = The total number of parallel machines.
$ RR_{j} $ = The amount of resource (Memory) required by task $ j $.
$ RC_{i} $ = the amount of Available resource (Memory) in machine $ i $.
$ p_{ij} $ = Processing time of task j on machine $ i $.
$ e_{ij} $ = Energy consumption while executing task $ j $ on machine $ i $
Decision variable has the following definition:
$ x_{ijt} $ = 1 if taks $ j $ is assigned on machine $ i $ at time $ t $ and 0 otherwise
A note on the problem description:
$n$ tasks are to be assigned on $m$ parallel machines over the time horizon $t$. The objective is to minimize the total energy consumption. There are total four constraints in the formulation. From top to down, Constraint 1 (assignment constraint) requires each task to be assigned to one machine only once. Constraint 2 (deadline constraint) requires that all tasks must finish their computation before the user specified deadline. Constraint 3 (capacity constraint) which requires that at any time period tasks assigned to any machine should not consume resources more than machine's capacity. The last constraint establishes the temporal dependency between the tasks in set one and tasks in set two.
Here is my question
I have implemented this IP in the IBM ILOG Cplex studio. This model is working fine and is producing accurate schedules. However, its taking too much time for a large number of tasks and machines as the number of variable and constraints increases accordingly. In order to improve the time efficiency:
Q1. Can I apply Dantzig-Wolfe decomposition to my formulation? Can anyone help to identify the master problem and other subproblem(s)?
Q2. Is there any possibility to apply Bender's decomposition?
optimization linear-programming integer-programming operations-research
asked Jan 27 at 6:05
user3606704user3606704
112
$endgroup$
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51
add a comment |
$begingroup$
I am dealing with the following Binary ILP:
begin{equation*}
label{equation6}
minimize
sum_{i=1}^{m}sum_{j=1}^{n}sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt}
end{equation*}
subject to
begin{equation} label{equation3}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}x_{ijt}=1, quad (j=1....n)
end{equation}
begin{equation}
label{equation2}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}(t+p_{ij})x_{ijt}leq D, quad (j=1....n)
end{equation}
begin{equation}
label{equation5}
sum_{j=1}^{n}sum_{s=max(0,t-p_{ij})}^{t-1} RR_{j}x_{ijs} leq RC_{i}, quad (i=1....m, t=0....T)
end{equation}
begin{equation}
begin{aligned}
sum_{i=1}^{m}sum_{s=max(0,t-p_{ij})}^{T-p_{ij}} x_{ijs} +
& sum_{i=1}^{m}sum_{s=0}^{t-1} x_{ij's} leq 1,\
& (j=1....n', j'=n'+1....n, t=0....T)
end{aligned}
end{equation}
begin{equation*}
x_{ijt} in {0,1}
end{equation*}
where
Indices have following meaning
$ j $= Index of tasks to be scheduled $ (i = 1, . . . , n', n'+1,.....n) $.
$ i $ =Index of parallel machines $ (j = 1, . . . , m) $.
$ t $ =Index of time in the scheduling horizon $ (t = 0, . . . , T ) $.
Parameters (non-negative integer numbers) have following interpretations:
$ n $ = The total number of tasks. Actually, there are two sets of tasks. Set one comprises tasks from 1 to n' and set two comprises the tasks from n'+1 to n. This has already shown above in meaning of index $j$.
$ m $ = The total number of parallel machines.
$ RR_{j} $ = The amount of resource (Memory) required by task $ j $.
$ RC_{i} $ = the amount of Available resource (Memory) in machine $ i $.
$ p_{ij} $ = Processing time of task j on machine $ i $.
$ e_{ij} $ = Energy consumption while executing task $ j $ on machine $ i $
Decision variable has the following definition:
$ x_{ijt} $ = 1 if taks $ j $ is assigned on machine $ i $ at time $ t $ and 0 otherwise
A note on the problem description:
$n$ tasks are to be assigned on $m$ parallel machines over the time horizon $t$. The objective is to minimize the total energy consumption. There are total four constraints in the formulation. From top to down, Constraint 1 (assignment constraint) requires each task to be assigned to one machine only once. Constraint 2 (deadline constraint) requires that all tasks must finish their computation before the user specified deadline. Constraint 3 (capacity constraint) which requires that at any time period tasks assigned to any machine should not consume resources more than machine's capacity. The last constraint establishes the temporal dependency between the tasks in set one and tasks in set two.
Here is my question
I have implemented this IP in the IBM ILOG Cplex studio. This model is working fine and is producing accurate schedules. However, its taking too much time for a large number of tasks and machines as the number of variable and constraints increases accordingly. In order to improve the time efficiency:
Q1. Can I apply Dantzig-Wolfe decomposition to my formulation? Can anyone help to identify the master problem and other subproblem(s)?
Q2. Is there any possibility to apply Bender's decomposition?
optimization linear-programming integer-programming operations-research
asked Jan 27 at 6:05
user3606704user3606704
112
$endgroup$
I am dealing with the following Binary ILP:
begin{equation*}
label{equation6}
minimize
sum_{i=1}^{m}sum_{j=1}^{n}sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt}
end{equation*}
subject to
begin{equation} label{equation3}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}x_{ijt}=1, quad (j=1....n)
end{equation}
begin{equation}
label{equation2}
sum_{i=1}^{m}sum_{t=0}^{T-p_{ij}}(t+p_{ij})x_{ijt}leq D, quad (j=1....n)
end{equation}
begin{equation}
label{equation5}
sum_{j=1}^{n}sum_{s=max(0,t-p_{ij})}^{t-1} RR_{j}x_{ijs} leq RC_{i}, quad (i=1....m, t=0....T)
end{equation}
begin{equation}
begin{aligned}
sum_{i=1}^{m}sum_{s=max(0,t-p_{ij})}^{T-p_{ij}} x_{ijs} +
& sum_{i=1}^{m}sum_{s=0}^{t-1} x_{ij's} leq 1,\
& (j=1....n', j'=n'+1....n, t=0....T)
end{aligned}
end{equation}
begin{equation*}
x_{ijt} in {0,1}
end{equation*}
where
Indices have following meaning
$ j $= Index of tasks to be scheduled $ (i = 1, . . . , n', n'+1,.....n) $.
$ i $ =Index of parallel machines $ (j = 1, . . . , m) $.
$ t $ =Index of time in the scheduling horizon $ (t = 0, . . . , T ) $.
Parameters (non-negative integer numbers) have following interpretations:
$ n $ = The total number of tasks. Actually, there are two sets of tasks. Set one comprises tasks from 1 to n' and set two comprises the tasks from n'+1 to n. This has already shown above in meaning of index $j$.
$ m $ = The total number of parallel machines.
$ RR_{j} $ = The amount of resource (Memory) required by task $ j $.
$ RC_{i} $ = the amount of Available resource (Memory) in machine $ i $.
$ p_{ij} $ = Processing time of task j on machine $ i $.
$ e_{ij} $ = Energy consumption while executing task $ j $ on machine $ i $
Decision variable has the following definition:
$ x_{ijt} $ = 1 if taks $ j $ is assigned on machine $ i $ at time $ t $ and 0 otherwise
A note on the problem description:
$n$ tasks are to be assigned on $m$ parallel machines over the time horizon $t$. The objective is to minimize the total energy consumption. There are total four constraints in the formulation. From top to down, Constraint 1 (assignment constraint) requires each task to be assigned to one machine only once. Constraint 2 (deadline constraint) requires that all tasks must finish their computation before the user specified deadline. Constraint 3 (capacity constraint) which requires that at any time period tasks assigned to any machine should not consume resources more than machine's capacity. The last constraint establishes the temporal dependency between the tasks in set one and tasks in set two.
Here is my question
I have implemented this IP in the IBM ILOG Cplex studio. This model is working fine and is producing accurate schedules. However, its taking too much time for a large number of tasks and machines as the number of variable and constraints increases accordingly. In order to improve the time efficiency:
Q1. Can I apply Dantzig-Wolfe decomposition to my formulation? Can anyone help to identify the master problem and other subproblem(s)?
Q2. Is there any possibility to apply Bender's decomposition?
optimization linear-programming integer-programming operations-research
optimization linear-programming integer-programming operations-research
asked Jan 27 at 6:05
user3606704user3606704
112
asked Jan 27 at 6:05
user3606704user3606704
112
edited Jan 28 at 14:53
user3606704
asked Jan 27 at 6:05
user3606704user3606704
112
asked Jan 27 at 6:05
user3606704user3606704
112
asked Jan 27 at 6:05
user3606704user3606704
112
112
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51
add a comment |
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :
Let $lambda_{sm}in {0,1 }$ be a binary variable that takes value $1$ if and only if schedule $s in Omega_m$ is used for machine $min M$. So $Omega_m$ is the set of feasible schedules for machine $m$. A schedule $s$ on machine $m$ requires $e_{sm}=sum_{j mid j in s} e_{mj}$ units of energy.
You want to minimize the overall energy consumption :
$$
sum_{min M}sum_{sin Omega_m} e_{sm}lambda_{sm}
$$
subject to
- Each machine has a unique schedule :
$$
sum_{sin Omega_m} lambda_{sm} = 1 quad forall m in M
$$
- Each task $j$ is assigned to a unique machine (your constraint $1$):
$$
sum_{min M}sum_{sin Omega_m mid j in s} lambda_{sm} = 1
$$
So this is your master problem. You will relax variables $lambda_{sm}$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $m$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $Omega_{m}$ sets.
You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $s$ on a given machine $m$, in terms of dual variables of the master problem above.
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089189%2fhow-to-reformulate-with-dantzig-wolfe-decomposition-technique%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :
Let $lambda_{sm}in {0,1 }$ be a binary variable that takes value $1$ if and only if schedule $s in Omega_m$ is used for machine $min M$. So $Omega_m$ is the set of feasible schedules for machine $m$. A schedule $s$ on machine $m$ requires $e_{sm}=sum_{j mid j in s} e_{mj}$ units of energy.
You want to minimize the overall energy consumption :
$$
sum_{min M}sum_{sin Omega_m} e_{sm}lambda_{sm}
$$
subject to
- Each machine has a unique schedule :
$$
sum_{sin Omega_m} lambda_{sm} = 1 quad forall m in M
$$
- Each task $j$ is assigned to a unique machine (your constraint $1$):
$$
sum_{min M}sum_{sin Omega_m mid j in s} lambda_{sm} = 1
$$
So this is your master problem. You will relax variables $lambda_{sm}$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $m$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $Omega_{m}$ sets.
You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $s$ on a given machine $m$, in terms of dual variables of the master problem above.
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
add a comment |
$begingroup$
Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :
Let $lambda_{sm}in {0,1 }$ be a binary variable that takes value $1$ if and only if schedule $s in Omega_m$ is used for machine $min M$. So $Omega_m$ is the set of feasible schedules for machine $m$. A schedule $s$ on machine $m$ requires $e_{sm}=sum_{j mid j in s} e_{mj}$ units of energy.
You want to minimize the overall energy consumption :
$$
sum_{min M}sum_{sin Omega_m} e_{sm}lambda_{sm}
$$
subject to
- Each machine has a unique schedule :
$$
sum_{sin Omega_m} lambda_{sm} = 1 quad forall m in M
$$
- Each task $j$ is assigned to a unique machine (your constraint $1$):
$$
sum_{min M}sum_{sin Omega_m mid j in s} lambda_{sm} = 1
$$
So this is your master problem. You will relax variables $lambda_{sm}$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $m$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $Omega_{m}$ sets.
You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $s$ on a given machine $m$, in terms of dual variables of the master problem above.
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
$endgroup$
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
add a comment |
$begingroup$
Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :
Let $lambda_{sm}in {0,1 }$ be a binary variable that takes value $1$ if and only if schedule $s in Omega_m$ is used for machine $min M$. So $Omega_m$ is the set of feasible schedules for machine $m$. A schedule $s$ on machine $m$ requires $e_{sm}=sum_{j mid j in s} e_{mj}$ units of energy.
You want to minimize the overall energy consumption :
$$
sum_{min M}sum_{sin Omega_m} e_{sm}lambda_{sm}
$$
subject to
- Each machine has a unique schedule :
$$
sum_{sin Omega_m} lambda_{sm} = 1 quad forall m in M
$$
- Each task $j$ is assigned to a unique machine (your constraint $1$):
$$
sum_{min M}sum_{sin Omega_m mid j in s} lambda_{sm} = 1
$$
So this is your master problem. You will relax variables $lambda_{sm}$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $m$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $Omega_{m}$ sets.
You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $s$ on a given machine $m$, in terms of dual variables of the master problem above.
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
$endgroup$
Here is one option. You can define schedules for one machine in your subproblem, and merge the schedules in the master problem. Something as follows :
Let $lambda_{sm}in {0,1 }$ be a binary variable that takes value $1$ if and only if schedule $s in Omega_m$ is used for machine $min M$. So $Omega_m$ is the set of feasible schedules for machine $m$. A schedule $s$ on machine $m$ requires $e_{sm}=sum_{j mid j in s} e_{mj}$ units of energy.
You want to minimize the overall energy consumption :
$$
sum_{min M}sum_{sin Omega_m} e_{sm}lambda_{sm}
$$
subject to
- Each machine has a unique schedule :
$$
sum_{sin Omega_m} lambda_{sm} = 1 quad forall m in M
$$
- Each task $j$ is assigned to a unique machine (your constraint $1$):
$$
sum_{min M}sum_{sin Omega_m mid j in s} lambda_{sm} = 1
$$
So this is your master problem. You will relax variables $lambda_{sm}$. Your other constraints define your subproblem (and thus your feasible schedules). Actually, you will have one subproblem per machine. More specifically, a schedule will be feasible for machine $m$ if deadlines constraints are met for each task of the schedule, if capacity constraints hold for the machine, and if temporal dependency constraints are met for each task. Such schedules will define your $Omega_{m}$ sets.
You will need to adapt the objective function of your subproblem. It should equal the reduced cost of a schedule $s$ on a given machine $m$, in terms of dual variables of the master problem above.
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
edited Jan 28 at 16:19
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
answered Jan 28 at 15:50
KuifjeKuifje
7,2722726
7,2722726
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
add a comment |
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
I get some clue by your explain but I don't understand it well. I think I should devote some more time to identify block structure in my problem. Once I explore the topic well, I will ping you here if I get any doubt. Thanks for your response.
$endgroup$
– user3606704
Jan 29 at 17:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
@ Kuifje Please have a look into the following paper: citeseerx.ist.psu.edu/viewdoc/… In this paper, Dantzig-Wolfe decomposition has been applied to the time-indexed formulation of a single machine problem. I want to apply the same procedure for my parallel machine problem. I am unable to figure out which constraint(s) would form my master problem and which will be kept as subproblems? And, further what would be my pricing problem? I am not even being able to establish the primal block angular structure in my formulation. Please help.
$endgroup$
– user3606704
Jan 30 at 14:53
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
The model I proposed is pretty much the same as the one on page $7$, but the notations are a little different. To apply Dantzig-Wolfe, you need to understand what the decomposition "physically" represents. What do your master problem variables physically represent ? A feasible schedule, this is key. In your master problem, you only need your constraints (1), and you add convexity constraints (my first constraint).
$endgroup$
– Kuifje
Jan 31 at 12:38
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
I get your point in your suggested solution. However, as per my understanding, you have changed my original time-indexed formulation with a new formulation and decision variable. I want to apply decomposition in my formulation. I think It is too hard to find primal block angular structure (i.e. necessary conditions for the applicability of Dantzig-Wolfe technique) in my formulation.
$endgroup$
– user3606704
Feb 1 at 16:22
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
$begingroup$
Can I put constraint 1 in Master problem and make all other three constarints as three different subproblems?
$endgroup$
– user3606704
Feb 1 at 17:47
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089189%2fhow-to-reformulate-with-dantzig-wolfe-decomposition-technique%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
It would be easier to help you if you added some context. Explain what each variable represents, and what each constraint means.
$endgroup$
– Kuifje
Jan 28 at 8:42
$begingroup$
@Kuifje Thanks for paying attention. I have updated the question.
$endgroup$
– user3606704
Jan 28 at 14:51