Integerohjelmointi

Integerohjelmointi, or integer programming in English, is a subfield of mathematical optimization that deals with the problem of finding the optimal integer solution to a linear program. In a standard linear program, we seek to maximize or minimize a linear objective function subject to linear equality or inequality constraints, where the decision variables can take any real value. In integer programming, however, one or more of these decision variables are restricted to be integers. If all variables must be integers, it is called pure integer programming. If some variables must be integers and others can be real, it is called mixed-integer programming.

The addition of integer constraints significantly complicates the problem. While linear programming problems can often be solved efficiently using algorithms like the simplex method, integer programming problems are generally NP-hard, meaning that finding an optimal solution can be computationally very difficult, especially for large instances. Several algorithms exist to tackle integer programming problems, including branch and bound, cutting plane methods, and branch and cut methods, which combine aspects of both.

Integer programming has a wide range of applications in various fields. Examples include resource allocation, scheduling, facility location, crew rostering, and network design. The ability to model discrete choices or quantities makes it a powerful tool for solving complex real-world decision-making problems where fractional solutions are not meaningful.