<p>Here are a few examples:</p>

<ul>
<li>(Most Common) Cutting Stock Problem - determine patterns for which to cut boards in order to meet demand.</li>
<li>(Kinda same problem) - Knapsack with general integer variables - used for column generation in the cutting stock problem</li>
<li><p>Problems with modular constraints:  <span class="math-container">$x \equiv 3 \pmod 5$</span> can be written as <span class="math-container">$x + 5y = 3$</span>, <span class="math-container">$y \in \mathbb{Z}$</span>.  Most commonly seen in cyclic train schedules - <a href="https://www.sciencedirect.com/science/article/abs/pii/S0360835213001782" rel="noreferrer">https://www.sciencedirect.com/science/article/abs/pii/S0360835213001782</a></p></li>
<li><p>Generalized Vehicle Routing Problems - <a href="http://orel.uca.es/pdfs/ORP3_3_ClaudiaBode.pdf" rel="noreferrer">http://orel.uca.es/pdfs/ORP3_3_ClaudiaBode.pdf</a></p></li>
<li>B-matchings - <a href="https://arxiv.org/pdf/math/0607088.pdf" rel="noreferrer">https://arxiv.org/pdf/math/0607088.pdf</a></li>
<li>Bin Packing with a constant number of item types (theoretical application) <a href="https://arxiv.org/abs/1307.5108" rel="noreferrer">https://arxiv.org/abs/1307.5108</a></li>
<li>Lattice point counting in polyhedra - <a href="https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf" rel="noreferrer">https://www.math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf</a></li>
<li>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. <a href="https://en.wikipedia.org/wiki/Lattice_problem" rel="noreferrer">https://en.wikipedia.org/wiki/Lattice_problem</a>
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
<a href="https://stanford.edu/~boyd/papers/pdf/int_quad_cuts.pdf" rel="noreferrer">https://stanford.edu/~boyd/papers/pdf/int_quad_cuts.pdf</a>
"The integer least squares problem captures the essence of the phase ambiguity estimation problem arising in the global positioning systems (GPS) [HB98]."</li>
</ul>

<p>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.  </p>

CC BY-SA 4.0
2018-12-19T06:31:44.777Z
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.
Lagerbaer
CC BY-SA 4.0
2018-12-19T00:27:24.693Z
2018-12-19T00:27:24.693Z
Robert Hildebrand
<p>I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that <em>is not</em> binary.</p>

<p>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.</p>

<p>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?</p>

<hr>

<p>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 <em>naturally</em> 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. </p>

<hr>

<p>EDIT:
In the integer programming literature, <em>binary</em> 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.</p>

CC BY-SA 3.0
2016-05-04T17:49:07.410Z
Oh, now it makes infinitely more sense. However, the question is still too vague. See e.g. http://meta.cstheory.stackexchange.com/a/2880 for a discussion of “natural”.
Emil Jeřábek
CC BY-SA 3.0
2016-05-04T18:23:24.873Z
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".
Lagerbaer
CC BY-SA 3.0
2016-05-04T22:36:45.777Z
When the variables are 0-1 it is not called binary, it is called "0-1 Integer Programming".
Kaveh
CC BY-SA 3.0
2016-05-04T22:42:11.620Z
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?
Kaveh
CC BY-SA 3.0
2016-05-05T03:57:20.020Z
The Gilmore-Gomory relaxation for bin packing/cutting stock problem has variables that can be arbitrary non-negative integers.
Sasho Nikolov
CC BY-SA 3.0
2016-05-07T15:44:21.147Z
This is not a research-level question. Just refer to nearly any book on integer programming for examples.
Austin Buchanan
<np-hardness><integer-programming>
What are some example problems for integer programming that are *not binary*
Lagerbaer
# What are some example problems for integer programming that are *not binary*

(Asked by: username_0 on 2016-05-03)

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.

**Tags:** np-hardness, integer-programming

> **Comments:**
> **username_1**: Oh, now it makes infinitely more sense. However, the question is still too vague. See e.g. http://meta.cstheory.stackexchange.com/a/2880 for a discussion of “natural”.  
> **username_0**: 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".  
> **username_2**: When the variables are 0-1 it is not called binary, it is called "0-1 Integer Programming".  
> **username_2**: 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?  
> **username_3**: The Gilmore-Gomory relaxation for bin packing/cutting stock problem has variables that can be arbitrary non-negative integers.  
> **username_4**: This is not a research-level question. Just refer to nearly any book on integer programming for examples.  

---

## 1 answers

### Answer by username_5 on 2018-12-19. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

