problem types in QPLIB format

[svigerske]

For the QPLIB format, another set of problem type abbreviations is introduced (see [1] after Table 7).

Here a question/suggestion I had as todo in the code and that wasn't answered so far: Are LPQC and QPQC frequently used abbreviations? If a linear program has quadratic constraints, how can it then still be a linear program? I am more familiar with the abbreviations QCP instead of LPQC and QCQP instead of QPQC. I further think that one could skip QCP and consider them as part of QCQP.

[nimgould]

I really don't mind what we call the various sub-species of QP, so long as we use notation that allows us to distinguish; I believe that there has already been a number of historical alternatives. My concern is simply that we are able to distinguish (i) the type of objective function, (ii) the (most general) type of constraints and (iii) the type(s) of variables involved.

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 15:11 To: fabiofurini/QPLIB Cc: Subscribed Subject: [fabiofurini/QPLIB] problem types in QPLIB format (#4)

For the QPLIB format, another set of problem type abbreviations is introduced (see [1] after Table 7).

Here a question/suggestion I had as todo in the code and that wasn't answered so far: Are LPQC and QPQC frequently used abbreviations? If a linear program has quadratic constraints, how can it then still be a linear program? I am more familiar with the abbreviations QCP instead of LPQC and QCQP instead of QPQC. I further think that one could skip QCP and consider them as part of QCQP.

� 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/4, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AK3AehhtnYqsoPE4amUDPkYEFlTR8rwWks5rWgkJgaJpZM4Lv3Yn.

[svigerske]

It would be nice to choose one of these alternatives instead of inventing a new one. To me, abbreviations like LP,QCP,QP,QCQP, and everything again prefixed with "MI" are familiar. Thus, I would change it to:

For continuous problems (i.e., all variables are continuous): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [LP] a linear program, \item [QCP] a problem with linear objective and linear quadratic constraints, \item [BQP] a bound-constrained quadratic program, \item [QP] a quadratic program (quadratic objective, linear constraints), and \item [QCQP] a quadratic program with linear and quadratic constraints. \end{description}

For integer problems (i.e., all variables are integer valued): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [ILP] an integer linear program, \item [IQCP] an integer program with linear objective and linear quadratic constraints, \item [IBQP] an integer bound-constrained quadratic program, \item [IQP] an integer quadratic program, and \item [IQCQP] an integer quadratic program with linear and quadratic constraints. \end{description} \item For mixed-integer problems (i.e., there is a mix of continuous and integer variables): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [MILP] a mixed-integer linear program, \item [MIQCP] a mixed-integer program with linear objective and linear and quadratic constraints, \item [MIBQP] a mixed-integer bound-constrained quadratic program, \item [MIQP] a mixed-integer quadratic program, and \item [MIQCQP] a mixed-integer problem with quadratic objective and linear and quadratic constraints. \end{description}

[merraksh]

I agree with Stefan's proposal and I think it's in accordance to Nick's classification guidelines regarding type of objective, constraints, and variables. Given that a mixed integer problem is as hard as an integer one, I would drop the I* classification.

Pietro

On Sun, Jan 29, 2017 at 3:23 PM, Stefan Vigerske notifications@github.com wrote:

It would be nice to choose one of these alternatives instead of inventing a new one. To me, abbreviations like LP,QCP,QP,QCQP, and everything again prefixed with "MI" are familiar. Thus, I would change it to:

For continuous problems (i.e., all variables are continuous): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [LP] a linear program, \item [QCP] a problem with linear objective and linear quadratic constraints, \item [BQP] a bound-constrained quadratic program, \item [QP] a quadratic program (quadratic objective, linear constraints), and \item [QCQP] a quadratic program with linear and quadratic constraints. \end{description}

For integer problems (i.e., all variables are integer valued): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [ILP] an integer linear program, \item [IQCP] an integer program with linear objective and linear quadratic constraints, \item [IBQP] an integer bound-constrained quadratic program, \item [IQP] an integer quadratic program, and \item [IQCQP] an integer quadratic program with linear and quadratic constraints. \end{description} \item For mixed-integer problems (i.e., there is a mix of continuous and integer variables): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [MILP] a mixed-integer linear program, \item [MIQCP] a mixed-integer program with linear objective and linear and quadratic constraints, \item [MIBQP] a mixed-integer bound-constrained quadratic program, \item [MIQP] a mixed-integer quadratic program, and \item [MIQCQP] a mixed-integer problem with quadratic objective and linear and quadratic constraints. \end{description}

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

[nimgould]

I am happy with change this if everyone agrees. I will update the qplib instances once I get the go-ahead.

Nick

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

It would be nice to choose one of these alternatives instead of inventing a new one. To me, abbreviations like LP,QCP,QP,QCQP, and everything again prefixed with "MI" are familiar. Thus, I would change it to:

For continuous problems (i.e., all variables are continuous): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [LP] a linear program, \item [QCP] a problem with linear objective and linear quadratic constraints, \item [BQP] a bound-constrained quadratic program, \item [QP] a quadratic program (quadratic objective, linear constraints), and \item [QCQP] a quadratic program with linear and quadratic constraints. \end{description}

For integer problems (i.e., all variables are integer valued): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [ILP] an integer linear program, \item [IQCP] an integer program with linear objective and linear quadratic constraints, \item [IBQP] an integer bound-constrained quadratic program, \item [IQP] an integer quadratic program, and \item [IQCQP] an integer quadratic program with linear and quadratic constraints. \end{description} \item For mixed-integer problems (i.e., there is a mix of continuous and integer variables): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [MILP] a mixed-integer linear program, \item [MIQCP] a mixed-integer program with linear objective and linear and quadratic constraints, \item [MIBQP] a mixed-integer bound-constrained quadratic program, \item [MIQP] a mixed-integer quadratic program, and \item [MIQCQP] a mixed-integer problem with quadratic objective and linear and quadratic constraints. \end{description}

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

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

[nimgould]

Hi Pietro

I am not an expert here, but I do recall going to a plenary at one of our big meetings (ISMP, SIAM-opt or something similar) where one of the plenary speakers claimed that mixed-integer problems were far harder than integer ones. What does the remainder of the committee think? Is this something that should be flagged in the format? I am happy to go with either viewpoint.

Nick

On 29/01/17 19:38, merraksh wrote:

I agree with Stefan's proposal and I think it's in accordance to Nick's classification guidelines regarding type of objective, constraints, and variables. Given that a mixed integer problem is as hard as an integer one, I would drop the I* classification.

Pietro

On Sun, Jan 29, 2017 at 3:23 PM, Stefan Vigerske notifications@github.com wrote:

It would be nice to choose one of these alternatives instead of inventing a new one. To me, abbreviations like LP,QCP,QP,QCQP, and everything again prefixed with "MI" are familiar. Thus, I would change it to:

For continuous problems (i.e., all variables are continuous): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [LP] a linear program, \item [QCP] a problem with linear objective and linear quadratic constraints, \item [BQP] a bound-constrained quadratic program, \item [QP] a quadratic program (quadratic objective, linear constraints), and \item [QCQP] a quadratic program with linear and quadratic constraints. \end{description}

For integer problems (i.e., all variables are integer valued): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [ILP] an integer linear program, \item [IQCP] an integer program with linear objective and linear quadratic constraints, \item [IBQP] an integer bound-constrained quadratic program, \item [IQP] an integer quadratic program, and \item [IQCQP] an integer quadratic program with linear and quadratic constraints. \end{description} \item For mixed-integer problems (i.e., there is a mix of continuous and integer variables): \begin{description}[leftmargin=!,labelwidth=\widthof{\texttt{SMILQPC}}] \item [MILP] a mixed-integer linear program, \item [MIQCP] a mixed-integer program with linear objective and linear and quadratic constraints, \item [MIBQP] a mixed-integer bound-constrained quadratic program, \item [MIQP] a mixed-integer quadratic program, and \item [MIQCQP] a mixed-integer problem with quadratic objective and linear and quadratic constraints. \end{description}

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/fabiofurini/QPLIB/issues/4#issuecomment-275920667, or mute the thread

https://github.com/notifications/unsubscribe-auth/AARvgiXLSWZQoJ0el4ZqMsLdNKxrfLABks5rXK7fgaJpZM4Lv3Yn .

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

-- 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]

According to https://github.com/fabiofurini/QPLIB/issues/3#issuecomment-275691825, it is sufficient if the one who writes code makes a decision. We've just put up qplib instances on the website to come, and I'll modify the problem type names in there accordingly. I wouldn't mind to drop the pure-integer category, as @merraksh suggested, but will leave it in for now.

[leoliberti]

[Nick]> I am not an expert here, but I do recall going to a plenary [Nick]> at one of our big meetings (ISMP, SIAM-opt or something similar) [Nick]> where one of the plenary speakers claimed that mixed-integer [Nick]> problems were far harder than integer ones. What does the [Nick]> remainder of the committee think?

Deriving compact descriptions of convex hulls of mixed-integer nonlinear sets is “difficult” because there are some complications w.r.t. just integer sets. Maybe this is what motivated that speaker? (Though I don’t know whom you’re referring to). It might also be just “practical difficulty”.

Computational complexity-wise, the following hold:

• Solving MINLPs is undecidable by the negative solution of Hilbert’s 10th problem (here “decidable” does not mean “finding a solution” but “proving whether a solution exists or not”).

• Solving MILPs is in NP hence decidable.

• There are several undecidable cases in MINLP, to do with representing all integers: o QCP in unbounded integer variables in undecidable o some simple continuous NLPs with sin/cos/tan are undecidable.

• Polynomial NLPs (continuous variables only) are all decidable by Tarski’s quantifier elimination.

• If a MINLP is bounded in both variable ranges and objective function range (let’s call that a “totally bounded MINLP”) then it’s decidable (proof: use Tarski’s quantifier elimination for each of the finite number of assignments to integer variables).

• With unboundedness in the obejctive and trigonometric functions, one can construct a bounded-variable NLP that is undecidable.

• MILPs are NP-hard by reduction from SAT

• QPs are NP-hard by reduction from SAT

• Box-constrained QPs are NP-hard by reduction from 3SAT

• QPs over a simplex are NP-hard by reduction from k-CLIQUE

• QPs with at least one negative eigenvalue are NP-hard by reduction from k-CLIQUE.

• Totally bounded MINLPs are NP-hard by inclusion of MILP and the various QP variants.

Although I believe MINLPs are actually “harder than INLPs” in practice, I don’t think one can argue the same point using computational complexity, since “being HP-hard” is a qualitative statement, not a quantitative one. It means “at least as hard as the hardest problem in the class NP, though we don’t know how hard that hardest problem really is, and this is why we are forced to use such a crappy qualitative relative notion of being hard”.

For practical purposes, I think it might be helpful to flag “only integer” versus “truly mixed-integer”. But since I currently don’t have the time to put in any change myself, following Antonio’s philosophy that “if you want something changed, then you should change it” (a principle with which I agree wholeheartedly), I’m going to live with the existing situation.

Leo

[frangio68]

Just a quick comment on the "problem types". The most elegant solution would have been to use the three-field classification we tout in the paper, which has the advantage that nobody uses it, so everybody dislikes it in the same way ;-)

Never tried to push for it and never will. However, in that classification the distinction between "I" (purely integer) and "G" (mixed-integer) was done. At the time it was considered OK, I gather. I don't see why it should not be OK now. So I'd vote for keeping it. But since I'm not doing any implementation one way or other, my vote counts precisely zilch.

A.

[merraksh]

Hi Nick,

I must have had my general-solver-developer goggles on ;-) Indeed the distinction can be quite clear as far as algorithms go. I'm fine with keeping the I* classes.

Pietro

On Mon, Jan 30, 2017 at 10:08 AM, Stefan Vigerske notifications@github.com wrote:

According to #3 (comment) https://github.com/fabiofurini/QPLIB/issues/3#issuecomment-275691825, it is sufficient if the one who writes code makes a decision. We've just put up qplib instances on the website to come, and I'll modify the problem type names in there accordingly. I wouldn't mind to drop the pure-integer category, as @merraksh https://github.com/merraksh suggested, but will leave it in for now.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/fabiofurini/QPLIB/issues/4#issuecomment-276023561, or mute the thread https://github.com/notifications/unsubscribe-auth/AARvgtRxZcmsSff6x63fRa9aKgtDjmJZks5rXba3gaJpZM4Lv3Yn .

[svigerske]

I recall some discussions on using the three-field classification from the paper for the .qplib format. That could have been by e-mail last summer or so. As far as I remember, the main reason against it was that the three-field classification also provided information about convexity of objective and constraints, which could be a burden for a casual user to compute. He could just specify everything as nonconvex, but that still wouldn't be correct, though it would probably be not much problematic in practice (<-- this is usually the argument to justify bad decisions :)).

I wouldn't mind to put the three-field classification additionally and optionally as an informative field into the format. Optionally could eventually mean having some string meaning "unknown", e.g., "???".

[nimgould]

Thanks, Leo. Very informative for a non expert!

See my next message ...

Nick

On 30/01/17 10:51, leoliberti wrote:

[Nick]> I am not an expert here, but I do recall going to a plenary [Nick]> at one of our big meetings (ISMP, SIAM-opt or something similar) [Nick]> where one of the plenary speakers claimed that mixed-integer [Nick]> problems were far harder than integer ones. What does the [Nick]> remainder of the committee think?

Deriving compact descriptions of convex hulls of mixed-integer nonlinear sets is “difficult” because there are some complications w.r.t. just integer sets. Maybe this is what motivated that speaker? (Though I don’t know whom you’re referring to). It might also be just “practical difficulty”.

Computational complexity-wise, the following hold:

*

Solving MINLPs is undecidable by the negative solution of Hilbert’s 10th
problem (here “decidable” does not mean “finding a solution” but “proving
whether a solution exists or not”).

*

Solving MILPs is in NP hence decidable.

*

There are several undecidable cases in MINLP, to do with representing all
integers:
o QCP in unbounded integer variables in undecidable
o some simple continuous NLPs with sin/cos/tan are undecidable.

*

Polynomial NLPs (continuous variables only) are all decidable by Tarski’s
quantifier elimination.

*

If a MINLP is bounded in both variable ranges and objective function range
(let’s call that a “totally bounded MINLP”) then it’s decidable (proof: use
Tarski’s quantifier elimination for each of the finite number of assignments
to integer variables).

*

With unboundedness in the obejctive and trigonometric functions, one can
construct a bounded-variable NLP that is undecidable.

*

MILPs are NP-hard by reduction from SAT

*

QPs are NP-hard by reduction from SAT

*

Box-constrained QPs are NP-hard by reduction from 3SAT

*

QPs over a simplex are NP-hard by reduction from k-CLIQUE

*

QPs with at least one negative eigenvalue are NP-hard by reduction from
k-CLIQUE.

*

Totally bounded MINLPs are NP-hard by inclusion of MILP and the various QP
variants.

Although I believe MINLPs are actually “harder than INLPs” in practice, I don’t think one can argue the same point using computational complexity, since “being HP-hard” is a qualitative statement, not a quantitative one. It means “at least as hard as the hardest problem in the class NP, though we don’t know how hard that hardest problem really is, and this is why we are forced to use such a crappy qualitative relative notion of being hard”.

For /practical purposes/, I think it might be helpful to flag “only integer” versus “truly mixed-integer”. But since I currently don’t have the time to put in any change myself, following Antonio’s philosophy that “if you want something changed, then you should change it” (a principle with which I agree wholeheartedly), I’m going to live with the existing situation.

Leo

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

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

[nimgould]

I am happy to go with this. Such a classification provides all the information needed to parse the remainder of the qplib file, and more. I don't think that it is an issue if we miss-classify problems so long as we err on the cautious side. I will re-generate the qplib files for all of our examples, and we can change things by hand at a later date if there are upgrades to an individual classification because of new information.

Just to be sure, I take it that by convex we mean that the function has a positive semi definite Hessian; some methods are only designed for strictly convex problems (Hessian is positive definite)?

Nick

On 30/01/17 11:13, Stefan Vigerske wrote:

I recall some discussions on using the three-field classification from the paper for the .qplib format. That could have been by e-mail last summer or so. As far as I remember, the main reason against it was that the three-field classification also provided information about convexity of objective and constraints, which could be a burden for a casual user to compute. He could just specify everything as nonconvex, but that still wouldn't be correct, though it would probably be not much problematic in practice (<-- this is usually the argument to justify bad decisions :)).

I wouldn't mind to put the three-field classification additionally and optionally as an informative field into the format. Optionally could eventually mean having some string meaning "unknown", e.g., "???".

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

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

[nimgould]

Dear all

I notice that we never seemed to have reached a consensus on this (from July 2016).

I know this will be controversial, but here goes again ...

Those of us from the continuous world are used to having quadratic functions written something like

q(x) = f + g^T x + 1/2 x^T H x

While the 1/2 might be seen as a nuisance, it does allow us to refer to H as the Hessian of q. I looked through all of the books on my shelf, and of the "classics" in the area include the 1/2, as does Wikipedia and other (but not all) online resources. CPLEX seems to be schizophrenic in that the 1/2 appear for the objective but not constraints!

I notice that our paper does not mention the 1/2. This would not really be an issue, except that the qplib format (at least as I have implemented it) assumed it. I can, of course, easily adapt this, but before I do, I wonder whether I should, or whether we might (trivially) change this in the paper (I think it occurs 8 times).

To my mind, not having the 1/2 goes against standard practice, but maybe this is only standard in my area, and that in the discrete world the 1/2 is seen as at best as an annoyance (and for some people perhaps an alliance with The Devil). I recall that Stefan was strongly opposed, but I never had a reaction from anyone else ... maybe nobody cares!

Nick

PS. p 9, paragraph 2, line 5. The sum should be involve z_j^2 (without the z), and it should say z^T = x^T L^i

PPS. The earlier discussion ...

I suspect that trying to go against 50+ years of history to remove the dreaded 1/2 will confuse more people than it helps. I suspect that the 1/2 simply had its origins in Taylor series.

I know where the 1/2 comes from, but I don't think that a problem instance format should take care of making gradients look easier. If one introduces a new format, then that gives the chance not to repeat a 50 years old mistake.

Well, the mistake probably goes back to Newton and Leibniz, where the 1/2 always precedes the Hessian. I just did a small survey of solvers/wikis (and of course that is biased!). The Wikis (wikipedia, NEOS) have the 1/2. Almost anything that leads to a QP from the continuous world has the 1/2, and many packages that derived in that world (such as CPLEX, CVXOPT, Mosek and Matlab) concur. There are some exceptions (CGAL), and some that are confused (Gurobi with 1/2 in the objective and 1 in the constraints).

The discrete solvers seem more mixed.

On this basis, I suspect that removing the half may baffle a sizeable fraction of our intended community. My feeling is to keep it,

-- 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]

Regarding "convex", it is indeed just positive semidefinite.

Regarding the 1/2 issue, I'm fine either way - repeating the awkard 1/2 for historical reasons or dropping it for practical reasons. Could also use a factor of 2, or 1/3, and maybe alternate from constraint to constraint... ;). @fabiofurini said they want to submit by Friday, so what is in the paper by then should be it.

[leoliberti]

About the 0.5 issue... for what it's worth, some combinatorial problems are actually written with 1/2 in front since otherwise the quantity you get is double what it should be, by symmetry (e.g. I think both max cut and the Motzkin-Straus formulation of the max clique have 1/2 in front).

Leo

[svigerske]

Closed by d4e031c1 (and following commits).