Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Integer programming
Summary
An integer programming 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. 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.
In integer linear programming, the canonical form is distinct from the standard form. An integer linear program in canonical form is expressed thus (note that it is the vector which is to be decided):
and an ILP in standard form is expressed as
where are vectors and is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables () and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.
The plot on the right shows the following problem.
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 and which both have an objective value of 2. The unique optimum of the relaxation is 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.
The following is a reduction from minimum vertex cover to integer programming that will serve as the proof of NP-hardness.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (22)
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization.
Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
ME-602: Modelling, optimisation, design and analysis of integrated energy systems
The student will learn advanced concepts in the field of process integration, process modeling and optimization for the design of integrated energy systems: Life cycle energy analysis.
MATH-504: Integer optimisation
The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s
Related lectures (141)
Linear Programming Basics
Explores linear programming basics, including basic solutions, feasible solutions, optimal solutions, and challenges in solving integer programming problems.
Energy Conversion Systems Optimization
Explores energy conversion systems optimization through heat recovery and mixed integer linear programming.
Optimal Decision Making: Applications of Discrete Optimization
Explores optimal decision making through discrete optimization, emphasizing binary variables and practical applications.
Related publications (510)
Related people (99)
Related units (9)
Related concepts (17)
NP-completeness
In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
Cutting-plane method
In mathematical optimization, the cutting-plane method is any of a variety of optimization methods that iteratively refine a feasible set or objective function by means of linear inequalities, termed cuts. Such procedures are commonly used to find integer solutions to mixed integer linear programming (MILP) problems, as well as to solve general, not necessarily differentiable convex optimization problems. The use of cutting planes to solve MILP was introduced by Ralph E. Gomory.
Branch and bound
Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.
Related MOOCs (7)
Linear and Discrete Optimization
This advanced undergraduate course treats basic principles on linear programming like the simplex algorithm, its complexity, and duality. Furthermore it gives an introduction on discrete optimization
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.
Optimization: principles and algorithms - Linear optimization
Introduction to linear optimization, duality and the simplex algorithm.