I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary.

Of course it is always possible to replace integer-valued variables with a set of binary variables, but that's okay; I'm still interested in optimization problems whose "natural" formulation would be as an integer problem with more-than-binary integers.

Classical examples that come up when searching for integer programming are Set Cover and Max Cut, but those have a very straight-forward binary formulation... any pointers?

EDIT: Let me clarify natural through an example. Let's say we have some integer optimization problem where variables $x_i$ refer to how many units of product $i$ a factory should produce. This would be naturally formulated with integers other than 0 and 1. On the other hand, a knapsack combinatorial optimization problem would have an integer formulation where $x_i = 0, 1$ indicating whether or not item $i$ is chosen.

EDIT: In the integer programming literature, binary does not refer to the overall representation of integers. It refers to the additional constraint that all variables be either 0 or 1, instead of arbitrary integers.

  • $\begingroup$ Oh, now it makes infinitely more sense. However, the question is still too vague. See e.g. meta.cstheory.stackexchange.com/a/2880 for a discussion of “natural”. $\endgroup$ May 4 '16 at 17:49
  • $\begingroup$ I tried adding some clarification. I understand that "natural" can be vague, but I thought in the context of integer problems, "natural" would mean "We want to find optimal values for certain quantities, and those quantities are integers" and if that's the case, then representing those quantities with integer-valued variables feels "natural". $\endgroup$
    – Lagerbaer
    May 4 '16 at 18:23
  • $\begingroup$ When the variables are 0-1 it is not called binary, it is called "0-1 Integer Programming". $\endgroup$
    – Kaveh
    May 4 '16 at 22:36
  • 1
    $\begingroup$ I think encoding number by a sequence of 0s and 1s is very natural. What you should do is to explain why you are looking for what you are looking for, i.e. what is your motivation? It seems to me your usage of "nice" and "natural" is a replacement to an explanation of why you are looking for problems reducible to Integer Programming. What difference it makes for you if a problem has a 0-1 Integer Program? $\endgroup$
    – Kaveh
    May 4 '16 at 22:42
  • 6
    $\begingroup$ The Gilmore-Gomory relaxation for bin packing/cutting stock problem has variables that can be arbitrary non-negative integers. $\endgroup$ May 5 '16 at 3:57

Here are a few examples:

I would, however, like to figure out upper bounds for integer variables used in practice. Something still on my mind. For instance, can we assume that all integer variable used in practice are upper bounded by 1000? 10,000? How can we use this information? It is true that often it can be advantageous when solving to convert integer variables into binary variables, but this is not always the case.

  • $\begingroup$ Great answer. Thank you very much. As to your follow-up question, I don't think there are "general" upper bounds. For example if you do portfolio optimization with discrete allocations (let's say you're solving for the actual number of stocks to purchase, instead of the floating-point weight), then depending on how much capital you have, the number of stocks to buy can be quite large. I'd say the bounds must always come out of the particular problem at hand. $\endgroup$
    – Lagerbaer
    Dec 19 '18 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.