3 ms·

Mixed Integer programming IS a multi-constraint optimization NP hard problem. Use Gurobi.

graycat 12y ago
Yes, but I took my parent's "NP" to abbreviate non-linear programming and not non-deterministic polynomial.
graycat 12y ago
Thanks for mentioning Gurobi. I just looked them up! So, they are headed up by Bixby! Terrific! After IBM bought ILOG and C-PLEX, I assumed that Bixby would retire. Apparently, nope! Also Bixby has two students from Georgia Tech so, likely from George Nemhauser and Ellis Johnson. George is the person who explained 0-1 integer linear set covering to me. That same day he gave me three words of advice that became the direction for my Ph.D. dissertation (in stochastic optimal control) at Johns Hopkins. I knew Ellis when we were both at IBM's Watson lab. Gurobi looks good.
- tlarkworthy 12y ago
  Yeah, it is very good. You can solve problems incrementally. Change a few params, add a few more constraints, and rerun using the previous result.
  - graycat 12y ago
    What you mentioned looks like something quite common for linear programming software. E.g., think linear programming tableaux and appending a new constraint with its own, new artificial variable. Then do elementary row operations to zero out the row of the new constraint in the columns of the old basic variables. Then do elementary row operations to zero out the new artificial column in all rows except the row of the new constraint. Then do simplex algorithm pivots to get the new artificial variable out of the basis. Changing costs is also easy and standard in convenient little operations called post-optimality. There are more details, but covering all of those would need much of a course in linear programming. E.g., the IBM Optimization Subroutine Library (OSL) is quite nice work, likely heavily from Ellis Johnson when he was still at IBM before he went to Georgia Tech where George Nemhauser has long been and does what you mentioned. Once I wrote some 0-1 integer linear programming software with some Lagrangian relaxation based on the OSL -- it was nice. From Bixby, the guy that did C-PLEX, and two Georgia Tech students, etc., I would expect more than the usual or just the OSL! I'd guess that they have some good results in integer programming, numerical stability, much larger problems, exploitation of multi-core processors, and more.
- areyousure 12y ago
  Out of curiosity, what were the three words? (Presumably not "stochastic optimal control"..)
  - graycat 12y ago
    Ah, I likely shouldn't betray that confidence!

Yes, but I took my parent's "NP" to abbreviate non-linear programming and not non-deterministic polynomial.

Thanks for mentioning Gurobi. I just looked them up! So, they are headed up by Bixby! Terrific! After IBM bought ILOG and C-PLEX, I assumed that Bixby would retire. Apparently, nope! Also Bixby has two students from Georgia Tech so, likely from George Nemhauser and Ellis Johnson. George is the person who explained 0-1 integer linear set covering to me. That same day he gave me three words of advice that became the direction for my Ph.D. dissertation (in stochastic optimal control) at Johns Hopkins. I knew Ellis when we were both at IBM's Watson lab. Gurobi looks good.

tlarkworthy 12y ago
Yeah, it is very good. You can solve problems incrementally. Change a few params, add a few more constraints, and rerun using the previous result.
- graycat 12y ago
  What you mentioned looks like something quite common for linear programming software. E.g., think linear programming tableaux and appending a new constraint with its own, new artificial variable. Then do elementary row operations to zero out the row of the new constraint in the columns of the old basic variables. Then do elementary row operations to zero out the new artificial column in all rows except the row of the new constraint. Then do simplex algorithm pivots to get the new artificial variable out of the basis. Changing costs is also easy and standard in convenient little operations called post-optimality. There are more details, but covering all of those would need much of a course in linear programming. E.g., the IBM Optimization Subroutine Library (OSL) is quite nice work, likely heavily from Ellis Johnson when he was still at IBM before he went to Georgia Tech where George Nemhauser has long been and does what you mentioned. Once I wrote some 0-1 integer linear programming software with some Lagrangian relaxation based on the OSL -- it was nice. From Bixby, the guy that did C-PLEX, and two Georgia Tech students, etc., I would expect more than the usual or just the OSL! I'd guess that they have some good results in integer programming, numerical stability, much larger problems, exploitation of multi-core processors, and more.
areyousure 12y ago
Out of curiosity, what were the three words? (Presumably not "stochastic optimal control"..)
- graycat 12y ago
  Ah, I likely shouldn't betray that confidence!