Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Mixed-Integer Linear Programming: Formulations and Applications

In course

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, marketing, transportation and finance to transform data into ...

Description

This lecture covers the motivation behind mixed-integer linear programming (MILP) by highlighting the need to model practical problems with discrete variables. It explains the concept of binary variables in LPs, the formulation of mixed-integer LPs, and their applications in decision-making problems such as the 0-1 knapsack problem and the assignment problem. The lecture also delves into the relationships between events, disjunctive constraints, and forcing constraints in MILPs. It concludes with a discussion on the strength of LP relaxations, the ideal formulation for an integer problem, and the importance of formulating MILPs effectively.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Daniel Kuhn

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Combinatorial optimization

Related concepts (32)

Integer programming

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.

Linear programming

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Linear programming relaxation

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.

Branch and cut

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.

Stokes' theorem

Stokes' theorem, also known as the Kelvin–Stokes theorem after Lord Kelvin and George Stokes, the fundamental theorem for curls or simply the curl theorem, is a theorem in vector calculus on . Given a vector field, the theorem relates the integral of the curl of the vector field over some surface, to the line integral of the vector field around the boundary of the surface. The classical theorem of Stokes can be stated in one sentence: The line integral of a vector field over a loop is equal to the flux of its curl through the enclosed surface.

Related lectures (51)

Approximation Algorithms

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Discrete Optimization: Relaxation MOOC: Optimization: principles and algorithms - Network and discrete optimization

Explores solving discrete optimization problems by relaxing integrality constraints.

Fundamental Groups

Explores fundamental groups, homotopy classes, and coverings in connected manifolds.

Hedging for LPs

Covers the concept of hedging for Linear Programs and the simplex method, focusing on minimizing costs and finding optimal solutions.

Exact methods: Branch and Bound MOOC: Optimization: principles and algorithms - Network and discrete optimization