help-glpk
[Top][All Lists]

## Re: [Help-glpk] Binary integer programming

 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

web
page: http://www.inf.uth.gr/~gathanas

_______________________________________________
Help-glpk mailing list
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 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

web page: http://www.inf.uth.gr/~gathanas _______________________________________________
Help-glpk mailing list