methods to solve a 01 linear programming problem with a matrix variable
$begingroup$
I have some problems to solve a two dimensional 01 programming problem. The problem has a similar body as follows,
${text{min}}_{{x_{ij}}} sum_i sum_j x_{ij} c_{ij}$
s.t. $sum_i x_{ij} leq 1$
$sum_j x_{ij} leq 1$
$x_{ij} in {0,1}$
The range of $i$ and $j$ are large. I think for one dimensional variable $x_iin{0,1}$, the problem can be solved by bisection method or Dinkelbach method. While as the problem has constraints in two dimension $i$ and $j$, I am not sure if these methods can still be effective. Moreover, since the variable matrix $X={x_{ij},forall i,j}$ is a sparse matrix, I wonder if there are some matrix related methods that can solve this problem. I'd like to ask about mathematic methods rather than computing tools such as CPLEX.
Thanks a lot if you guys can give me some advices!
convex-optimization linear-programming
asked Dec 24 '18 at 3:28
user3919259user3919259
52
$endgroup$
add a comment |
$begingroup$
I have some problems to solve a two dimensional 01 programming problem. The problem has a similar body as follows,
${text{min}}_{{x_{ij}}} sum_i sum_j x_{ij} c_{ij}$
s.t. $sum_i x_{ij} leq 1$
$sum_j x_{ij} leq 1$
$x_{ij} in {0,1}$
The range of $i$ and $j$ are large. I think for one dimensional variable $x_iin{0,1}$, the problem can be solved by bisection method or Dinkelbach method. While as the problem has constraints in two dimension $i$ and $j$, I am not sure if these methods can still be effective. Moreover, since the variable matrix $X={x_{ij},forall i,j}$ is a sparse matrix, I wonder if there are some matrix related methods that can solve this problem. I'd like to ask about mathematic methods rather than computing tools such as CPLEX.
Thanks a lot if you guys can give me some advices!
convex-optimization linear-programming
asked Dec 24 '18 at 3:28
user3919259user3919259
52
$endgroup$
$begingroup$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09
add a comment |
$begingroup$
I have some problems to solve a two dimensional 01 programming problem. The problem has a similar body as follows,
${text{min}}_{{x_{ij}}} sum_i sum_j x_{ij} c_{ij}$
s.t. $sum_i x_{ij} leq 1$
$sum_j x_{ij} leq 1$
$x_{ij} in {0,1}$
The range of $i$ and $j$ are large. I think for one dimensional variable $x_iin{0,1}$, the problem can be solved by bisection method or Dinkelbach method. While as the problem has constraints in two dimension $i$ and $j$, I am not sure if these methods can still be effective. Moreover, since the variable matrix $X={x_{ij},forall i,j}$ is a sparse matrix, I wonder if there are some matrix related methods that can solve this problem. I'd like to ask about mathematic methods rather than computing tools such as CPLEX.
Thanks a lot if you guys can give me some advices!
convex-optimization linear-programming
asked Dec 24 '18 at 3:28
user3919259user3919259
52
$endgroup$
I have some problems to solve a two dimensional 01 programming problem. The problem has a similar body as follows,
${text{min}}_{{x_{ij}}} sum_i sum_j x_{ij} c_{ij}$
s.t. $sum_i x_{ij} leq 1$
$sum_j x_{ij} leq 1$
$x_{ij} in {0,1}$
The range of $i$ and $j$ are large. I think for one dimensional variable $x_iin{0,1}$, the problem can be solved by bisection method or Dinkelbach method. While as the problem has constraints in two dimension $i$ and $j$, I am not sure if these methods can still be effective. Moreover, since the variable matrix $X={x_{ij},forall i,j}$ is a sparse matrix, I wonder if there are some matrix related methods that can solve this problem. I'd like to ask about mathematic methods rather than computing tools such as CPLEX.
Thanks a lot if you guys can give me some advices!
convex-optimization linear-programming
convex-optimization linear-programming
asked Dec 24 '18 at 3:28
user3919259user3919259
52
asked Dec 24 '18 at 3:28
user3919259user3919259
52
edited Dec 24 '18 at 9:30
user3919259
asked Dec 24 '18 at 3:28
user3919259user3919259
52
asked Dec 24 '18 at 3:28
user3919259user3919259
52
asked Dec 24 '18 at 3:28
user3919259user3919259
52
52
$begingroup$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09
add a comment |
$begingroup$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09
$begingroup$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09
$begingroup$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
$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%2f3050902%2fmethods-to-solve-a-01-linear-programming-problem-with-a-matrix-variable%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$
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
$endgroup$
add a comment |
$begingroup$
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
$endgroup$
add a comment |
$begingroup$
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
$endgroup$
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
answered Dec 24 '18 at 9:53
VincenzoVincenzo
1916
1916
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%2f3050902%2fmethods-to-solve-a-01-linear-programming-problem-with-a-matrix-variable%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$
The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable'
$endgroup$
– Alex Shtof
Dec 24 '18 at 9:09