Integer programming: Difference between revisions

Revision as of 21:02, 5 September 2023

Revision as of 12:34, 13 October 2023

Line 1:

{{Short description|A mathematical optimization problem restricted to integers}}

An '''integer programming''' problem is a [[mathematical optimization]] or [[Constraint satisfaction problem|feasibility]] program in which some or all of the variables are restricted to be [[integer]]s. In many settings the term refers to '''integer [[linear programming]]''' (ILP), in which the [[objective function]] and the constraints (other than the integer constraints) are [[Linear function (calculus)|linear]].

Integer programming is [[NP-complete]]{{Reference needed|date=May 2023}}. In particular, the special case of 0-10–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of [[Karp's 21 NP-complete problems]].

If some decision variables are not discrete, the problem is known as a '''mixed-integer programming''' problem.<ref>{{cite web |url=http://macc.mcmaster.ca/maccfiles/chachuatnotes/07-MILP-I_handout.pdf |title=Mixed-Integer Linear Programming (MILP): Model Formulation |access-date=16 April 2018}}</ref>

Line 42:

</math>

The feasible integer points are shown in red, and the red dashed lines indicate their convex hull, which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points <math>(1,2)</math> and <math>(2,2)</math> whichthat both have an objective value of 2. The unique optimum of the relaxation is <math>(1.8,2.8)</math> with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP.

==Proof of NP-hardness==

Line 62:

'''Mixed-integer linear programming''' ('''MILP''') involves problems in which only some of the variables, <math>x_i</math>, are constrained to be integers, while other variables are allowed to be non-integers.

'''Zero-oneZero–one linear programming''' (or '''binary integer programming''') involves problems in which the variables are restricted to be either 0 or 1. Any bounded integer variable can be expressed as a combination of [[binary data|binary variables]].<ref>{{cite book|last=Williams|first=H.P.|title=Logic and integer programming|series=International Series in Operations Research & Management Science|year=2009|volume=130|isbn= 978-0-387-92280-5}}</ref> For example, given an integer variable, <math>0\le x\le U</math>, the variable can be expressed using <math>\lfloor \log_2U\rfloor+1</math> binary variables:

:<math display=block>

x = x_1+2x_2+4x_3+\cdots+2^{\lfloor \log_2U\rfloor}x_{\lfloor \log_2U\rfloor+1}.

Line 75:

===Production planning===

Mixed-integer programming has many applications in industrial productions, including job-shop modelling. One important example happens in agricultural [[production planning]] and involves determining production yield for several crops that can share resources (e.g. Landland, labor, capital, seeds, fertilizer, etc.). A possible objective is to maximize the total production, without exceeding the available resources. In some cases, this can be expressed in terms of a linear program, but the variables must be constrained to be integer.

===Scheduling===

These problems involve service and vehicle scheduling in transportation networks. For example, a problem may involve assigning buses or subways to individual routes so that a timetable can be met, and also to equip them with drivers. Here binary decision variables indicate whether a bus or subway is assigned to a route and whether a driver is assigned to a particular train or subway. The zero-onezero–one programming technique has been successfully applied to solve a project selection problem in which projects are mutually exclusive and/or technologically interdependent. It is used in a special case of integer programming, in which all the decision variables are integers. ItVariable can assume only the values either as zero or one.

===Territorial partitioning===

Territorial partitioning or districting problemproblems consistsconsist inof partitioning a geographical region into districts in order to plan some operations while considering different criteria or constraints. Some requirements for this problem are: contiguity, compactness, balance or equity, respect of natural boundaries, and socio-economic homogeneity. Some applications for this type of problem include: political districting, school districting, health services districting and waste management districting.

===Telecommunications networks===

The goal of these problems is to design a network of lines to install so that a predefined set of communication requirements are met and the total cost of the network is minimal.<ref>{{cite web|last1=Borndörfer|first1=R.|last2=Grötschel|first2=M.|author2-link= Martin Grötschel |title=Designing telecommunication networks by integer programming|url=http://www.zib.de/groetschel/teaching/SS2012/120503Vorlesung-DesigningTelcomNetworks-reduced.pdf|year=2012}}</ref> This requires optimizing both the topology of the network along with the setting the capacities of the various lines. In many cases, the capacities are constrained to be integer quantities. Usually there are, depending on the technology used, additional restrictions that can be modeled as linear inequalities with integer or binary variables.

===Cellular networks===

Line 120:

===Exact algorithms===

When the matrix <math>A</math> is not totally unimodular, there are a variety of algorithms that can be used to solve integer linear programs exactly. One class of algorithms are [[Cutting-plane method|cutting plane methods]], which work by solving the LP relaxation and then adding linear constraints that drive the solution towards being integer without excluding any integer feasible points.

Another class of algorithms are variants of the [[branch and bound]] method. For example, the [[branch and cut]] method that combines both branch and bound and cutting plane methods. Branch and bound algorithms have a number of advantages over algorithms that only use cutting planes. One advantage is that the algorithms can be terminated early and as long as at least one integral solution has been found, a feasible, although not necessarily optimal, solution can be returned. Further, the solutions of the LP relaxations can be used to provide a worst-case estimate of how far from optimality the returned solution is. Finally, branch and bound methods can be used to return multiple optimal solutions.

Line 149:

* The original algorithm of Lenstra<ref name=":0" /> had run-time <math>2^{O(n^3)}\cdot (m\cdot \log V)^{O(1)}</math>.

* Kannan<ref>{{Cite journal|last=Kannan|first=Ravi|date=1987-08-01|title=Minkowski's Convex Body Theorem and Integer Programming|url=https://pubsonline.informs.org/doi/abs/10.1287/moor.12.3.415|journal=Mathematics of Operations Research|volume=12|issue=3|pages=415–440|doi=10.1287/moor.12.3.415|s2cid=495512 |issn=0364-765X}}</ref> presented an improved algorithm with run-time <math>n^{O(n)}\cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Goemans|first1=Michel X.|author1link = Michel Goemans|last2=Rothvoss|first2=Thomas|date=2020-11-07|title=Polynomiality for Bin Packing with a Constant Number of Item Types|journal=[[Journal of the ACM]]|volume=67|issue=6|pages=38:1–38:21|doi=10.1145/3421750|hdl=1721.1/92865 |s2cid=227154747 |issn=0004-5411|doi-access=free}}</ref>

* Frank and Tardos<ref>{{Cite journal|last1=Frank|first1=András|last2=Tardos|first2=Éva|date=1987-03-01|title=An application of simultaneous diophantine approximation in combinatorial optimization|url=https://doi.org/10.1007/BF02579200|journal=Combinatorica|language=en|volume=7|issue=1|pages=49–65|doi=10.1007/BF02579200|s2cid=45585308|issn=1439-6912}}</ref> presented an improved algorithm with run-time <math>n^{2.5 n} \cdot 2^{O(n)} \cdot (m\cdot \log V)^{O(1)}</math>.<ref>{{Cite journal|last1=Bliem|first1=Bernhard|last2=Bredereck|first2=Robert|last3=Niedermeier|first3=Rolf|author3-link=Rolf Niedermeier|date=2016-07-09|title=Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels|url=https://dl.acm.org/doi/abs/10.5555/3060621.3060636|journal=Proceedings of the Twenty-Fifth [[International Joint Conference on Artificial Intelligence]]|series=IJCAI'16|___location=New York, New York, USA|publisher=AAAI Press|pages=102–108|isbn=978-1-57735-770-4}}</ref><ref>{{Cite book|last1=Bredereck|first1=Robert|last2=Kaczmarczyk|first2=Andrzej|last3=Knop|first3=Dušan|last4=Niedermeier|first4=Rolf|title=Proceedings of the 2019 ACM Conference on Economics and Computation |chapter=High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming |date=2019-06-17|chapter-url=https://doi.org/10.1145/3328526.3329649|series=EC '19|___location=Phoenix, AZ, USA|publisher=Association for Computing Machinery|pages=505–523|doi=10.1145/3328526.3329649|isbn=978-1-4503-6792-9|s2cid=195298520}}</ref>{{Rp|Prop.8}}

* Dadush<ref>Dadush, Daniel (2012-06-14). [https://homepages.cwi.nl/~dadush/papers/dadush-thesis.pdf "Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation].</ref> presented an improved algorithm with run-time <math>n^n \cdot 2^{O(n)} \cdot (m \cdot \log V)^{O(1)}</math>.

Line 169:

== Sparse integer programming ==

It is often the case that the matrix <math>A</math> whichthat defines the integer program is ''[[Sparse matrix|sparse]]''. In particular, this occurs when the matrix has a [[Block matrix|block structure]], which is the case in many applications. The sparsity of the matrix can be measured as follows. The ''graph'' of <math>A</math> has vertices corresponding to columns of <math>A</math>, and two columns form an edge if <math>A</math> has a row where both columns have nonzero entries. Equivalently, the vertices correspond to variables, and two variables form an edge if they share an inequality. The ''sparsity measure'' <math>d</math> of <math>A</math> is the minimum betweenof the [[tree-depth]] of the graph of <math>A</math> and the [[tree-depth]] of the graph of the transpose of <math>A</math>. Let <math>a</math> be the ''numeric measure'' of <math>A</math> defined as the maximum absolute value of any entry of <math>A</math>. Let <math>n</math> be the number of variables of the integer program. Then it was shown in 2018<ref>{{Cite journal|last1=Koutecký|first1=Martin|last2=Levin|first2=Asaf|last3=Onn|first3=Shmuel|date=2018|others=Michael Wagner|title=A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs|url=http://drops.dagstuhl.de/opus/volltexte/2018/9089/|language=en|pages=14 pages|doi=10.4230/LIPICS.ICALP.2018.85|arxiv=1802.05859|s2cid=3336201}}</ref> that integer programming can be solved in [[strongly polynomial]] and [[fixed-parameter tractable]] time parameterized by <math>a</math> and <math>d</math>. That is, for some computable function <math>f</math> and some constant <math>k</math>, integer programming can be solved in time <math>f(a,d)n^k</math>. In particular, the time is independent of the right-hand side <math>b</math> and objective function <math>c</math>. Moreover, in contrast to the classical result of Lenstra, where the number <math>n</math> of variables is a parameter, here the number <math>n</math> of variables is a variable part of the input.

==See also==