Thread Subject: bintprog, more than one optimal

Hello, I'm using bintprog() to solve an integer programming optimization problem and the problem that i have is that I'm expecting several optimal solutions but bintprog() returns just one. I can prove by hand that there are more than one solution for my example. Could you help me with this? Is there any way to get the set of all solutions?

George,

bintprog returns only one solution - as soon as it finds one solution it will stop searching.

-Marcelo

George Athanasiou wrote:
> Hello, I'm using bintprog() to solve an integer programming optimization problem and the problem that i have is that I'm expecting
> several optimal solutions but bintprog() returns just one. I can prove by hand that there are more than one solution for my example.
>Could you help me with this? Is there any way to get the set of all solutions?

"George Athanasiou" <geo.athanasiou@gmail.com> wrote in message <h1quqm$fp0$1@fred.mathworks.com>...
> Hello, I'm using bintprog() to solve an integer programming optimization problem and the problem that i have is that I'm expecting several optimal solutions but bintprog() returns just one. I can prove by hand that there are more than one solution for my example. Could you help me with this? Is there any way to get the set of all solutions?

Without the inequality optimal solutions of bintprog is a solution of system of linear diophantine equations. Such system can be solved through the so called "Smith normal form" of the matrix, some sort of integer arithmethic Gaussian elimination (opearated in the "field" - without division - using GCD). This call for large integer operations, and better implemented in infinity integer arithmetic (such as symbolic toolbox). Just Google, you can find plenty of algorithm described somewhere else.

A single diophantine equation is discussed here: http://www.mathworks.com/matlabcentral/newsreader/view_thread/172882

In any case, there might be infinity number of solutions. List them all is impossible. Better way is code them by Smith normal form (two permutations matrix + diagonal matrix), and extract the solution(s) when they are needed later.

Bruno