Binray Variables - non-integer solution

Archiver · February 22, 2012, 10:07am

Hey guys,

I want to solve a (mixed) interger problem by a column generating
method in GAMS. The masterproblem (lp-relaxation) should be solved by
an mrip-solver. The variables of the master problem are defined as
binary variables.

When I tested it for small instances everything went well. But for
larger examples the solution contains non-integer values like 0.5 or
0.125.

Has anybody an idea what’s the reason? Hope to get a response.

\

Archiver · February 22, 2012, 12:26pm

Getting a solution with discrete variables having integer values when using rmip is more of an exception than a rule. I am not familiar with the column generating thing but i guess solving the problem using mip instead of rmip might do the trick.
Regards, Milos
On Feb 22, 2012 10:10 AM, “kripuhh” wrote:

Hey guys,

I want to solve a (mixed) interger problem by a column generating
method in GAMS. The masterproblem (lp-relaxation) should be solved by
an mrip-solver. The variables of the master problem are defined as
binary variables.

When I tested it for small instances everything went well. But for
larger examples the solution contains non-integer values like 0.5 or
0.125.

Has anybody an idea what’s the reason? Hope to get a response.

–
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Archiver · February 22, 2012, 2:08pm

column generation is for solving lp problems (for example the lp
relaxation of a mip problem). if you want an integer solution you
could add a rounding heuristic that fixes variables to integer values
at some point of the procedure. another option is the more complicated
branch and price.

On 22 Feb., 10:07, kripuhh wrote:

Hey guys,

I want to solve a (mixed) interger problem by a column generating
method in GAMS. The masterproblem (lp-relaxation) should be solved by
an mrip-solver. The variables of the master problem are defined as
binary variables.

When I tested it for small instances everything went well. But for
larger examples the solution contains non-integer values like 0.5 or
0.125.

Has anybody an idea what’s the reason? Hope to get a response.

\

Archiver · February 22, 2012, 8:30pm

Thanks for your quick response!

It is very helpful.

2012/2/22 Matthes

column generation is for solving lp problems (for example the lp
relaxation of a mip problem). if you want an integer solution you
could add a rounding heuristic that fixes variables to integer values
at some point of the procedure. another option is the more complicated
branch and price.

On 22 Feb., 10:07, kripuhh wrote:

Hey guys,

I want to solve a (mixed) interger problem by a column generating
method in GAMS. The masterproblem (lp-relaxation) should be solved by
an mrip-solver. The variables of the master problem are defined as
binary variables.

When I tested it for small instances everything went well. But for
larger examples the solution contains non-integer values like 0.5 or
0.125.

Has anybody an idea what’s the reason? Hope to get a response.

–
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

\

To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Archiver · February 23, 2012, 4:53pm

Dear Kristine,

Another alternative is to solve a mip problem with all the columns
from the Column Generation algorithm. It will return a feasible
solution for your original problem.

regards,
Luiz Carlos.

On 2/22/12, Kristine Puritz wrote:

Thanks for your quick response!

It is very helpful.

2012/2/22 Matthes

column generation is for solving lp problems (for example the lp
relaxation of a mip problem). if you want an integer solution you
could add a rounding heuristic that fixes variables to integer values
at some point of the procedure. another option is the more complicated
branch and price.

On 22 Feb., 10:07, kripuhh wrote:

Hey guys,

I want to solve a (mixed) interger problem by a column generating
method in GAMS. The masterproblem (lp-relaxation) should be solved by
an mrip-solver. The variables of the master problem are defined as
binary variables.

When I tested it for small instances everything went well. But for
larger examples the solution contains non-integer values like 0.5 or
0.125.

Has anybody an idea what’s the reason? Hope to get a response.

–
“gamsworld” group.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to
gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/gamsworld?hl=en.

–
“gamsworld” group.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to
gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/gamsworld?hl=en.

\

Archiver · February 23, 2012, 9:43pm

Thank you, Luiz.
Thats excatly, what I do. But there’s no guaranty that the solution is optimal.
I was wondering if there is a way to get the optimal solution of the mip without implementing a whole branch-and-price algorithm.
Am 23.02.2012 16:53 schrieb “Luiz Carlos Sousa” :