faster addRow operation for LP

[Tapolcai János]

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​).

[Balazs Dezso]

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

• _addRow() pure virtual function
• _adRow(RowIterator?, RowIterator?, Value, Value)

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.

[Alpar Juttner]

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.

[Tapolcai János]

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

[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.

[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?

[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.

[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().

[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.

[Alpar Juttner]

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

[Balazs Dezso]

The patch is remaked

[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.

[Alpar Juttner]

[e4554cd6b2bf] is now in the main branch.