Opened 11 years ago
Closed 4 years ago
#326 closed enhancement (fixed)
MipSolver interface fixes and extension
Reported by: | Peter Kovacs | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | critical | Milestone: | LEMON 1.4 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description (last modified by )
In MipSolver
there are type()
, sol()
and solValue()
functions to obtain the (primal) solution.
- There are two inconsistent names here:
solValue()
should be renamed tosol()
(as on overloaded version) asprimalValue()
was renamed toprimal()
inLpSolver
.ColTypes
should be renamed toColType
, since we do not use plural in similar names.
- Apart form that, I suggest an extension. Let's introduce
primalType()
andprimal()
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).
- Maybe
type()
,sol()
could also be added toLpSolver
as an alias for the primal queries.
Attachments (2)
Change History (31)
comment:1 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 11 years ago by
Priority: | major → critical |
---|
comment:3 follow-up: 4 Changed 11 years ago by
comment:4 Changed 11 years ago by
comment:5 Changed 11 years ago by
Owner: | changed from Balazs Dezso to Peter Kovacs |
---|---|
Status: | new → assigned |
The attached patch [d4c3ba9ac811] makes the following modifications:
- Add
sol()
(without parameters) toMipSolver
as an alias forsolValue()
, since we haveprimal()
instead ofprimalValue()
inLpSolver
. - Add
primal()
(3 overloaded variants) andprimalValue()
toMipSolver
as aliases forsol()
andsolValue()
. - Rename
ColTypes
toColType
inMipSolver
and keep the old name as an obsolete typedef. - Add
primalValue()
toLpSolver
as an alias forprimal()
(without parameters). - Doc improvements + unifications.
Changed 11 years ago by
Attachment: | 326-lp-mip-unify-d4c3ba9ac811.patch added |
---|
comment:6 Changed 11 years ago by
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?
comment:7 follow-ups: 8 9 Changed 11 years ago by
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.
comment:8 Changed 11 years ago by
Replying to alpar:
In other words, primal(...)
is for obtaining x, while primalValue()
is for obtaining cx.
comment:9 follow-up: 10 Changed 11 years ago by
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 inMipSolver
nor inLpSolver
.
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/orprimal(Expr &e)
was intended to return the whole solution (as anExpr
),
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?
comment:10 follow-up: 11 Changed 11 years ago by
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 inMipSolver
nor inLpSolver
.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/orprimal(Expr &e)
was intended to return the whole solution (as anExpr
),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 abovesol(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.
comment:11 follow-up: 12 Changed 11 years ago by
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/orprimal(Expr &e)
was intended to return the whole solution (as anExpr
),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 abovesol(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.
comment:12 follow-up: 13 Changed 11 years ago by
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 aSolution
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.
comment:13 follow-up: 14 Changed 11 years ago by
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 aSolution
class, and the functionsThis 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. :)
comment:14 follow-up: 15 Changed 11 years ago by
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 aSolution
class, and the functionsThis 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 callerVect
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 toExpr
. - 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.
comment:15 follow-up: 18 Changed 11 years ago by
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 callerVect
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 toExpr
.
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
comment:16 follow-up: 17 Changed 11 years ago by
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?
comment:17 follow-up: 19 Changed 11 years ago by
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 aSolution
/Expr
class for that?
Because you may also want to store the solution in an efficient way.
comment:18 follow-up: 20 Changed 11 years ago by
Replying to kpeter:
Actually, the question about the names (
Expr
vsSolution
) 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.
comment:19 Changed 11 years ago by
comment:20 Changed 11 years ago by
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 forX
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:
void primalSolution(X&)
,void dualSolution(X&)
forLpSolver
,void solution(X&)
forMipSolver
.
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.
comment:21 follow-ups: 22 23 Changed 11 years ago by
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
?
comment:22 Changed 11 years ago by
Replying to kpeter:
keeping
primal()
as an obsolete alternative?
Or "as an alternative" (without saying that any of the two variants is obsolete).
comment:23 Changed 11 years ago by
comment:24 Changed 11 years ago by
The attached new patch [1e16e62a9ea1] is a clarified version, which only contains the modification that I find important/necessary:
- Add
sol()
(without parameters) toMipSolver
as an alias forsolValue()
, since we hadprimal()
instead ofprimalValue()
inLpSolver
. - Add
primalValue()
toLpSolver
as an alias forprimal()
(without parameters). (This enables the 0.x query function again because inMipSolver
we forgot to make the corresponding renaming. Btw. I find this one slightly better.) - Rename
ColTypes
toColType
inMipSolver
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:
- Do nothing more, thus the query functions of LP and MIP solvers remain strictly different.
- Add
sol*()
functions toLpSolver
as aliases forprimal*()
functions. - Add
primal*()
functions toMipSolver
as aliases forsol*()
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
.
comment:25 follow-up: 27 Changed 11 years ago by
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.
comment:26 Changed 11 years ago by
Milestone: | LEMON 1.2 release → LEMON 1.3 release |
---|
comment:27 Changed 11 years ago by
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.
comment:28 Changed 8 years ago by
Milestone: | LEMON 1.3 release → LEMON 1.4 release |
---|
comment:29 Changed 4 years ago by
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
Type: | defect → enhancement |
Replying to kpeter:
Of course,
solValue()
should be kept for compatibility. So what about addingprimalValue()
toLpSolver
to be consistent?Could we do anything with this? E.g. rename to
ColType
and keep an obsolete typedefColTypes
?What do you think about these ideas?