Publication

On the number of iterations of the simplex method.

Thomas Liebling
1972
Conference Papers

Abstract

RENYI and SULANKE studied the properties of the convex hull of a set of points thrown at random independently of each other. Carnal generalized their results concerning the asymptotic behaviour of the number of faces of that convex hull as the number of points increases. The present work connects those results with the mean number of pivot steps used by the Simplex Method to solve certain Linear Programming Problems. This is made possible through the polar interpretation of the LP-Problems. Monte Carlo Simulation confirmed the results. Aside from statistical applications, it is felt that this kind of an approach will make it possible to characterize optimization problems with polyhedral feasible sets as to their benevolence.

Official source

https://infoscience.epfl.ch/entities/publication/ac9a9171-813f-475a-8fed-55943808f2d2

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.

Thomas Liebling
1972
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/ac9a9171-813f-475a-8fed-55943808f2d2

About this result

Related concepts (31)

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.

Simplex algorithm

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope.

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.

Related publications (18)

On the number of iterations of the simplex method.

Chat with Graph Search

A Strong Linear Programming Relaxation for Weighted Tree Augmentation

Optimization of Pelton turbines start-up considering fatigue damage via a fracture mechanics model

Robust Optimization Application of Cchp System Planning Based on Typical Day Selection: Combining 3e (Energy, Environmental, Economy) Analysis and Global Sensitivity Analysis