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

Question

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.

Answer 1

Here are a few examples:

• (Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.
• (Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem

• Problems with modular constraints: $x \equiv 3 \pmod 5$ can be written as $x + 5y = 3$, $y \in \mathbb{Z}$. Most commonly seen in cyclic train schedules - https://www.sciencedirect.com/science/article/abs/pii/S0360835213001782

• Generalized Vehicle Routing Problems - http://orel.uca.es/pdfs/ORP3_3_ClaudiaBode.pdf

• B-matchings - https://arxiv.org/pdf/math/0607088.pdf
• Bin Packing with a constant number of item types (theoretical application) https://arxiv.org/abs/1307.5108
• Lattice point counting in polyhedra - https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf
• Lattice vector problems - Closest Vector Problem (CVP) and Shortest Vector Problem (SVP) are technically unconstrained convex quadratic (general) integer programming problems. These are important problems in computer science. https://en.wikipedia.org/wiki/Lattice_problem This also goes under the name of "integer least squares regression" since it is also just solving a quadratic regression problem with an integer constraint https://stanford.edu/~boyd/papers/pdf/int_quad_cuts.pdf "The integer least squares problem captures the essence of the phase ambiguity estimation problem arising in the global positioning systems (GPS) [HB98]."

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.