MipSolver interface fixes and extension

[Peter Kovacs]

In MipSolver there are type(), sol() and solValue() functions to obtain the (primal) solution.

1. There are two inconsistent names here:
   • solValue() should be renamed to sol() (as on overloaded version) as primalValue() was renamed to primal() in LpSolver.
   • ColTypes should be renamed to ColType, since we do not use plural in similar names.

2. Apart form that, I suggest an extension. Let's introduce primalType() and primal() as an alias for the above functions. Adding these variants, one can change to using a Mip solver instead of an Lp solver without rewriting the code (if only primal queries were used).

3. Maybe type(), sol() could also be added to LpSolver as an alias for the primal queries.

[Peter Kovacs]

Replying to kpeter:

• solValue() should be renamed to sol() (as on overloaded version) as primalValue() was renamed to primal() in LpSolver.

Of course, solValue() should be kept for compatibility. So what about adding primalValue() to LpSolver to be consistent?

• ColTypes should be renamed to ColType, since we do not use plural in similar names.

Could we do anything with this? E.g. rename to ColType and keep an obsolete typedef ColTypes?

2. Apart form that, I suggest an extension. Let's introduce primalType() and primal() as an alias for the above functions. Adding these variants, one can change to using a Mip solver instead of an Lp solver without rewriting the code (if only primal queries were used).

3. Maybe type(), sol() could also be added to LpSolver as an alias for the primal queries.

What do you think about these ideas?

[Alpar Juttner]

Replying to kpeter:

What do you think about these ideas?

I second them all.

[Peter Kovacs]

The attached patch [d4c3ba9ac811] makes the following modifications:

• Add sol() (without parameters) to MipSolver as an alias for solValue(), since we have primal() instead of primalValue() in LpSolver.
• Add primal() (3 overloaded variants) and primalValue() to MipSolver as aliases for sol() and solValue().
• Rename ColTypes to ColType in MipSolver and keep the old name as an obsolete typedef.
• Add primalValue() to LpSolver as an alias for primal() (without parameters).
• Doc improvements + unifications.

[Peter Kovacs]

The patch could be merged into both branches.

Could you please review it? In general, we don't prefer aliases, but in this case, it could worth to have some. Using this patch, however, MipSolver would have 4 functions for the same operation, namely obtaining the solution value: sol(), solValue(), primal(), primalValue(). (Currently LpSolver has only primal() and MipSolver has only solValue() for this purpose.)

Do we need/like all these aliases? Do you have better unification concept? As I remember, Balazs suggested to have sol*() function aliases in LpSolver instead of primal*() variants in MipSolver. Would it be better?

[Alpar Juttner]

Ops. Now, I got very confused.

I can't find the interface for obtaining the nonzero elements of the solution (as an Expr) neither in MipSolver nor in LpSolver. Moreover, I can't see much use of the current Value sol/primal(Expr &e) variant.

Something tells me that - in the original concept - primal() and/or primal(Expr &e) was intended to return the whole solution (as an Expr), while primalValue() was for obtaining the value of a solution. This naming convention sounds logical for me.

[Alpar Juttner]

Replying to alpar:

In other words, primal(...) is for obtaining x, while primalValue() is for obtaining cx.

[Peter Kovacs]

Replying to alpar:

Ops. Now, I got very confused.

You are not alone. :)

I can't find the interface for obtaining the nonzero elements of the solution (as an Expr) neither in MipSolver nor in LpSolver.

Did we ever have such function? Why is it important?

As far as I understand, an Expr object describes a linear combination of the columns, i.e. ax for some coefficient vector a. Why is it useful to obtain an expression that is the sum of all non-zero valued variable?

Moreover, I can't see much use of the current Value sol/primal(Expr &e) variant.

It calculates the current value of any primal expression. I find it useful.

Something tells me that - in the original concept - primal() and/or primal(Expr &e) was intended to return the whole solution (as an Expr),

It would be really strange for me. As far as I see, the solution is an actual assignment of values to the variables (columns) and every expression has a concrete value with respect to any solution. So, once we have a solution, we could calculate the value of an Expr, which is done using the above sol(const Expr&) function.

while primalValue() was for obtaining the value of a solution. This naming convention sounds logical for me.

I think, the solution cannot be obtained at once, only by querying the value of each column.

Or I'm completely wrong?

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Ops. Now, I got very confused.

You are not alone. :)

I can't find the interface for obtaining the nonzero elements of the solution (as an Expr) neither in MipSolver nor in LpSolver.

Did we ever have such function? Why is it important?

Because in many cases the solution contains only a small number of nonzero elements and we need only those. The best solution would be to keep track of the elements on the lower/upper bounds and in the middle and make it possible to list them separately. Alas, Expr is not capable of doing that.

As far as I understand, an Expr object describes a linear combination of the columns, i.e. ax for some coefficient vector a.

Not really. Expr is a set of column-value pairs or a column->value mapping where a the non-zero values are not listed. (Plus an additional constant but it is irrelevant here)

I agree that it may be strange at first to use the "coefficients" to store the values of the solution, but the objective function, the constraints and also the soultion are all just vectors of the same size, thus it is quite natural to use the same data structure for describing them.

Why is it useful to obtain an expression that is the sum of all non-zero valued variable?

Why do you talk about of the sum of the values? I've never done so.

Moreover, I can't see much use of the current Value sol/primal(Expr &e) variant.

It calculates the current value of any primal expression. I find it useful.

This is kind of statement if quite hard to argue with. I still can't see much use of it. If you know a good example, let me know, please.

Something tells me that - in the original concept - primal() and/or primal(Expr &e) was intended to return the whole solution (as an Expr),

It would be really strange for me. As far as I see, the solution is an actual assignment of values to the variables (columns)

Yes, and so does the Expr.

and every expression has a concrete value with respect to any solution. So, once we have a solution, we could calculate the value of an Expr, which is done using the above sol(const Expr&) function.

I understand, you are talking about the multiplication of two vectors. So what?

I think, the solution cannot be obtained at once, only by querying the value of each column.

It may be obtained more efficiently in some cases. If using the x>=0 form, everything not in the basis is zero.

Or I'm completely wrong?

Clearly, the best would be to have a dedicated data structure for describing a solution. What I proposed is a simpler but easier-to-implement substitute for that.

[Peter Kovacs]

Now, I understand your suggestion.

Replying to alpar:

Did we ever have such function? Why is it important?

Because in many cases the solution contains only a small number of nonzero elements and we need only those. The best solution would be to keep track of the elements on the lower/upper bounds and in the middle and make it possible to list them separately. Alas, Expr is not capable of doing that.

I see.

As far as I understand, an Expr object describes a linear combination of the columns, i.e. ax for some coefficient vector a.

Not really. Expr is a set of column-value pairs or a column->value mapping where a the non-zero values are not listed.

Here is the major difference. You talked about the implementation, I talked about the purpose for which the class was introduced and for which its name and the name of all its members are designed: linear expression of variables (columns) and a constant component.

(Plus an additional constant but it is irrelevant here)

It could be used to store the value of the objective function, couldn't it? If this whole idea would not already be confused enough. :)

I agree that it may be strange at first to use the "coefficients" to store the values of the solution, but the objective function, the constraints and also the soultion are all just vectors of the same size, thus it is quite natural to use the same data structure for describing them.

I agree, it would be strange. Basically, the two purposes could be implemented the same way, however, lot of feaures of Expr is unnecessary for a Solution class, and the functions of the latter one should have other names (e.g. value instead of coefficient). That's why I would prefer separate classes (e.g. PrimalSolution and DualSolution) for the purposes you request, although they could be implemented using Expr and DualExpr.

Why is it useful to obtain an expression that is the sum of all non-zero valued variable?

Why do you talk about of the sum of the values? I've never done so.

You haven't talked about the coefficients (just about the nonzero elements of the solution), thus I thought them to be set to one. Now I understand that you propose an expression whose current value (calculated with the primal() or sol() function) would not be the sum of the values of the variables, but the sum of the squares of the values. :)

It calculates the current value of any primal expression. I find it useful.

This is kind of statement if quite hard to argue with. I still can't see much use of it. If you know a good example, let me know, please.

I don't have much experience in working with LPs in practice. However, I could imagine such situations. E.g. you have several objective functions. You solve the LP using one of them and then calculate the current value of the others. After that, you may do the same, selecting another one of the functions. Isn't it realistic?

Something tells me that - in the original concept - primal() and/or primal(Expr &e) was intended to return the whole solution (as an Expr),

It would be really strange for me. As far as I see, the solution is an actual assignment of values to the variables (columns)

Yes, and so does the Expr.

Logically, it is a linear expression, not a solution.

and every expression has a concrete value with respect to any solution. So, once we have a solution, we could calculate the value of an Expr, which is done using the above sol(const Expr&) function.

I understand, you are talking about the multiplication of two vectors. So what?

I think, the solution cannot be obtained at once, only by querying the value of each column.

It may be obtained more efficiently in some cases. If using the x>=0 form, everything not in the basis is zero.

I meant that you cannot do it using the _current_ interface.

Or I'm completely wrong?

Clearly, the best would be to have a dedicated data structure for describing a solution. What I proposed is a simpler but easier-to-implement substitute for that.

I do not prefer this solution, I think it would be a "nightmare" to confuse such different things.

[Alpar Juttner]

Replying to kpeter:

(Plus an additional constant but it is irrelevant here)

It could be used to store the value of the objective function, couldn't it?

No, it couldn't. The current interface allows to set any kind of Expr as on objective function. Therefore the objective function can also have a constant component. The implementation handles it correctly (I hope), i.e. it does not pass this constant to the solver backend, but it is stored and added to the primal/dual objective value.

I agree, it would be strange. Basically, the two purposes could be implemented the same way, however, lot of feaures of Expr is unnecessary for a Solution class, and the functions

This alone is not a problem. It would be strange to say that a tool can provide a functionality only if it is useful for all use.

[...]

Clearly, the best would be to have a dedicated data structure for describing a solution. What I proposed is a simpler but easier-to-implement substitute for that.

I do not prefer this solution, I think it would be a "nightmare" to confuse such different things.

The word "nightmare" is probably a bit to strong to say here.

[Peter Kovacs]

Replying to alpar:

It could be used to store the value of the objective function, couldn't it?

No, it couldn't.

I said the _value_ of the objective function (with respect to the current solution), which could be different from cx, it could be cx + c_0.

I agree, it would be strange. Basically, the two purposes could be implemented the same way, however, lot of feaures of Expr is unnecessary for a Solution class, and the functions

This alone is not a problem. It would be strange to say that a tool can provide a functionality only if it is useful for all use.

You're right. That's why I wrote the second part of the sentence, which you omitted. It was: "the functions of the latter one should have other names (e.g. value instead of coefficient)."

I do not prefer this solution, I think it would be a "nightmare" to confuse such different things.

The word "nightmare" is probably a bit to strong to say here.

You're right again. That's why I used the quotes. :)

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

It could be used to store the value of the objective function, couldn't it?

No, it couldn't.

I said the _value_ of the objective function (with respect to the current solution), which could be different from cx, it could be cx + c_0.

That clear. The comment was an just explanation why I don't like your idea.

I agree, it would be strange. Basically, the two purposes could be implemented the same way, however, lot of feaures of Expr is unnecessary for a Solution class, and the functions

This alone is not a problem. It would be strange to say that a tool can provide a functionality only if it is useful for all use.

You're right. That's why I wrote the second part of the sentence, which you omitted.

Of course I didn't. I just typically do not answer anything if I can add nothing to it.

It was: "the functions of the latter one should have other names (e.g. value instead of coefficient)."

See, this is a statement. No explanation no arguments. The only sensible answers are 'Yes' and 'No' for this.

I do not prefer this solution, I think it would be a "nightmare" to confuse such different things.

The word "nightmare" is probably a bit to strong to say here.

Actually something tells me that this approach is already in use somewhere in the internal API. Am I right?

All in all the real points here are these.

• It is all about names. If we Expr were caller Vect probably noone would complain about its dual use. In fact -if I remember correctly, it used to be called like that, but at a point we had to introduce the constant components thus I renamed it to Expr.
• I agree that the name Expr is not a best choice if we also want to use it for querying the result, but
  • firstly, we can't change it now.
  • secondly, having two classes with different names but with the same functionality causes incomparably more problems than using a class for a purpose which isn't expected at the first glance. The first choice may really lead to a "nightmare" (from the maintenance point of view), while the only thing second one may cause is "surprise" (maybe a big one :) ).
• But, the nature of the solution of an LP (i.e. it is not only a vector of numbers, but also it constructed from a basis) may justify using a different class for this purpose provided that is will reflect to this difference (i.e. the values in/out of the basis can be handled separately).
• Anything like this will certainly not be in release 1.2, but I wanna make sure the API will allow us to naturally introduce this feature later.

[Peter Kovacs]

Replying to alpar:

It was: "the functions of the latter one should have other names (e.g. value instead of coefficient)."

See, this is a statement. No explanation no arguments. The only sensible answers are 'Yes' and 'No' for this.

Yes, it is a statement. I wrote it as a reason for my point of view. Is it possible to argue using a question? :)

Actually something tells me that this approach is already in use somewhere in the internal API. Am I right?

I don't know.

All in all the real points here are these.

• It is all about names. If we Expr were caller Vect probably noone would complain about its dual use. In fact -if I remember correctly, it used to be called like that, but at a point we had to introduce the constant components thus I renamed it to Expr.

Yes, it is all about names, as I stated above.

• I agree that the name Expr is not a best choice if we also want to use it for querying the result, but
  • firstly, we can't change it now.

Agreed.

• secondly, having two classes with different names but with the same functionality

Not really the same. A Solution class would require much less functionality (e.g. we don't need operators +, -, *, /, +=, -=, *=, /= for that) and its representation could also be slightly different as we don't need a constant component.

causes incomparably more problems than using a class for a purpose which isn't expected at the first glance. The first choice may really lead to a "nightmare" (from the maintenance point of view), while the only thing second one may cause is "surprise" (maybe a big one :) ).

Recall many similar cases in the library. E.g. IterableIntMap and BucketHeap have the same implementation, but they are used for completely different purposes, so they have different interfaces with different function names.

In fact, there are a lot of code and doc duplications. Since the doc is changed more times, the many doc duplications cause more problem.

• But, the nature of the solution of an LP (i.e. it is not only a vector of numbers, but also it constructed from a basis) may justify using a different class for this purpose provided that is will reflect to this difference (i.e. the values in/out of the basis can be handled separately).

This point should be thought over.

• Anything like this will certainly not be in release 1.2, but I wanna make sure the API will allow us to naturally introduce this feature later.

Actually, the question about the names (Expr vs Solution) is not important until we would like to add such a query function to obtain the solution at once.

It would be better to hear other one's opinion. And I would like to turn back to the original questions of this ticket, namely the current conflicts between the interfaces of MipSolver and LpSolver

[Peter Kovacs]

As far as I see, the only important addition of your suggestion would be the use of Expr::CoeffIt to obtain the non-zero elements of the solution (instead of obtaining the values for all columns). Why do we need a Solution/Expr class for that? We could have just an iterator class, e.g. SolutionIt, like the min cut iterators in GomoryHu. This concept would accept any implementation, it could even reflect to the the fact that a solution is constructed from a basis. What do you think about it?

[Alpar Juttner]

Replying to kpeter:

As far as I see, the only important addition of your suggestion would be the use of Expr::CoeffIt to obtain the non-zero elements of the solution (instead of obtaining the values for all columns). Why do we need a Solution/Expr class for that?

Because you may also want to store the solution in an efficient way.

[Alpar Juttner]

Replying to kpeter:

Actually, the question about the names (Expr vs Solution) is not important until we would like to add such a query function to obtain the solution at once.

So, let's assume this mysterious data structure is called X. Now what I want to see is how the query interface for X would look like. Of course I would like to see a solution which looks natural and which is consistent with the other solution query functions.

[Peter Kovacs]

Replying to alpar:

Because you may also want to store the solution in an efficient way.

That's true, I see.

I created a separate ticket for this problem: #345. We could postpone the question of using Expr or a new class Solution.

[Peter Kovacs]

Replying to alpar:

So, let's assume this mysterious data structure is called X. Now what I want to see is how the query interface for X would look like. Of course I would like to see a solution which looks natural and which is consistent with the other solution query functions.

I agree, this is the important question now.

I could not find better functions than:

1. void primalSolution(X&), void dualSolution(X&) for LpSolver,
2. void solution(X&) for MipSolver.

However, the latter one would be a bit strange or confusing, since we have sol() functions in MipSolver, e.g. Value sol(const Expr&). If X = Expr, then Value sol(const Expr&) and void solution(Expr&) would be really confusing, since they would be used for entirely different purposes.

[Peter Kovacs]

I don't like the renaming of primalValue() to primal() too much. (Especially because we forgot to rename solValue() to sol().) There are many overloaded versions of primal(). I think, it would be clearer to have:

  - Value primal (Col c) const
  - Value primal (const Expr &e) const
  - Value primalValue () const

and probably

  - X primalSolution () const

What do you think? Could/should we turn back to primalValue() (keeping primal() as an obsolete alternative)? What about MipSolver?

[Peter Kovacs]

Replying to kpeter:

keeping primal() as an obsolete alternative?

Or "as an alternative" (without saying that any of the two variants is obsolete).

[Peter Kovacs]

Replying to kpeter:

• X primalSolution () const

It should be primalSolution (X&) const.

[Peter Kovacs]

Clarified version

[Peter Kovacs]

The attached new patch [1e16e62a9ea1] is a clarified version, which only contains the modification that I find important/necessary:

• Add sol() (without parameters) to MipSolver as an alias for solValue(), since we had primal() instead of primalValue() in LpSolver.
• Add primalValue() to LpSolver as an alias for primal() (without parameters). (This enables the 0.x query function again because in MipSolver we forgot to make the corresponding renaming. Btw. I find this one slightly better.)
• Rename ColTypes to ColType in MipSolver and keep the old name as an obsolete alias (typedef).
• Doc improvements and unifications.

What do you think? Is it okay? Or should we select xyz() or xyzValue() as prefered form and only apply one of the first two modifications?

Apart from these changes I could accept three versions:

1. Do nothing more, thus the query functions of LP and MIP solvers remain strictly different.
2. Add sol*() functions to LpSolver as aliases for primal*() functions.
3. Add primal*() functions to MipSolver as aliases for sol*() functions.

What do you like? The advantage of 2. and 3. is that they make it easy to switch between LP and MIP solvers in a code. I slightly prefer 3., while Balazs prefer 2. However, the disadvantage of 2. and 3. is that they result in 3-4 alternatives for obtaining the (primal) objective value in LpSolver or MipSolver.

[Alpar Juttner]

I think it's still not very clear what to do with this proposal. After talking to Balazs I opted for removing it from the 1.2 milestone.

This decision is conditional to my assumption that we haven't touched the API of the LP/MIP interface since release 1.1. Please let me know if I'm wrong here.

[Peter Kovacs]

Replying to alpar:

I think it's still not very clear what to do with this proposal. After talking to Balazs I opted for removing it from the 1.2 milestone.

Yes, it's still not clear. Without unambigous decisions, it really seems to be better (or at least safer) to postpone this task, although I do find the current LP-MIP inconsistency quite annoying and "faulty" in a sense that a renaming (primalValue()-->primal()) was not performed consistently (we still have solValue()).

This decision is conditional to my assumption that we haven't touched the API of the LP/MIP interface since release 1.1. Please let me know if I'm wrong here.

We did not change it.