[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Column Generation

From: Marc Goetschalckx
Subject: Re: [Help-glpk] Column Generation
Date: Fri, 14 Mar 2014 15:28:19 -0400
User-agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0

On 12-Mar-14 12:38, Andrew Makhorin wrote:
I am trying to develop a column generation algorithm for a MIP problem
Please note that glpk mip solver does *not* support column generation.
Only rows (lazy constraints and/or cutting planes) can be added to
subproblems during the search.

  and I want to calculate the reduced costs of my variables.

I do not have access to the API but I can only call the glpsol
executable and so I thought I would  use the .dual suffix after
“--read"ing the solution of the current subproblem.

The problem is that the .dual function always returns 0, for every
structural variable.

I thought that the problem was I have a MIP problem instead of a LP
problem. So I ran glpsol with the --nomip option but the result is
still 0!

What am I doing wrong?

If your mathprog model has integer variables, it is considered as mip
independently on --nomip option. The latter affects only output from the
problem object (e.g. -o option) and doesn't affect which solution
components (lp or mip) go into the model. And since for mip solution
dual variables have no meaning, they all are set to zero.

The --nomip option states that it considers all variables as continuous variables.

Options specific to MIP solver:
   --nomip           consider all integer variables as continuous
                     (allows solving MIP as pure LP)

I assumed it solved the linear relaxation of the (mixed-)integer problem.
That is significantly different from the explanation provided above by Andrew. Dual variable values should be available at the conclusion of the solution algorithm. If that is not the case, this is a bug report since the program behavior is inconsistent with the documentation.

Help-glpk mailing list

Marc Goetschalckx

reply via email to

[Prev in Thread] Current Thread [Next in Thread]