Skip to content

Latest commit

 

History

History
115 lines (98 loc) · 7.87 KB

Discrete Optimization.md

File metadata and controls

115 lines (98 loc) · 7.87 KB

Discrete Optimization

Discrete optimization or combinatorial optimization means searching for an optimal solution in a finite or countably infinite set of potential solutions. Optimality is defined with respect to some criterion function, which is to be minimized or maximized.

Integer Optimization

Integer-programming models arise in practically every area of application of mathematical programming.

Branch and Bound Algorithms

Hierarchies of Integer Programming Relaxations

Mathematical programming relaxations of integer programming formulations are a popular way to apply convex optimization techniques to hard combinatorial optimization problems. Such relaxations can be made closer to their integer programming counterparts by adding constraints; a systematic way to achieve this is via hierarchies of relaxations. Several such hierarchies are well-studied in the literature: Lovasz-Schrijver, Sherali-Adams and the Parrilo-Lasserre sum-of-squares (SoS) hierarchy.

Mixed Integer Optimization

Robert Weismantel, Head of the Mixed Integer Optimization team at ETHZ, said:

Mixed Integer Optimization deals with mathematical optimization problems with two types of variables: variables taking values in an integer domain, and variables taking values in a continuous domain. The fact that Mixed Integer Optimization problems naturally appear in many contexts has led to an increased interest in the design of strong algorithms for different variants of the problem.

Combinatorial Optimization

Rico Zenklusen, Head of the Combinatorial Optimization team at ETHZ, said:

Technically speaking, Combinatorial Optimization is concerned with finding an optimal or close to optimal solution among a finite collection of possibilities. The finite set of possible solutions is typically described through mathematical structures, like graphs, matroids or independence systems. The focus in Combinatorial Optimization lies on efficient algorithms which, more formally, means algorithms with a running time bounded by a polynomial in the input size. Therefore, two of the arguably most prominent questions in Combinatorial Optimization are:

  • How quickly can one find a single (or all) optimal solution(s) of a given problem?
  • When dealing with a problem where, due to complexity-​theoretic reasons, it is unlikely that an optimal solution can be found efficiently: What is the best solution quality that an efficient algorithm can guarantee?

Optimziation over Graph