|
From: | John LaRusic |
Subject: | Re: [Help-glpk] Binary integer programming |
Date: | Tue, 21 Jul 2009 23:28:27 +0300 |
Hi George, Generally, LP/IP programming only concerns itself with finding a single optimal solution, particularly in the case of integer programs where finding even a single optimal solution could be very expensive (for example, a traveling salesman problem solution). Further, I *think* its possible that an IP technique could overlook integer optimal solutions. Assuming the feasible region is convex, if x and y are two integer optimal solutions then any integer on the line between x and y is also optimal. However, an IP will probably find only the integer solutions at vertices of the convex hull (someone smarter than me would have to confirm this :-). Since with IP programming you #39;re going through the expense of branching anyways, it might make more sense to look to tree search to solve your problem. Patrick Prosser #39;s "Hybrid Algorithms for the Constraint Satisfaction Problem" is a good introduction to some simple but effective tree search strategies. Of course, no matter what you do you #39;re looking at a very expensive search for every optimal solution (you might have exponentially many optimal solutions, no?). You might want to question if you really need every optimal solution. Cheers, John LaRusic p.s. I #39;m pretty new to this list, so hi everyone! I #39;m completing a MSc in Mathematics and looking to join the GLPK development effort after I graduate. For now, I #39;m just mostly lurking. On Tue, Jul 21, 2009 at 3:16 AM, George Athanasiou <address@hidden> wrote: Hello, I’m trying to solve a binary integer programming problem. I’m using matlab (bintprog function) and the problem is that I get a single optimal solution (with brunch techniques). I know that my problem has more than one solutions (with equal cost). Is there any way to get complete set of solutions with GLPK? Thank you, George Athanasiou George Athanasiou Ph.D. Candidate University of Thessaly Department of Computer and Communications Engineering Centre for Research and Technology Hellas Glavani 37 28 Oktovriou 38221, Volos, Greece Tel: +30 24210 74553 Fax: +30 24210 74668 e-mail:address@hidden web page: http://www.inf.uth.gr/~gathanas _______________________________________________ Help-glpk mailing list address@hidden http://lists.gnu.org/mailman/listinfo/help-glpkHi George,
Hello,
Im trying to solve a binary integer programming problem. Im using matlab (bintprog function) and the problem is that I get a single optimal solution (with brunch techniques). I know that my problem has more than one solutions (with equal cost). Is there any way to get complete set of solutions with GLPK?
Thank you,
George Athanasiou
George Athanasiou
Ph.D. Candidate
University of Thessaly
Department of Computer and Communications Engineering
Centre for Research and Technology Hellas
Glavani 37 & 28 Oktovriou
38221, Volos, Greece
Tel: +30 24210 74553
Fax: +30 24210 74668
e-mail: address@hidden
web page: http://www.inf.uth.gr/~gathanas
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
[Prev in Thread] | Current Thread | [Next in Thread] |