Publication

Integer Programming Approaches

Dominique de Werra
2023

Abstract

Integer programming has been widely used to solve round-robin tournament scheduling problems, either as standalone formulations or embedded in decomposition strategies. Methods applied to sports scheduling problems include branch-and-bound, branch-and-cut, Benders decomposition, and column generation. They are used to solve scheduling problems in real-life sports leagues and to tackle theoretical problems such as the traveling tournament problem or break minimization. We illustrate how integer programming can be used to model and solve a typical round-robin tournament scheduling problem. The traveling tournament problem with predefined venues is used as the motivation for studying integer programming formulations of round-robin tournament scheduling problems.

Official source

https://infoscience.epfl.ch/entities/publication/b5a79310-fd6f-44a4-b81f-598e20c8e450

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.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Dominique de Werra
2023

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/b5a79310-fd6f-44a4-b81f-598e20c8e450

About this result

Related concepts (29)

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.

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.

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.

Related publications (9)

Integer Programming Approaches

Chat with Graph Search

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

A Reinforcement Learning Approach to Train Routing and Scheduling

Globally Optimal Cell Tracking using Integer Programming