**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 GraphSearch.

Concept# Linear programming relaxation

Summary

In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable.
For example, in a 0–1 integer program, all constraints are of the form
The relaxation of the original integer program instead uses a collection of linear constraints
The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.
Consider the set cover problem, the linear programming relaxation of which was first considered by . In this problem, one is given as input a family of sets F = {S0, S1, ...}; the task is to find a subfamily, with as few sets as possible, having the same union as F.
To formulate this as a 0–1 integer program, form an indicator variable xi for each set Si, that takes the value 1 when Si belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints
(that is, only the specified indicator variable values are allowed) and, for each element ej of the union of F,
(that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function
The linear programming relaxation of the set cover problem describes a fractional cover in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized.
As a specific example of the set cover problem, consider the instance F = a, b}, {b, c}, {a, c. There are three optimal set covers, each of which includes two of the three given sets.

Official source

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.

Related courses (11)

Related concepts (11)

MGT-483: Optimal decision making

This course introduces the theory and applications of optimization. We develop tools and concepts of optimization and decision analysis that enable managers in manufacturing, service operations, marke

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

CS-627: Algorithmic Toolbox

This course covers numerous powerful algorithmic techniques (greedy, local search, linear programming, multiplicative weight update, ...). The concepts are studied in clean and simple settings so as t

Related units (7)

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex).

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch. This description assumes the ILP is a maximization problem.

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 publications (369)

Related people (70)

Related lectures (104)

Exact methods: Gomory cutsMOOC: Optimization: principles and algorithms - Linear optimization

Covers the application of Gomory cuts in linear programming problems.

Branch and Bound: Optimization Techniques

Covers the Branch and Bound optimization technique with LP Relaxation and Integral Optimal Solutions.

Optimal Decision Making: Applications of Discrete Optimization

Explores optimal decision making through discrete optimization, emphasizing binary variables and practical applications.

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024Maryna Viazovska, Matthew De Courcy-Ireland, Maria Margarethe Dostert

We prove that the Cohn-Elkies linear programming bound for sphere packing is not sharp in dimension 6. The proof uses duality and optimization over a space of modular forms, generalizing a construction of Cohn- Triantafillou [Math. Comp. 91 (2021), pp. 491 ...