Timeline for Closed-form solution of a linear programming question
Current License: CC BY-SA 3.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2016 at 0:45 | history | undeleted | Jerry Jiannan Lu | ||
| Apr 2, 2016 at 0:43 | history | deleted | Jerry Jiannan Lu | via Vote | |
| Apr 1, 2016 at 16:44 | comment | added | Jerry Jiannan Lu | Let us continue this discussion in chat. | |
| Apr 1, 2016 at 8:07 | comment | added | Brendan McKay | Another observation is that this is an example of a minimum-cost flow problem. Optimal solutions can be characterised. See perso.ens-lyon.fr/eric.thierry/Graphes2010/amaury-pouly.pdf for example | |
| Apr 1, 2016 at 7:12 | comment | added | Brendan McKay | You can just scale integer matrices to make the entries sum to 1, and real matrices are approximated arbitrarily closely by rational matrices. So I think such things as description of the vertices remain the same. | |
| Apr 1, 2016 at 6:36 | comment | added | Jerry Jiannan Lu | @BrendanMcKay Thank you very much, I'll make sure to read them carefully. One more point -- it seems that the references you mentioned mainly addressed "integer linear programming" questions. If we are doing this just for real numbers, would the solutions be easier to obtain? | |
| Apr 1, 2016 at 5:48 | comment | added | Brendan McKay | There is a description and algorithm in the accepted answer of this question: mathoverflow.net/questions/75873/… . The referenced book of Brualdi is at books.google.com/books?id=xdP9d8S1BxQC . | |
| Apr 1, 2016 at 4:28 | comment | added | Jerry Jiannan Lu | @BrendanMcKay I admittedly have no knowledge of transportation polytope and just looked it up. It does seem to be what I am looking for. Any chance you can point me to some literature on the "well-known vertices?" Thank you very much! | |
| Apr 1, 2016 at 4:21 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 22 characters in body
|
| Apr 1, 2016 at 4:19 | comment | added | Jerry Jiannan Lu | Thanks @BrendanMcKay for pointing out this confusion. Yes I have this condition here. I didn't write it down explicitly, because I thought "probability matrix" already covers it. Let me write it down. | |
| Apr 1, 2016 at 4:09 | comment | added | Brendan McKay | In your thesis you seem to have the condition $\sum_{jk} p_{jk}=1$. Do you have this condition here too? If so, please add it. In that case you have a transportation polytope and so the max and min of any linear function occurs at one of the (well-known) vertices of that polytope. | |
| Apr 1, 2016 at 3:43 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 7 characters in body
|
| Apr 1, 2016 at 3:37 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 221 characters in body
|
| Apr 1, 2016 at 2:01 | comment | added | Brendan McKay | An approach would be to first describe the vertices of the polytope, then if the description is simple enough we just need to select the best vertex. Without the upper bounds $p_{kl}\le 1$ it is a transportation polytope, whose vertices are well-known (the bipartite graph formed by the nonzero entries must be acyclic), but with the upper bounds in place it seems to be quite a bit more complicated. Perhaps the solution in the transportation case will provide some information? It is at least a lower bound, and is exact if the row and column sums are at most 1. | |
| Mar 31, 2016 at 16:00 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 675 characters in body
|
| Mar 31, 2016 at 15:55 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 675 characters in body
|
| Mar 31, 2016 at 6:40 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 32 characters in body
|
| Mar 30, 2016 at 20:58 | history | edited | Jerry Jiannan Lu | CC BY-SA 3.0 |
added 1 character in body; edited tags
|
| Mar 30, 2016 at 20:28 | comment | added | Stefan Kohl♦ | You might consider adding a top-level tag in order to make more people see this question. | |
| Mar 30, 2016 at 20:17 | review | First posts | |||
| Mar 30, 2016 at 20:28 | |||||
| Mar 30, 2016 at 20:14 | history | asked | Jerry Jiannan Lu | CC BY-SA 3.0 |