Re: [Help-glpk] Binary integer programming

[John LaRusic]

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-glpk






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're going through the expense of branching anyways, it might make more sense to look to tree search to solve your problem.  Patrick Prosser'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'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'm pretty new to this list, so hi everyone!  I'm completing a MSc in Mathematics and looking to join the GLPK development effort after I graduate.  For now, I'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-glpk