**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 GraphSearch.

Concept# Feasible region

Summary

In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.
For example, consider the problem of minimizing the function with respect to the variables and subject to and Here the feasible set is the set of pairs (x, y) in which the value of x is at least 1 and at most 10 and the value of y is at least 5 and at most 12. The feasible set of the problem is separate from the objective function, which states the criterion to be optimized and which in the above example is
In many problems, the feasible set reflects a constraint that one or more variables must be non-negative. In pure integer programming problems, the feasible set is the set of integers (or some subset thereof). In linear programming problems, the feasible set is a convex polytope: a region in multidimensional space whose boundaries are formed by hyperplanes and whose corners are vertices.
Constraint satisfaction is the process of finding a point in the feasible region.
Convex optimization
A convex feasible set is one in which a line segment connecting any two feasible points goes through only other feasible points, and not through any points outside the feasible set. Convex feasible sets arise in many types of problems, including linear programming problems, and they are of particular interest because, if the problem has a convex objective function that is to be maximized, it will generally be easier to solve in the presence of a convex feasible set and any local optimum will also be a global optimum.
If the constraints of an optimization problem are mutually contradictory, there are no points that satisfy all the constraints and thus the feasible region is the empty set.

Official source

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 MOOCs (6)

Related people (2)

Related concepts (22)

Related publications (9)

Related courses (12)

Related lectures (177)

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Optimization: principles and algorithms - Linear optimization

Introduction to linear optimization, duality and the simplex algorithm.

Optimization: principles and algorithms - Network and discrete optimization

Introduction to network optimization and discrete optimization

Constraint (mathematics)

In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy. There are several types of constraints—primarily equality constraints, inequality constraints, and integer constraints. The set of candidate solutions that satisfy all constraints is called the feasible set. The following is a simple optimization problem: subject to and where denotes the vector (x1, x2). In this example, the first line defines the function to be minimized (called the objective function, loss function, or cost function).

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.

Feasible region

In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potentially including inequalities, equalities, and integer constraints. This is the initial set of candidate solutions to the problem, before the set of candidates has been narrowed down.

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, marke

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

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

We derive the branch ampacity constraint associated to power losses for the convex optimal power flow (OPF) model based on the branch flow formulation. The branch ampacity constraint derivation is mot

Mario Paolone, Antonio Zecchino, Zhao Yuan

Frequency response and voltage support are vital ancillary services for power grids. In this paper, we design and experimentally validate a real-time control framework for battery energy storage syste

2021Diego Felipe Paez Granados, Chen Yang

This work proposes an autonomous docking control for nonholonomic constrained mobile robots and applies it to an intelligent mobility device or wheelchair for assisting the user in approaching resting

2021Linear Programming: Weighted Bipartite MatchingCS-450: Advanced algorithms

Covers linear programming, weighted bipartite matching, and vertex cover problems in optimization.

Simplex Algorithm: Graphical MethodMOOC: Optimization: principles and algorithms - Linear optimization

Illustrates the simplex algorithm through a graphical method to find optimal solutions.

Gradient Descent: Optimization and Constraints

Discusses gradient descent for optimization with equality constraints and iterative convergence criteria.