Facility Location Problem with Integer Linear Programming
up vote
1
down vote
favorite
I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. These have yet to be built and there are 20 possible locations for these facilities.
When setting the objective function and the constraints, it is a challenge to link the maximum of 3 facilities with links between customer and facility in the constraints. Let me explain a bit more mathematically. Please assume that demand and capacity is not an issue and that each route is driven once per time unit.
Between customer i and facility j, there is a possible link Xij. When Xij is 1, it means that a connection is established, and 0 if not. There can be 3 facilities Yj opened. The cost function Cij of opening a link is used in the objective function.
The objective function
$$MIN quad sum_{i=1}^{50}sum_{j=1}^{20}C_{ij} X_{ij}$$
defines the goal of minimizing costs.
This is constrained by:
$$
sum_{j=1}^{20} Y_j le 3 quad mbox{(there may be 3 facilities opened)}
$$
Now my issue is, how can this Yj be related to the Xij, meaning that there cannot be a link opened between a customer and non-existing facility?
I was thinking something with:
$$
sum_{i=1}^{50} X_{ij} ge Y_j
$$
There cannot be a link between a facility if that one is not opened, but the number of links with a specific facility is unlimited
Is my way of thinking correct and would it work, or is there something wrong with my way of thinking?
linear-programming
edited Nov 21 at 12:40
Kuifje
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
add a comment |
up vote
1
down vote
favorite
I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. These have yet to be built and there are 20 possible locations for these facilities.
When setting the objective function and the constraints, it is a challenge to link the maximum of 3 facilities with links between customer and facility in the constraints. Let me explain a bit more mathematically. Please assume that demand and capacity is not an issue and that each route is driven once per time unit.
Between customer i and facility j, there is a possible link Xij. When Xij is 1, it means that a connection is established, and 0 if not. There can be 3 facilities Yj opened. The cost function Cij of opening a link is used in the objective function.
The objective function
$$MIN quad sum_{i=1}^{50}sum_{j=1}^{20}C_{ij} X_{ij}$$
defines the goal of minimizing costs.
This is constrained by:
$$
sum_{j=1}^{20} Y_j le 3 quad mbox{(there may be 3 facilities opened)}
$$
Now my issue is, how can this Yj be related to the Xij, meaning that there cannot be a link opened between a customer and non-existing facility?
I was thinking something with:
$$
sum_{i=1}^{50} X_{ij} ge Y_j
$$
There cannot be a link between a facility if that one is not opened, but the number of links with a specific facility is unlimited
Is my way of thinking correct and would it work, or is there something wrong with my way of thinking?
linear-programming
edited Nov 21 at 12:40
Kuifje
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. These have yet to be built and there are 20 possible locations for these facilities.
When setting the objective function and the constraints, it is a challenge to link the maximum of 3 facilities with links between customer and facility in the constraints. Let me explain a bit more mathematically. Please assume that demand and capacity is not an issue and that each route is driven once per time unit.
Between customer i and facility j, there is a possible link Xij. When Xij is 1, it means that a connection is established, and 0 if not. There can be 3 facilities Yj opened. The cost function Cij of opening a link is used in the objective function.
The objective function
$$MIN quad sum_{i=1}^{50}sum_{j=1}^{20}C_{ij} X_{ij}$$
defines the goal of minimizing costs.
This is constrained by:
$$
sum_{j=1}^{20} Y_j le 3 quad mbox{(there may be 3 facilities opened)}
$$
Now my issue is, how can this Yj be related to the Xij, meaning that there cannot be a link opened between a customer and non-existing facility?
I was thinking something with:
$$
sum_{i=1}^{50} X_{ij} ge Y_j
$$
There cannot be a link between a facility if that one is not opened, but the number of links with a specific facility is unlimited
Is my way of thinking correct and would it work, or is there something wrong with my way of thinking?
linear-programming
edited Nov 21 at 12:40
Kuifje
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. These have yet to be built and there are 20 possible locations for these facilities.
When setting the objective function and the constraints, it is a challenge to link the maximum of 3 facilities with links between customer and facility in the constraints. Let me explain a bit more mathematically. Please assume that demand and capacity is not an issue and that each route is driven once per time unit.
Between customer i and facility j, there is a possible link Xij. When Xij is 1, it means that a connection is established, and 0 if not. There can be 3 facilities Yj opened. The cost function Cij of opening a link is used in the objective function.
The objective function
$$MIN quad sum_{i=1}^{50}sum_{j=1}^{20}C_{ij} X_{ij}$$
defines the goal of minimizing costs.
This is constrained by:
$$
sum_{j=1}^{20} Y_j le 3 quad mbox{(there may be 3 facilities opened)}
$$
Now my issue is, how can this Yj be related to the Xij, meaning that there cannot be a link opened between a customer and non-existing facility?
I was thinking something with:
$$
sum_{i=1}^{50} X_{ij} ge Y_j
$$
There cannot be a link between a facility if that one is not opened, but the number of links with a specific facility is unlimited
Is my way of thinking correct and would it work, or is there something wrong with my way of thinking?
linear-programming
linear-programming
edited Nov 21 at 12:40
Kuifje
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
edited Nov 21 at 12:40
Kuifje
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
edited Nov 21 at 12:40
Kuifje
7,0232625
edited Nov 21 at 12:40
Kuifje
7,0232625
edited Nov 21 at 12:40
Kuifje
7,0232625
7,0232625
asked Nov 19 at 20:24
Tyler Johnson
61
asked Nov 19 at 20:24
Tyler Johnson
61
asked Nov 19 at 20:24
Tyler Johnson
61
61
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33
add a comment |
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Each customer should be assigned to exactly one facility :
$$sum_{j=1}^{20} X_{ij}=1 quad forall i=1,...,50$$
and if customer $i$ is assigned to facility $j$, it means that facility $j$ is opened :
$$
X_{ij} le Y_jquad forall i=1,...,50 quad forall j =1,...,20
$$
answered Nov 21 at 12:28
Kuifje
7,0232625
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',
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%2f3005476%2ffacility-location-problem-with-integer-linear-programming%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
up vote
0
down vote
Each customer should be assigned to exactly one facility :
$$sum_{j=1}^{20} X_{ij}=1 quad forall i=1,...,50$$
and if customer $i$ is assigned to facility $j$, it means that facility $j$ is opened :
$$
X_{ij} le Y_jquad forall i=1,...,50 quad forall j =1,...,20
$$
answered Nov 21 at 12:28
Kuifje
7,0232625
add a comment |
up vote
0
down vote
Each customer should be assigned to exactly one facility :
$$sum_{j=1}^{20} X_{ij}=1 quad forall i=1,...,50$$
and if customer $i$ is assigned to facility $j$, it means that facility $j$ is opened :
$$
X_{ij} le Y_jquad forall i=1,...,50 quad forall j =1,...,20
$$
answered Nov 21 at 12:28
Kuifje
7,0232625
add a comment |
up vote
0
down vote
up vote
0
down vote
Each customer should be assigned to exactly one facility :
$$sum_{j=1}^{20} X_{ij}=1 quad forall i=1,...,50$$
and if customer $i$ is assigned to facility $j$, it means that facility $j$ is opened :
$$
X_{ij} le Y_jquad forall i=1,...,50 quad forall j =1,...,20
$$
answered Nov 21 at 12:28
Kuifje
7,0232625
Each customer should be assigned to exactly one facility :
$$sum_{j=1}^{20} X_{ij}=1 quad forall i=1,...,50$$
and if customer $i$ is assigned to facility $j$, it means that facility $j$ is opened :
$$
X_{ij} le Y_jquad forall i=1,...,50 quad forall j =1,...,20
$$
answered Nov 21 at 12:28
Kuifje
7,0232625
answered Nov 21 at 12:28
Kuifje
7,0232625
answered Nov 21 at 12:28
Kuifje
7,0232625
answered Nov 21 at 12:28
Kuifje
7,0232625
7,0232625
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3005476%2ffacility-location-problem-with-integer-linear-programming%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
It is right. The constraint is $$sum_{i=1}^{50}X_{ij} geq Y_j forall j=1,2,3$$ $X_{ij}, Y_jin {0,1}$
– callculus
Nov 19 at 22:49
@callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$.
– Kuifje
Nov 21 at 12:33