COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 10 years ago

#203 closed enhancement (done)

faster addRow operation for LP

Reported by: Tapolcai János Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: LP interface Cc:
Revision id:

Description (last modified by Alpar Juttner)

A new function is requested in lp_base.h:

virtual int _addRow(ConstRowIterator, ConstRowIterator, Value, Value) =0;

int this case the following two function can be replaced in lp_base.h

1.

    Row addRow(Value l,const Expr &e, Value u) {
      Row r=addRow();
      row(r,l,e,u);
      return r;
    }

by

    Row addRow(Value l,const Expr &e, Value u) {
	  Row r; 
      e.simplify();
      r.id = _addRow(ConstRowIterator(e.begin(), *this),
                    ConstRowIterator(e.end(), *this),l-e.constComp(),u-e.constComp() );
      return r;
    }

2.

    Row addRow(const Constr &c) {
      Row r=addRow();
      row(r,c);
      return r;
    }

by

    Row addRow(const Constr &c) {
      Row r=addRow(c.lowerBounded()?c.lowerBound():-INF,
          c.expr(), c.upperBounded()?c.upperBound():INF);
      return r;
    }

For each solver a new int _addRow(ConstRowIterator, ConstRowIterator, Value, Value) function must be implemented (see also the attached files).

Attachments (6)

lemon_lp_mip.zip (36.6 KB) - added by Tapolcai János 11 years ago.
faster-addrow-c46afb3f67a6.patch (4.7 KB) - added by Tapolcai János 11 years ago.
71fc4fd467f2.patch (2.9 KB) - added by Alpar Juttner 11 years ago.
939d0f436ebe_lp.patch (1.5 KB) - added by Tapolcai János 11 years ago.
c8a0d6a69a47.patch (3.0 KB) - added by Alpar Juttner 11 years ago.
e4554cd6b2bf.patch (8.9 KB) - added by Balazs Dezso 10 years ago.
The patch is remaked

Download all attachments as: .zip

Change History (20)

Changed 11 years ago by Tapolcai János

Attachment: lemon_lp_mip.zip added

comment:1 Changed 11 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 11 years ago by Balazs Dezso

In my opinion, both type of base interface could be used in lp base interface:

The second type is also virtual, but it has a default implementation based on the first one. Therefore, if a simple lp interface must be implemented in short time, then the first one need to be implemented only. Otherway in order to an efficient implementation, the second one can be overrided.

comment:3 in reply to:  description Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

Replying to jtapolcai:

Could you please create a patch from this changes? You can find some hints here on how to do that.

You might also want to take deba's comment into account.

Changed 11 years ago by Tapolcai János

comment:4 Changed 11 years ago by Tapolcai János

I have added a ticket, but the lp_test fails (mip_test passed).

comment:5 in reply to:  4 Changed 11 years ago by Alpar Juttner

Replying to jtapolcai:

I have added a ticket, but the lp_test fails (mip_test passed).

Thanks for the patch. Some comments

  • It seems that you started to edit and older version of lp_base.h then you copied it into the latest version [c46afb3f67a6]. The result is that your patch reverts some important changes such as [fb5af0411793] and [81627fa1b007]. It is not a problem if your patch is not against the very latest version but you should always be careful not to copy a file between different revisions.
  • [c46afb3f67a6] in not the hash id of your changesets but its parent's. Yours is [a7b59195961a].
  • The newly implemented _addRow(i1,i2) function is not used by any solver backend.

comment:6 in reply to:  4 ; Changed 11 years ago by Alpar Juttner

Replying to jtapolcai:

I have added a ticket, but the lp_test fails (mip_test passed).

I had another look into your patch, and now I can confirm that the problem is indeed that you reverted some essential bugfixes. It is always advisable the have a look into the patch file (or into the output of hg diff before the commit) to see the actual changes. Moreover, with hg kdiff lemon/lp_base.h you are able to see your changes in a GUI and you can also revert your changes one by one.

I also noticed a strange warning with gcc-4.3.2.

In file included from test/lp_test.cc:29:
./lemon/lp_base.h:944: warning: 'virtual int lemon::LpBase::_addRow(lemon::LpBase::ExprIterator, lemon::LpBase::ExprIterator)' was hidden
./lemon/glpk.h:55: warning:   by 'virtual int lemon::GlpkBase::_addRow()'

Could anyone tell me if this warning is valid and how to avoid it?

Changed 11 years ago by Alpar Juttner

Attachment: 71fc4fd467f2.patch added

comment:7 in reply to:  6 Changed 11 years ago by Alpar Juttner

Replying to alpar:

Replying to jtapolcai:

I have added a ticket, but the lp_test fails (mip_test passed).

I had another look into your patch, and now I can confirm that the problem is indeed that you reverted some essential bugfixes.

Hmmm. I'm completely confused now.

I made clean version [71fc4fd467f2] of the patch by removing the faulty changes, see in the attachment. However lp_test crashes with this version.

Changed 11 years ago by Tapolcai János

Attachment: 939d0f436ebe_lp.patch added

comment:8 Changed 11 years ago by Tapolcai János

The previous attachment 939d0f436ebe_lp.patch contains a bugfix of the _addRow operation. This time the lp_test succeeds. There was two bugs: (1) the SkeletonSolverBase::_addRow(ExprIterator?, ExprIterator?) must return a valid row id. (2) the new row id must be stored in the rows vector by calling function _addRowId().

Changed 11 years ago by Alpar Juttner

Attachment: c8a0d6a69a47.patch added

comment:9 Changed 11 years ago by Alpar Juttner

The attached chgset [c8a0d6a69a47] is a reapplied version of the changes here to the tip plus two using directives are added.

Alas, make check still fails on it.

comment:10 Changed 11 years ago by Balazs Dezso

Status: newassigned

comment:11 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.1 releaseLEMON 1.2 release

comment:12 in reply to:  11 ; Changed 10 years ago by Alpar Juttner

Does anyone feel temptation for working on this in the near future (i.e. before the release of LEMON 1.2)?

Changed 10 years ago by Balazs Dezso

Attachment: e4554cd6b2bf.patch added

The patch is remaked

comment:13 in reply to:  12 Changed 10 years ago by Balazs Dezso

Replying to alpar:

Does anyone feel temptation for working on this in the near future (i.e. before the release of LEMON 1.2)?

I have uploaded the patch [e4554cd6b2bf]. I remade the new feature, because I did not want to check and rebase all the original patches.

comment:14 Changed 10 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed
Type: defectenhancement

[e4554cd6b2bf] is now in the main branch.

Note: See TracTickets for help on using tickets.