Assignment problem with constrained on agents
$begingroup$
I've spent a decent amount of time looking for the solution to the problem, which seems to be a variant of the assignment problem with constraints on the agents.
For a simple example, consider this:
A primary school has $m$ teachers who are to be assigned to teach $n$ courses. Each of these teachers is able to teach more than one but not all courses. For instance, Alice can teach Math and Chemistry, Bob can teach Chemistry and Physics, Cathy can teach Physics and Music, and so on. The goal is to design the assignment of teachers to the courses. Note that apparently a teacher not in the set of Music can't be assigned to the Music course. Assume there is no limit on how many courses each teacher can be assigned to, but each teacher should at least teach one course.
Mathematically, let us define $textbf{X} in {0,1}^{m times n}$ as the assignment matrix where $x_{i,j}=1$ indicates that Teacher $i$ is assigned to Course $j$ and $x_{i,j}=0$ otherwise. For each course $j in {1,cdots,n}$, the set of available teachers is denoted by $textbf{S}_j$.
Then, the constraints can be written as
$sumlimits_{i in textbf{S}_j} x_{i,j} = text{integer const}, quad forall j$
$sumlimits_{j=1}^n x_{i,j} geq 1, quad forall i $
The objective can be similarly formulated as the standard assignment problem.
Compared to the standard assignment problem, the main difference is that in the first constraint the sum is taken over a given set of agents instead of over all agents.
One possible approach that came to my mind is to write the constraints as the standard assignment problem, i.e., assuming $textbf{S}_j = {1,cdots,m}$ for any $j$, and impose a high cost for the non-existent edges between agents and tasks in the objective.
I appreciate it if anyone can shed any light on this problem. Thanks very much.
combinatorics optimization linear-programming
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
$endgroup$
add a comment |
$begingroup$
I've spent a decent amount of time looking for the solution to the problem, which seems to be a variant of the assignment problem with constraints on the agents.
For a simple example, consider this:
A primary school has $m$ teachers who are to be assigned to teach $n$ courses. Each of these teachers is able to teach more than one but not all courses. For instance, Alice can teach Math and Chemistry, Bob can teach Chemistry and Physics, Cathy can teach Physics and Music, and so on. The goal is to design the assignment of teachers to the courses. Note that apparently a teacher not in the set of Music can't be assigned to the Music course. Assume there is no limit on how many courses each teacher can be assigned to, but each teacher should at least teach one course.
Mathematically, let us define $textbf{X} in {0,1}^{m times n}$ as the assignment matrix where $x_{i,j}=1$ indicates that Teacher $i$ is assigned to Course $j$ and $x_{i,j}=0$ otherwise. For each course $j in {1,cdots,n}$, the set of available teachers is denoted by $textbf{S}_j$.
Then, the constraints can be written as
$sumlimits_{i in textbf{S}_j} x_{i,j} = text{integer const}, quad forall j$
$sumlimits_{j=1}^n x_{i,j} geq 1, quad forall i $
The objective can be similarly formulated as the standard assignment problem.
Compared to the standard assignment problem, the main difference is that in the first constraint the sum is taken over a given set of agents instead of over all agents.
One possible approach that came to my mind is to write the constraints as the standard assignment problem, i.e., assuming $textbf{S}_j = {1,cdots,m}$ for any $j$, and impose a high cost for the non-existent edges between agents and tasks in the objective.
I appreciate it if anyone can shed any light on this problem. Thanks very much.
combinatorics optimization linear-programming
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
$endgroup$
2
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13
add a comment |
$begingroup$
I've spent a decent amount of time looking for the solution to the problem, which seems to be a variant of the assignment problem with constraints on the agents.
For a simple example, consider this:
A primary school has $m$ teachers who are to be assigned to teach $n$ courses. Each of these teachers is able to teach more than one but not all courses. For instance, Alice can teach Math and Chemistry, Bob can teach Chemistry and Physics, Cathy can teach Physics and Music, and so on. The goal is to design the assignment of teachers to the courses. Note that apparently a teacher not in the set of Music can't be assigned to the Music course. Assume there is no limit on how many courses each teacher can be assigned to, but each teacher should at least teach one course.
Mathematically, let us define $textbf{X} in {0,1}^{m times n}$ as the assignment matrix where $x_{i,j}=1$ indicates that Teacher $i$ is assigned to Course $j$ and $x_{i,j}=0$ otherwise. For each course $j in {1,cdots,n}$, the set of available teachers is denoted by $textbf{S}_j$.
Then, the constraints can be written as
$sumlimits_{i in textbf{S}_j} x_{i,j} = text{integer const}, quad forall j$
$sumlimits_{j=1}^n x_{i,j} geq 1, quad forall i $
The objective can be similarly formulated as the standard assignment problem.
Compared to the standard assignment problem, the main difference is that in the first constraint the sum is taken over a given set of agents instead of over all agents.
One possible approach that came to my mind is to write the constraints as the standard assignment problem, i.e., assuming $textbf{S}_j = {1,cdots,m}$ for any $j$, and impose a high cost for the non-existent edges between agents and tasks in the objective.
I appreciate it if anyone can shed any light on this problem. Thanks very much.
combinatorics optimization linear-programming
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
$endgroup$
I've spent a decent amount of time looking for the solution to the problem, which seems to be a variant of the assignment problem with constraints on the agents.
For a simple example, consider this:
A primary school has $m$ teachers who are to be assigned to teach $n$ courses. Each of these teachers is able to teach more than one but not all courses. For instance, Alice can teach Math and Chemistry, Bob can teach Chemistry and Physics, Cathy can teach Physics and Music, and so on. The goal is to design the assignment of teachers to the courses. Note that apparently a teacher not in the set of Music can't be assigned to the Music course. Assume there is no limit on how many courses each teacher can be assigned to, but each teacher should at least teach one course.
Mathematically, let us define $textbf{X} in {0,1}^{m times n}$ as the assignment matrix where $x_{i,j}=1$ indicates that Teacher $i$ is assigned to Course $j$ and $x_{i,j}=0$ otherwise. For each course $j in {1,cdots,n}$, the set of available teachers is denoted by $textbf{S}_j$.
Then, the constraints can be written as
$sumlimits_{i in textbf{S}_j} x_{i,j} = text{integer const}, quad forall j$
$sumlimits_{j=1}^n x_{i,j} geq 1, quad forall i $
The objective can be similarly formulated as the standard assignment problem.
Compared to the standard assignment problem, the main difference is that in the first constraint the sum is taken over a given set of agents instead of over all agents.
One possible approach that came to my mind is to write the constraints as the standard assignment problem, i.e., assuming $textbf{S}_j = {1,cdots,m}$ for any $j$, and impose a high cost for the non-existent edges between agents and tasks in the objective.
I appreciate it if anyone can shed any light on this problem. Thanks very much.
combinatorics optimization linear-programming
combinatorics optimization linear-programming
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
edited Jan 16 at 16:02
J Zhao
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
asked Jan 15 at 16:55
J ZhaoJ Zhao
62
62
2
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13
add a comment |
2
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13
2
2
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13
add a comment |
0
active
oldest
votes
Your Answer
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%2f3074640%2fassignment-problem-with-constrained-on-agents%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3074640%2fassignment-problem-with-constrained-on-agents%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
2
$begingroup$
Start by defining your variables : let $x_{ij}in {0,1}$ be a variable that takes value $1$ if and only only if teacher $i$ is assigned to course $j$. Can you finish ?
$endgroup$
– Kuifje
Jan 15 at 19:16
$begingroup$
@Kuifje Thanks for your comment. I've added mathematical description for the constraints. Hope this will be clearer. Thank you for your help.
$endgroup$
– J Zhao
Jan 16 at 14:56
$begingroup$
With $const:=1$, you are good. And just minimize $sum_{i,j}c_{ij} x_{ij}$
$endgroup$
– Kuifje
Jan 16 at 15:04
$begingroup$
@Kuifje Thank you so much for the prompt reply. I learned that integral solutions are guaranteed for the standard assignment problem if the RHS vector is also integral, as the constraint matrix is totally unimodular. However, with this modified formulation, the constraint matrix is no longer totally unimodular. I'm thinking of stating the constraints as the classical problem, but imposing large $c_{i,j}$ for $i notin textbf{S}_j$. Do you know any references giving any guarantee for this approach? Thanks!
$endgroup$
– J Zhao
Jan 16 at 15:59
$begingroup$
I am pretty sur you can relax integrity constraints here as well. But how big is the size of your problem ? If it is not too big, just solve it as is with binary variables and you will be fine.
$endgroup$
– Kuifje
Jan 16 at 20:13