Integer programming

An integer programming, also known as integer optimization, problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. 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.

Integer programming is NP-complete (the difficult part is showing the NP membership). In particular, the special case of 0–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.

maximize𝐱∈ℤn𝐜T𝐱subject toA𝐱≤𝐛,𝐱≥𝟎

and an ILP in standard form is expressed as

A∈ℝm×n is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables ((1,2) and G=(V,E) be an undirected graph. Define a linear program as follows:

v∈C and to 0 for any xi, are constrained to be integers, while other variables are allowed to be non-integers.

Zero–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 variables. For example, given an integer variable, x=x1+2x2+4x3+⋯+2⌊log2U⌋x⌊log2U⌋+1.

Applications

edit

There are two main reasons for using integer variables when modeling problems as a linear program:

1. Some integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars.
2. Other integer variables represent decisions (e.g. whether to include an edge in a graph) and so should only take on the value 0 or 1.

These considerations occur frequently in practice and so integer linear programming can be used in many applications areas, some of which are briefly described below.

Production planning

edit

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. land, 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

edit

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–one programming technique has been successfully applied to solve a project selection problem in which projects are mutually exclusive and/or technologically interdependent.

Territorial partitioning

edit

Territorial partitioning or districting problems consist of 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

edit

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. This requires optimizing both the topology of the network along with 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

edit

The task of frequency planning in GSM mobile networks involves distributing available frequencies across the antennas so that users can be served and interference is minimized between the antennas. This problem can be formulated as an integer linear program in which binary variables indicate whether a frequency is assigned to an antenna.

Other applications

edit

• Cash flow matching
• Energy system optimization
• UAV guidance
• Transit map layouting

Algorithms

edit

The naive way to solve an ILP is to simply remove the constraint that x is integer, solve the corresponding LP (called the LP relaxation of the ILP), and then round the entries of the solution to the LP relaxation. But, not only may this solution not be optimal, it may not even be feasible; that is, it may violate some constraint.

Using total unimodularity

edit

While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form A and 𝐱 be an arbitrary basic feasible solution . Since 𝐱0=[xn1,xn2,⋯,xnj] be the elements corresponding to the basis columns for the basic solution A with linearly independent columns such that B is square, det⁡(B)=±1. Also, since B−1=Badjdet⁡(B)=±Badj. Here B is integral. Therefore, A 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 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.

Exact algorithms for a small number of variables

edit

Suppose 𝐱 satisfying 𝐛. If n (the number of variables) is a fixed constant, then the feasibility problem can be solved in time polynomial in m and log V. This is trivial for the case n=1. The case n=2 was solved in 1981 by Herbert Scarf. The general case was solved in 1983 by Hendrik Lenstra, combining ideas by László Lovász and Peter van Emde Boas. Doignon's theorem asserts that an integer program is feasible whenever every subset of n, but possibly doubly exponential in 𝐱 is obvious, or the value of nO(n)⋅(m⋅log⁡V)O(1).

Frank and Tardos presented an improved algorithm with run-time (log⁡n)O(n)⋅(m⋅log⁡V)O(1).

These algorithms can also be used for mixed integer linear programs (MILP) - programs in which some variables are integer and some variables are real. The original algorithm of Lenstra has run-time 2O(nlog⁡n) or to A has vertices corresponding to columns of d of A. Let A. Let d. That is, for some computable function f(a,d)nk. In particular, the time is independent of the right-hand side n of variables is a parameter, here the number Papadimitriou, Christos H. (1981-10-01). "On the complexity of integer programming". J. ACM. 28 (4): 765–768. doi:10.1145/322276.322287. hdl:1721.1/148979. ISSN 0004-5411.

↑ "Mixed-Integer Linear Programming (MILP): Model Formulation" (PDF). Retrieved 16 April 2018.

↑ Williams, H.P. (2009). Logic and integer programming. International Series in Operations Research & Management Science. Vol. 130. ISBN 978-0-387-92280-5.

↑ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01). "Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming". Renewable Energy. 35 (1): 151–156. Bibcode:2010REne...35..151M. doi:10.1016/j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.

↑ Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). "Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming". Aerospace Science and Technology. 50: 149–160. Bibcode:2016AeST...50..149R. doi:10.1016/j.ast.2015.12.021. ISSN 1270-9638.

↑ Lenstra, H. W. (1983-11-01). "Integer Programming with a Fixed Number of Variables". Mathematics of Operations Research. 8 (4): 538–548. doi:10.1287/moor.8.4.538. ISSN 0364-765X.

↑ Kannan, Ravi (1987-08-01). "Minkowski's Convex Body Theorem and Integer Programming". Mathematics of Operations Research. 12 (3): 415–440. doi:10.1287/moor.12.3.415. ISSN 0364-765X. S2CID 495512.

↑ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 102–108. ISBN 978-1-57735-770-4.{{cite journal}}: CS1 maint: periodical has ISBN (link)

↑ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "A parameterized strongly polynomial algorithm for block structured integer programs". In Chatzigiannakis, Ioannis; Kaklamanis, Christos; Marx, Dániel; Sannella, Donald (eds.). 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9–13, 2018, Prague, Czech Republic. LIPIcs. Vol. 107. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 85:1–85:14. arXiv:1802.05859. doi:10.4230/LIPICS.ICALP.2018.85.