# What are some example problems for integer programming that are *not binary*

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.

• 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”. May 4 '16 at 17:49
• 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". May 4 '16 at 18:23
• When the variables are 0-1 it is not called binary, it is called "0-1 Integer Programming". May 4 '16 at 22:36
• 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? May 4 '16 at 22:42
• The Gilmore-Gomory relaxation for bin packing/cutting stock problem has variables that can be arbitrary non-negative integers. May 5 '16 at 3:57