Saya memiliki masalah pemrograman bilangan bulat campuran. Dan saya saat ini menggunakan GLPK sebagai solver saya. Tetapi saya menemukan bahwa GLPK baik untuk masalah Pemrograman Linier, tetapi untuk pemrograman Mixed Integer, membutuhkan waktu yang lebih lama, oleh karena itu tidak memenuhi persyaratan kami. Saya sangat mencari perangkat lunak lain. Apakah ada alat open source lain yang bagus untuk menyelesaikan masalah pemrograman integer campuran dengan kecepatan cepat? Terima kasih!
14
Jawaban:
If you want something open-source, you probably want to try COIN's CBC code (they also have a couple other MILP solvers, like a branch-and-price framework, or SYMPHONY).
Gurobi and CPLEX will be considerably faster, and as of the 2011 or 2012 INFORMS meeting, Gurobi was faster than CPLEX (though the performance metrics are of course problem dependent). On the MILPs solved in my thesis, Gurobi was approximately 15-100 times faster than CBC, and CPLEX was almost as fast as Gurobi, but very slightly slower (like 12-80 times faster).
Although the worst-case performance is indeed exponential, the execution time will depend heavily on problem structure. It's unlikely that you'll be able to solve an MILP with millions of variables unless you exploit special structure (maybe if it's a stochastic program that can be decomposed into many much smaller problems), but it's entirely possible to solve nontrivial MILPs with thousands of variables in under a minute. (Of course, it's also possible for these problems to take an hour or more to solve.)
As Brian Borchers notes, CPLEX and Gurobi both have free licenses available for some researchers, one of these two software packages would really be the best to use as a general-purpose MILP solver.
sumber
Masalah linear integer programming lebih sulit untuk dipecahkan daripada masalah linear programming. Dalam hal kompleksitas komputasi, LP dapat diselesaikan dalam waktu polinomial sementara memecahkan MILP adalah masalah NP-Hard. Algoritma yang dikenal untuk memecahkan MILP memiliki kompleksitas kasus terburuk yang eksponensial.
There are other software packages for mixed integer linear programming that you could look at, including SCIP (free for academic use), CPLEX (commercial but has an academic licensing option) and GUROBI (also commercial with an academic licensing option.) One or more of these packages might be substantially faster than GLPK on your problems, but don't expect any of them to be nearly as fast at solving MILP as they are in solving similarly sized LP's.
sumber
If you want to try a bunch of different solvers, give Julia's JuMP modeling framework a try. It lets you write your model as a JuMP model, and then switch out the solvers with one line of code. For example, for MILP problems you can choose from the Bonmin, Cbc, Couenne, CPLEX, GLPK, Gurobi, and MOSEK solvers. Because of this, if you write it in JuMP, you can just try all the solvers that Geoff mentioned and see what works without having to write a bunch of code. Your own personal tests will be the best source of knowledge for what the fastest algorithms are for your problems.
sumber
@code_llvmto check the resulting assembly code to see that the glue code is essentially nothing (this is also because Julia naively uses function pointers and the same bit arrays as C/Fortran).Mengikuti saran orang lain, saya telah menggunakan (komersial) GAMS for many projects. It is very straight forward; all you have to do is to put the mathematic formulation of your problem. It picks up the variables, constraints, objective functions and all the input data. Then, it provides a range of solvers (optimisers) for any case. Depending on your case, you add more sophisticated solvers.
Pastinya MUDAH is worth a look. Open-source framework.
Istilah "cepat" sangat kabur! Kamu perlu lebih spesifik; Cepat dalam hal jumlah iterasi? jumlah evaluasi? waktu berlalu? kombinasi ini?
Namun, jika Anda tidak mencari perangkat lunak, dan Anda hanya ingin menyelesaikan masalah, saya dapat menyarankan untuk menggunakan pengoptimal global NSGA-II, yang merupakan pengoptimalisasi sumber terbuka dengan reputasi dan kinerja yang sangat tinggi.
Jika Anda memberikan informasi lebih lanjut, saya dapat memandu dengan tepat.
sumber