Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Discrete optimization
Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. Three notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures integer programming constraint programming These branches are all closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.g. shortest path) or constraint programs, any constraint program can be formulated as an integer program and vice versa, and constraint and integer programs can often be given a combinatorial interpretation.
Official source
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 courses (10)
MATH-600: Optimization and simulation
Master state-of-the art methods in optimization with heuristics and simulation.
Work involves:
- reading the material beforehand
- class hours to discuss the material and solve problems
- homework
MATH-513: Metric embeddings
The course aims to introduce the basic concepts and results on metric embeddings, or more precisely on approximate embeddings. This area has been under rapid development since the 90's and it has stro
MATH-261: Discrete optimization
This course is an introduction to linear and discrete optimization.
Warning: This is a mathematics course! While much of the course will be algorithmic in nature, you will still need to be able to p
Related lectures (35)
Optimal Decision Making: Applications of Discrete Optimization
Explores optimal decision making through discrete optimization, emphasizing binary variables and practical applications.
Optimization for Machine Learning: Accelerated Gradient Descent
Explores Accelerated Gradient Descent and Gradient-free optimization in machine learning, discussing their applications and convergence rates.
Statistical Physics: Spin Glasses & Optimization
Explores the Curie-Weiss model, spin glasses, and optimization problems in statistical physics.
Related publications (18)
Robot Learning using Tensor Networks
In various robotics applications, the selection of function approximation methods greatly influences the feasibility and computational efficiency of algorithms. Tensor Networks (TNs), also referred to as tensor decomposition techniques, present a versatile ...
EPFL2024Probabilistic methods for neural combinatorial optimization
The monumental progress in the development of machine learning models has led to a plethora of applications with transformative effects in engineering and science. This has also turned the attention of the research community towards the pursuit of construc ...
EPFL2023Streaming and Matching Problems with Submodular Functions
Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...
EPFL2022Related concepts (4)
Applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathematical science and specialized knowledge. The term "applied mathematics" also describes the professional specialty in which mathematicians work on practical problems by formulating and studying mathematical models.
Continuous or discrete variable
In mathematics and statistics, a quantitative variable may be continuous or discrete if they are typically obtained by measuring or counting, respectively. If it can take on two particular real values such that it can also take on all real values between them (even values that are arbitrarily close together), the variable is continuous in that interval. If it can take on a value such that there is a non-infinitesimal gap on each side of it containing no values that the variable can take on, then it is discrete around that value.
Combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.