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. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists. Linear programs are problems that can be expressed in canonical form as : \begin{align} & \text{F

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.

Related publications

Related people

Related units

Related concepts

Related courses

Related lectures

Summary

Official source

About this result

Related publications (100)

Related publications

Related people (98)

Related people

Related units (41)

Related units

Related concepts (81)

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternative

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 wa

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets

Related concepts

Related courses (143)

Related courses

Related lectures (405)

Related lectures

The number of positive solutions of a non-linear problem with discontinuous non-linearity

Jacques Douchet

Cambridge, Royal Society of Edinburgh Scotland Foundation1981

Some constructions of maximal witness codes

Nikolaos Makriyannis, Bertrand Meyer

Given a code C is an element of F-2(n) and a word c is an element of C, a witness of c is a subset W subset of {, 1 ... , n} of coordinate positions such that c differs from any other codeword c' is an element of C on the indices in W. If any codeword posseses a witness of given length w, C is called a w-witness code. This paper gives new constructions of large w-witness codes and proves with a numerical method that their sizes are maximal for certain values of n and w. Our technique is in the spirit of Delsarte's linear programming bound on the size of classical codes and relies on the Lovasz theta number, semidefinite programming, and reduction through symmetry.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

The Gene Family-Free Median of Three

Metin Balaban

The gene family-free framework for comparative genomics aims at developing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We show that the corresponding computational problem is MAX SNP-hard and we present a 0-1 linear program for its exact solution. The result of this program is a median genome with median genes associated to extant genes, in which median adjacencies are assumed to define positional orthologs. We demonstrate through simulations and comparison with the OMA orthology database that the herein presented method is able compute accurate medians and positional orthologs for genomes comparable in size of bacterial genomes.

Springer AG2016

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternative

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 wa

ME-454: Modelling and optimization of energy systems

The goal of the lecture is to present and apply techniques for the modelling and the thermo-economic optimisation of industrial process and energy systems. The lecture covers the problem statement, the solving methods for the simulation and the single and multi-objective optimisation problems.

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 insights for making better decisions.

MATH-265: Introduction to optimization and operations research

Introduction to major operations research models and optimization algorithms