default value in QPLIB format

[svigerske]

The proposed QPLIB format (Appendix B) allows to specify a "default value" for matrix and vector entries. Usually, when it is about coefficients, one uses zero.

I would suggest to make it simpler, even though that would reduce flexibility. Always fix the default value for coefficients to 0 (otherwise, how you parse this? First initialize a n x n matrix with the non-zero default and then overwrite with the given entries, which may then be zero?) and have no default bounds for variables. If you then also adapt the suggestion to use a constraint sense ($\leq$,$\geq$,$=$) and a right-hand-side instead of a left- and right-hand-side, then there is also no need to specify a value for infinity. This would leave out ranged constraints - but are they really used? One could do it like CPLEX and have an extra constraint sense for ranges and an extra section to specify the range.

As you might guess by now, I had this as todo in the paper, which was then removed without comment (maybe it's only me who don't consider "Add files via upload" a useful commit message).

[frangio68]

The proposed QPLIB format (Appendix B) allows to specify a "default value" for matrix and vector entries. Usually, when it is about coefficients, one uses zero.

I would suggest to make it simpler

Do you realise that making it simpler would require rewriting all the instances and also the software that translated them? If you are available to do that it can be discussed. The same sort of goes for abbreviations: some I don't particularly like myself, but my motto is "(s)he who implements decides", and the one who implemented this has decided otherwise. So, if you are volunteering, it won't me me who stop you.

A.

[svigerske]

No, I didn't realise that. I haven't seen any code that handles this QPLIB format, nor any instance in that format. My impression was that the format was still under discussion, also because open questions (put in the paper) had never been commented on. I'll then see whether I'll be available next week to rewrite some translation code.

[nimgould]

Dear all

Sorry, I was away on Friday, and have just got back.

I really don't see the point of this. Why make our propsed format more restrictive, and possibly more verbose? In my area (nonlinear programming), two sided constraints are common, both in applications and arising as subproblems from SQP methods. I appreciate that for many discrete problems, non-negativity is a common theme, but in my world more general bounds are more typical. Thus, the format I described has been shaped by my needs. I don't claim that it is necessarily the best, more that it is sufficiently flexible to handle what one might see as general QPs in all their forms (I accept, that this does not cover every case, such as those where matrices arise not through sparsity, but via some other compressed form such as using a sum of dense, low rank matrices). I was particularly conscious that practitioners find it very inconvenient to massage their application into a more restrictive "standard" form. I believe that to often in the past, input formats (and subroutine/function calling sequences) have been proposed on the basis of the needs of the algorithm, rather than that of the user, and I hope that we are addressing this here.

I really don't see that providing a single (possibly nonzero) value to specify default values for vectors is a large overhead; the default for matrices is zero, as sparsity is by far the most common structure in both discrete and continuous problems as far as I am aware. I accept that one then needs to be able to represent infinity, but to my mind it is simply a choice of either having a file for which all fields (save for a few keywords at the start) are numbers, or mixing numbers, symbols and further keywords; I simply prefer the former as I find it easier to parse.

I should add that I have interfaces to all of my (local) QP methods (in GALAHAD) using this format (as well as others), and have found it convenient. I have written conversion codes between the current qplib and lp formats, and also codes to fill (fortran) matrices and vectors from qplib (a C version would be trivial, but probably best left to a native C speaker). I fully expect that the qplib format will be useful not just for our test set, but as an alternative for others who wish to exchange their QP examples.

I think we need more views here.

Nick

Nicholas I. M. Gould Scientific Computing Department mailto:nick.gould@stfc.ac.uk G59, R18 Rutherford Appleton Laboratory phone: 0(44)1235 445801 Chilton, Oxon OX11 0QX England EU www: http://www.numerical.rl.ac.uk/people/nimg/nimg.html

---

From: Stefan Vigerske [notifications@github.com] Sent: 27 January 2017 14:55 To: fabiofurini/QPLIB Cc: Subscribed Subject: [fabiofurini/QPLIB] default value in QPLIB format (#3)

The proposed QPLIB format (Appendix B) allows to specify a "default value" for matrix and vector entries. Usually, when it is about coefficients, one uses zero.

I would suggest to make it simpler, even though that would reduce flexibility. Always fix the default value for coefficients to 0 (otherwise, how you parse this? First initialize a n x n matrix with the non-zero default and then overwrite with the given entries, which may then be zero?) and have no default bounds for variables. If you then also adapt the suggestion to use a constraint sense ($\leq$,$\geq$,$=$) and a right-hand-side instead of a left- and right-hand-side, then there is also no need to specify a value for infinity. This would leave out ranged constraints - but are they really used? One could do it like CPLEX and have an extra constraint sense for ranges and an extra section to specify the range.

As you might guess by now, I had this as todo in the paper, which was then removed without comment (maybe it's only me who don't consider "Add files via upload" a useful commit message).

� You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/fabiofurini/QPLIB/issues/3, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AK3Aev997dOhJTLFXGn3AorHR2Gkp1Q0ks5rWgVYgaJpZM4Lv2UA.

[svigerske]

Thanks for the informative answer.

I think the changes that I suggested were not really restricting the problems you could write, but only restricted the number of ways you could write it (which makes me think that having only exactly one way to write a specific MIQCQP (with given variables and equations order) would be an additional benefit). I doubt that it would be "very inconvenient" for a user if one removes the choice on the "default values" and just fixes a reasonable value.

Disallowing ranged rows (-inf < c_l < c_u < +inf) completely would be true restriction. If the format is meant to be used for more than the QPLIB instances, then I agree that that would be "very inconvenient".

Another more specific followup question: Why one can specify the "default values" for the coefficients of the linear part in the objective, but not for the coefficients of the linear parts in the constraints? Thus, there is b_d^0 but no b_d^i. I think it would be easier to just eleminate b_d^0, too, and assume that is 0 (as for all other coefficient vectors and matrices).

[nimgould]

Hi Stefan

Certainly some of the QP examples I submitted from CUTEst have range constraints. Thus it is not simply the potential use outside of QPLIB for which this is important.

I agree that one could also provide a default for the linear parts of the constraints. However, I chose not to for a couple of reasons. Firstly, since this information is encoded in the matrix A, it was not obvious how to do so for an individual row without making things far more verbose; one could have an overall default for A, but would this ever be used? Secondly, many eminent people, such as Gil Strang, have suggested that the objective function and constraints generally play different roles in (optimization) problems. The constraints reflect the "physics" (or economics or whatever the field is), while the objective represents "ambition", which is far harder to quantify in general. "Physics" is usually encoded in local interactions, and thus constraints tend to be "sparse". Thus zero is generally a useful default for values of A. I accept that this will not always be the case, but is it really so common that we should overcomplicate our format? Our test set strongly suggests that zero is reasonable, especially for large instances. As the objective is far less uniformly defined, it makes sense to me (at least) to allow for a different default; a brief examination of the problems in our set suggests that the objective gradient is frequently dense, and often representable by a single value. Thus, I would be reluctant to presume that b_d^0 = 0; the other "formats" we support make no such assumptions, and to do so would again over-constrain our poor practitioners.

Best wishes

Nick

On 29/01/17 15:10, Stefan Vigerske wrote:

Thanks for the informative answer.

I think the changes that I suggested were not really restricting the problems you could write, but only restricted the number of ways you could write it (which makes me think that having only exactly one way to write a specific MIQCQP (with given variables and equations order) would be an additional benefit). I doubt that it would be "very inconvenient" for a user if one removes the choice on the "default values" and just fixes a reasonable value.

Disallowing ranged rows (-inf < c_l < c_u < +inf) completely would be true restriction. If the format is meant to be used for more than the QPLIB instances, then I agree that that would be "very inconvenient".

Another more specific followup question: Why one can specify the "default values" for the coefficients of the linear part in the objective, but not for the coefficients of the linear parts in the constraints? Thus, there is b_d^0 but no b_d^i. I think it would be easier to just eleminate b_d^0, too, and assume that is 0 (as for all other coefficient vectors and matrices).

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/fabiofurini/QPLIB/issues/3#issuecomment-275919730, or mute the thread https://github.com/notifications/unsubscribe-auth/AK3AekSpCWYPOw0gOVgmIPcyXH7TZcLKks5rXKvlgaJpZM4Lv2UA.

-- Nicholas I. M. Gould Scientific Computing Department email: nick.gould@stfc.ac.uk G59, R18 Rutherford Appleton Laboratory phone: 0(44)1235 445801 Chilton, Oxon OX11 0QX England EU www: http://www.numerical.rl.ac.uk/people/nimg

[svigerske]

It doesn't seem as if I'm much convincing :(, nor others seem to have a strong opinion on this, so I'll close this issue.