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

Publication

Faster Algorithms for Integer Programs with Block Structure

Friedrich Eisenbrand, Kim-Manuel Klein, Christoph Hunkenschröder
2018
Conference Papers

Résumé

We consider integer programming problems max {c^Tx : A x = b, l

Source officielle

https://infoscience.epfl.ch/entities/publication/0ac0dd1b-cd65-4305-b2f9-bf03ec8accb1

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Friedrich Eisenbrand, Kim-Manuel Klein, Christoph Hunkenschröder
2018
Conference Papers

Résumé

We consider integer programming problems max {c^Tx : A x = b, l

Source officielle

https://infoscience.epfl.ch/entities/publication/0ac0dd1b-cd65-4305-b2f9-bf03ec8accb1

À propos de ce résultat

Concepts associés (32)

Matrice inversible

En mathématiques et plus particulièrement en algèbre linéaire, une matrice inversible (ou régulière ou encore non singulière) est une matrice carrée A pour laquelle il existe une matrice B de même taille n avec laquelle les produits AB et BA sont égaux à la matrice identité. Dans ce cas la matrice B est unique, appelée matrice inverse de A et notée B = A. Cette définition correspond à celle d’élément inversible pour la multiplication dans l’anneau des matrices carrées associé.

Matrice par blocs

vignette|Un matrice présente une structure par blocs si l'on peut isoler les termes non nuls dans des sous-matrices (ici la structure « diagonale par blocs » d'une réduite de Jordan). On appelle matrice par blocs une matrice divisée en blocs à partir d'un groupement quelconque de termes contigus de sa diagonale. Chaque bloc étant indexé comme on indicerait les éléments d'une matrice, la somme et le produit de deux matrices partitionnées suivant les mêmes tailles de bloc, s'obtiennent avec les mêmes règles formelles que celles des composantes (mais en veillant à l'ordre des facteurs dans les produits matriciels!).

Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières.

Afficher plus

Publications associées (35)

Afficher plus

Faster Algorithms for Integer Programs with Block Structure

Graph Chatbot

Convex Computation of Value-at-risk Bounds for Stochastic Processes

Integer Linear Programming for Unsupervised Training Set Selection in Molecular Machine Learning

Spectral Estimators for High-Dimensional Matrix Inference