Project allocation optimisation Code
$begingroup$
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
Variables
$X_{i,j}$ = 1, if student i is allocated to project j and 0, otherwise
$C_{i,j}$ can take any value in set C where,C ∈ [1,2,3]
Constraints
$sum_{j=1}^{Tp} X_{i,j} = 1$
Each student is allocated to one project where Tp = total projects
$sum_{i=1}^{Ts} X_{i,j} = 1$
Each project is allocated to one student where Ts = total students
$sum_{j=1}^{Tp} C_{i,j} times X_{i,j} geq 1$
Each student is allocated a project that is one of their preferences
Objective Function
Minimize $sum_{i=1}^{Ts}sum_{j=1}^{Tp} C_{i,j} times X_{i,j}$
To minimize the sum of the rankings.
How can I code this integer optimisation problem in MATLAB or another way?
Thank you!!
optimization algorithms linear-programming integer-programming mixed-integer-programming
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
$endgroup$
add a comment |
$begingroup$
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
Variables
$X_{i,j}$ = 1, if student i is allocated to project j and 0, otherwise
$C_{i,j}$ can take any value in set C where,C ∈ [1,2,3]
Constraints
$sum_{j=1}^{Tp} X_{i,j} = 1$
Each student is allocated to one project where Tp = total projects
$sum_{i=1}^{Ts} X_{i,j} = 1$
Each project is allocated to one student where Ts = total students
$sum_{j=1}^{Tp} C_{i,j} times X_{i,j} geq 1$
Each student is allocated a project that is one of their preferences
Objective Function
Minimize $sum_{i=1}^{Ts}sum_{j=1}^{Tp} C_{i,j} times X_{i,j}$
To minimize the sum of the rankings.
How can I code this integer optimisation problem in MATLAB or another way?
Thank you!!
optimization algorithms linear-programming integer-programming mixed-integer-programming
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
$endgroup$
$begingroup$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31
add a comment |
$begingroup$
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
Variables
$X_{i,j}$ = 1, if student i is allocated to project j and 0, otherwise
$C_{i,j}$ can take any value in set C where,C ∈ [1,2,3]
Constraints
$sum_{j=1}^{Tp} X_{i,j} = 1$
Each student is allocated to one project where Tp = total projects
$sum_{i=1}^{Ts} X_{i,j} = 1$
Each project is allocated to one student where Ts = total students
$sum_{j=1}^{Tp} C_{i,j} times X_{i,j} geq 1$
Each student is allocated a project that is one of their preferences
Objective Function
Minimize $sum_{i=1}^{Ts}sum_{j=1}^{Tp} C_{i,j} times X_{i,j}$
To minimize the sum of the rankings.
How can I code this integer optimisation problem in MATLAB or another way?
Thank you!!
optimization algorithms linear-programming integer-programming mixed-integer-programming
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
$endgroup$
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
Variables
$X_{i,j}$ = 1, if student i is allocated to project j and 0, otherwise
$C_{i,j}$ can take any value in set C where,C ∈ [1,2,3]
Constraints
$sum_{j=1}^{Tp} X_{i,j} = 1$
Each student is allocated to one project where Tp = total projects
$sum_{i=1}^{Ts} X_{i,j} = 1$
Each project is allocated to one student where Ts = total students
$sum_{j=1}^{Tp} C_{i,j} times X_{i,j} geq 1$
Each student is allocated a project that is one of their preferences
Objective Function
Minimize $sum_{i=1}^{Ts}sum_{j=1}^{Tp} C_{i,j} times X_{i,j}$
To minimize the sum of the rankings.
How can I code this integer optimisation problem in MATLAB or another way?
Thank you!!
optimization algorithms linear-programming integer-programming mixed-integer-programming
optimization algorithms linear-programming integer-programming mixed-integer-programming
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
edited Jan 12 at 16:55
Mwana Hussein
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
asked Jan 12 at 16:10
Mwana HusseinMwana Hussein
12
12
$begingroup$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31
add a comment |
$begingroup$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31
$begingroup$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
First, a comment: I don't see the purpose of the third constraint ($sum_{j=1}^{T_p} C_{i,j} X_{i,j} ge 1$). Since $C_{i,j}ge 1$, this constraint is implied by the first one (assign every student to a project).
Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.
answered Jan 12 at 19:55
prubinprubin
1,515125
$endgroup$
add a comment |
$begingroup$
I agree with @prubin in both statements.
There is no need for the third constraint and Excel + Solver may solve your problem.
In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/
Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.
It can even have some interactive tools (forms, interface with spreadsheets, etc.).
An short example with your code:
https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M
An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).
answered Jan 23 at 2:36
SghatSghat
1
$endgroup$
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%2f3071062%2fproject-allocation-optimisation-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
First, a comment: I don't see the purpose of the third constraint ($sum_{j=1}^{T_p} C_{i,j} X_{i,j} ge 1$). Since $C_{i,j}ge 1$, this constraint is implied by the first one (assign every student to a project).
Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.
answered Jan 12 at 19:55
prubinprubin
1,515125
$endgroup$
add a comment |
$begingroup$
First, a comment: I don't see the purpose of the third constraint ($sum_{j=1}^{T_p} C_{i,j} X_{i,j} ge 1$). Since $C_{i,j}ge 1$, this constraint is implied by the first one (assign every student to a project).
Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.
answered Jan 12 at 19:55
prubinprubin
1,515125
$endgroup$
add a comment |
$begingroup$
First, a comment: I don't see the purpose of the third constraint ($sum_{j=1}^{T_p} C_{i,j} X_{i,j} ge 1$). Since $C_{i,j}ge 1$, this constraint is implied by the first one (assign every student to a project).
Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.
answered Jan 12 at 19:55
prubinprubin
1,515125
$endgroup$
First, a comment: I don't see the purpose of the third constraint ($sum_{j=1}^{T_p} C_{i,j} X_{i,j} ge 1$). Since $C_{i,j}ge 1$, this constraint is implied by the first one (assign every student to a project).
Second,regarding software, you could solve this in Excel (assuming a "reasonable" number of students and projects). Excel has a built-in linear programming solver, with limited capacity (but enough to do this for one class). There is also an open-source plug-in (OpenSolver) that works quite well and handles larger problem instances. If you are comfortable with spreadsheets but not an Excel user, OpenSolver also has a version for Google Sheets. To do it in MATLAB, you might start here: https://www.mathworks.com/help/optim/ug/first-choose-problem-based-or-solver-based-approach.html.
answered Jan 12 at 19:55
prubinprubin
1,515125
answered Jan 12 at 19:55
prubinprubin
1,515125
answered Jan 12 at 19:55
prubinprubin
1,515125
answered Jan 12 at 19:55
prubinprubin
1,515125
1,515125
add a comment |
add a comment |
$begingroup$
I agree with @prubin in both statements.
There is no need for the third constraint and Excel + Solver may solve your problem.
In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/
Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.
It can even have some interactive tools (forms, interface with spreadsheets, etc.).
An short example with your code:
https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M
An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).
answered Jan 23 at 2:36
SghatSghat
1
$endgroup$
add a comment |
$begingroup$
I agree with @prubin in both statements.
There is no need for the third constraint and Excel + Solver may solve your problem.
In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/
Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.
It can even have some interactive tools (forms, interface with spreadsheets, etc.).
An short example with your code:
https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M
An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).
answered Jan 23 at 2:36
SghatSghat
1
$endgroup$
add a comment |
$begingroup$
I agree with @prubin in both statements.
There is no need for the third constraint and Excel + Solver may solve your problem.
In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/
Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.
It can even have some interactive tools (forms, interface with spreadsheets, etc.).
An short example with your code:
https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M
An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).
answered Jan 23 at 2:36
SghatSghat
1
$endgroup$
I agree with @prubin in both statements.
There is no need for the third constraint and Excel + Solver may solve your problem.
In case you are looking for something a bit more robust, I strongly recommend Google Colab (enviroment for Python notebooks): https://colab.research.google.com/
Combine it with OR tools (https://developers.google.com/optimization/lp) and you will have a good tool to solve and teach linear programming problems right from the web browser.
It can even have some interactive tools (forms, interface with spreadsheets, etc.).
An short example with your code:
https://colab.research.google.com/drive/1ukeA5Isx9COqHjAuDbUCecAlHhdUid8M
An alternative could be Gusek (http://gusek.sourceforge.net/gusek.html).
answered Jan 23 at 2:36
SghatSghat
1
answered Jan 23 at 2:36
SghatSghat
1
answered Jan 23 at 2:36
SghatSghat
1
answered Jan 23 at 2:36
SghatSghat
1
1
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.
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%2f3071062%2fproject-allocation-optimisation-code%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$
Welcome to Math.SE! Our strengths will tend more to helping with algorithms, e.g. for your integer programming problem, rather than with advice about writing code. You might look up the Hungarian algorithm for assignment problems.
$endgroup$
– hardmath
Jan 12 at 16:21
$begingroup$
This is a good option : pypi.org/project/PuLP . Easy and effective
$endgroup$
– Kuifje
Jan 12 at 16:37
$begingroup$
thanks hardmath, Kuifje
$endgroup$
– Mwana Hussein
Jan 12 at 17:31