Re: [Help-glpk] lp/mip preprocessor api

[Andrew Makhorin]

> This is true, however after step L4 in your suggested API:
> Q = glp_npp_build_prob(npp, ...);
> any subsequent modifications to Q are not reflected in the PP
> workspace. My suggestion is to allow calling glp_npp_load_prob() with
> this modified Q (with changed bounds or added rows) to update the
> workspace before further preprocessing passes. 

There is no need (and technically it'd be difficult) to load Q back into
the PP wksp. It would be sufficient to provide some specific
preprocessor routines that allows, for example, fixing a column or add a
row to the current instance residing in the workspace.





___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] lp/mip preprocessor api

[Chris Matrakidis]

Hi Andrew,


> Sorry, I don't catch your idea. The resulting (preprocessed) problem
> always resides in the PP workspace, so one can preprocess it in several
> passes, if necessary.
>

This is true, however after step L4 in your suggested API:
Q = glp_npp_build_prob(npp, ...);
any subsequent modifications to Q are not reflected in the PP workspace. My
suggestion is to allow calling glp_npp_load_prob() with this modified Q
(with changed bounds or added rows) to update the workspace before further
preprocessing passes.

In a way this takes your suggestion to Heinrich, to "...first preprocess
your instance with glpk pp and then preprocess the resulting instance with
your own preprocessor" one step further, in that it allows to rerun the
glpk preprocessor again using the same workspace.

I have used this procedure myself in:
a) a loop that fixes columns of the proproecessed problem using probing
until no further changes are possible; and
b) for additional preprocessing after adding symmetry breaking inequalities
to the preprocessed problem.

Best Regards,

Chris Matrakidis
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] lp/mip preprocessor api

[Andrew Makhorin]

Hi Chris,


> Here is my suggestion, together with a patch to implement it: 
> 
> 
> I think it is useful to be able to perform step L2 more than once,
> i.e. to be able to call glp_npp_load_prob() after modifying the
> problem returned from glp_npp_build_prob() in order to update the PP
> workspace and continue preprocessing.
> 
> 
> The attached patch modifies glp_npp_load_prob() to allow this.
> 

Sorry, I don't catch your idea. The resulting (preprocessed) problem
always resides in the PP workspace, so one can preprocess it in several
passes, if necessary.


Andrew Makhorin




___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] lp/mip preprocessor api

[Andrew Makhorin]

> >> the API should allow the user to add his own simplifications.
> >>
> >> This may require access to the npp internal structure.
> > 
> > It would be problematic. I only plan to include a set of preprocessing
> > operations sufficient in most cases (at least for LP). On the other
> > hand, if the user needs to perform his own preprocessing, why not to do
> > that independently on the glpk preprocessor?
> 
> You have already implemented a lot of useful presolving and scaling
> routines.
> 
> If I wanted to build on it and simply add another one I would not like
> to reimplement your work.

You may first preprocess your instance with glpk pp and then preprocess
the resulting instance with your own preprocessor.

> 
> > 
> >>
> >> It would be great if the variable mapping could be applied forward and
> >> reverse in the MIP callback hook.
> > 
> > Could you provide an example of what you mean?
> 
> In the MIP callback currently we can only access the scaled and
> presolved model.
> 
> If we could apply the backwards transformation we would be able to
> understand the solution in our original variables.

This feature is already implemented (and even available in glpsol), i.e.
it will be possible to recover the solution to the original mip within
the callback.

> 
> If we could apply the forward transformation we would be able to create
> a constraint in our own variables and than add the transformed
> constraint to the scaled and presolved model.
> 

Currently the preprocessor is unable to do this. May be to implement
such a feature later.


Andrew Makhorin


___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] lp/mip preprocessor api

[Heinrich Schuchardt]

On 12/02/2017 05:54 PM, Andrew Makhorin wrote:
> Hi Heinrich,
> 
>>
>> the API should allow the user to add his own simplifications.
>>
>> This may require access to the npp internal structure.
> 
> It would be problematic. I only plan to include a set of preprocessing
> operations sufficient in most cases (at least for LP). On the other
> hand, if the user needs to perform his own preprocessing, why not to do
> that independently on the glpk preprocessor?

You have already implemented a lot of useful presolving and scaling
routines.

If I wanted to build on it and simply add another one I would not like
to reimplement your work.

> 
>>
>> It would be great if the variable mapping could be applied forward and
>> reverse in the MIP callback hook.
> 
> Could you provide an example of what you mean?

In the MIP callback currently we can only access the scaled and
presolved model.

If we could apply the backwards transformation we would be able to
understand the solution in our original variables.

If we could apply the forward transformation we would be able to create
a constraint in our own variables and than add the transformed
constraint to the scaled and presolved model.

Best regards

Heinrich

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] lp/mip preprocessor api

[Andrew Makhorin]

Hi Heinrich,

> 
> the API should allow the user to add his own simplifications.
> 
> This may require access to the npp internal structure.

It would be problematic. I only plan to include a set of preprocessing
operations sufficient in most cases (at least for LP). On the other
hand, if the user needs to perform his own preprocessing, why not to do
that independently on the glpk preprocessor?

> 
> It would be great if the variable mapping could be applied forward and
> reverse in the MIP callback hook.

Could you provide an example of what you mean?


Best regards,

Andrew Makhorin


___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] lp/mip preprocessor api

[Andrew Makhorin]

Currently the LP/MIP preprocessor is used internally by glp_simplex,
glp_interior, and glp_intopt. However, I think it would be reasonable
to make the LP/MIP preprocessor available to the user on API level.
Please see below the API routines I plan to include in the package.

Any comments/suggestions are appreciated.

Thank you,

Andrew Makhorin

--
A crude scheme of using the preprocessor routines on API level is the
following.

L1:   /* allocate preprocessor (PP) workspace */
  npp = glp_npp_alloc_wksp(...);

L2:   /* load original problem instance into PP workspace */
  glp_npp_load_prob(npp, P, ...);

L3:   /* perform preprocessing */
  call one or more specific preprocessor routines;

L4:   /* obtain resulting problem instance */
  Q = glp_npp_build_prob(npp, ...);

L5:   /* solve resulting problem instance */
  glp_simplex / glp_interior / glp_intopt (Q, ...);

L6:   /* load solution to resulting problem instance into PP wksp */
  glp_npp_load_sol(npp, Q, ...);

L7:   /* obtain solution to original problem instance from PP wksp */
  glp_npp_recover_sol(npp, P, ...);

L8:   /* free PP workspace */
  glp_npp_free_wksp(npp);

Steps L1, L2, and L8 are performed only once. Steps L3, ..., L7 can be
performed many times, if necessary.



___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

[Help-glpk] glpk 4.64 release information

[Andrew Makhorin]

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

GLPK 4.64 Release Information
*

Release date: December 02, 2017

GLPK (GNU Linear Programming Kit) is intended for solving large-scale
linear programming (LP), mixed integer linear programming (MIP), and
other related problems. It is a set of routines written in ANSI C89 and
organized as a callable library.

In this release:

The dual simplex solver routine was changed to perform more
aggressive perturbation to prevent dual degeneracy and avoid
stalling even if the current dual basic solution is strongly
feasible (mainly if the objective is zero). Thanks to David
Monniaux  for bug report
and example model.

The exact simplex solver routine was changed to perform
terminal output according to the verbosity level (specified by
the control parameter smcp.msg_lev). Thanks to Jeroen Demeyer
 for bug report.

A minor bug (related to MS Windows version) was fixed. Thanks
to Heinrich Schuchardt  for bug report.

An example model (Graceful Tree Labeling Problem) in MathProg
was added. Thanks to Mike Appleby  for
contribution.

Three example models (Power plant LP scheduler, Neumann CA
grid emulator generator) in MathProg and one in Cplex LP format
were added. Thanks to Peter Naszvadi  for
contribution.

See GLPK web page at .

GLPK distribution can be ftp'ed from  or
from some mirror ftp sites; see .

MD5 check-sum is the following:

71a99d744589570f3ee98a566f27ea49 *glpk-4.64.tar.gz

GLPK is also available as a Debian GNU/Linux package. See its web page
at .

Precompiled GLPK binaries (lib, dll, exe) for 32- and 64-bit MS Windows
can be downloaded from .
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.2.1 (MingW32)

iD8DBQFaInhL0XvyMFmB6BgRAojLAKCdZa7PY/GdgrdFj5vpgZHWVc+SfwCeJI8B
V9YNFO6KWARbM3WXpmD4bpQ=
=TfUH
-END PGP SIGNATURE-



___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk