How do you define and identify the feasibility region in optimization problems?

A couple of comments on the "imprecise" words used here: 1. I would prefer not to use the term "optimization problems." Problems can be modeled through an optimization formulation. 2. An optimization formulation can have multiple best solutions, referred to as 'optimal solutions' in the operations research (OR) field. 3. OR guys use the term "feasible region", not "feasibility region." 4. A feasible region is the set of all solutions that satisfy the constraints in the optimization formulation.

The feasibility (feasible) region represents the set of all possible points that satisfy a given set of constraints without violating any of them. Optimization problems that include constraints are significantly more critical than those without, primarily because most real-world problems naturally come with constraints. However, it is sometimes possible to reformulate constrained optimization problems as unconstrained ones. These constraints can be inequalities or equations that define the limits within which an optimal solution can exist. This region is crucial because it helps to identify the bounds of possible solutions, ensuring that solutions are practical and adhere to the specified constraints of the problem.

For example to optimize production schedules, the feasible region represents all combinations of production quantities for various products that adhere to constraints such as machine capacities, labor availability, and raw material availability. Any combination of production quantities that falls within these constraints constitutes a feasible solution within the feasible region.

The feasibility region in optimization refers to the set of all possible solutions that satisfy a given set of constraints. It represents the space within which an optimal solution can be found. In mathematical terms, it’s the region in a coordinate system where all the constraints overlap, defining the boundaries of potential solutions. Understanding the feasibility region is crucial in optimization problems, as it helps to identify whether a solution exists and where the best possible outcome might lie.

the feasible region is defined by the set of values that satisfy all specified constraints in an optimization problem. Visualizing, algebraically defining, or using optimization tools to identify this region is crucial for finding the optimal solution within the constraints of the problem.Consider a production optimization problem where a company aims to maximize profit by allocating resources to various products. Constraints may include limited raw materials, production capacities, and labor availability. The feasible region is the set of production levels satisfying these constraints, ensuring efficient resource utilization and adherence to operational limitations.

The feasible region is the intersection of the regions defined by each constraint. In this case, it is the region where both inequalities are simultaneously satisfied.The intersection of the feasible regions defined by the inequalities constitutes the feasibility region for the optimization problem.

Identifying the feasibility region involves analyzing and visualizing constraints to determine where all conditions are met. For simpler problems, this can be done graphically, while more complex cases require algebraic methods. The intersection of all feasible regions for each constraint forms the overall feasibility region, guiding where viable solutions exist.

Some corrections: 1. "If the feasibility region is a line, a plane, or a higher-dimensional space, it means that there are infinitely many solutions that satisfy all the constraints, and the problem is unbounded." --> Having infinitely many solutions does not mean the optimization formulation is unbounded. For example, "0<=x<=2; 0<=y<=2" defines a bounded square. A formulation is unbounded if you can arbitrarily improve its objective function. 2. A problem can be represented through different optimization formulations , some of which can be unbounded and others infeasible. So, it is not appropriate to say "...the problem is unbounded... ." (Continued...)

4. "The optimal solution for a bounded problem is usually found at one of the vertices or corners of the feasibility region, which can be determined by using methods such as the simplex method or the graphical method." It's incorrect to make this general statement. Finding an optimal solution at a corner of the feasible region requires special properties/structures. For example, it would be okay to make such a statement for a linear program.

3. "If the feasibility region is a bounded region with a finite area or volume, it means that there are finitely many solutions that satisfy all the constraints, and the problem is bounded." Here the formulation would be bounded, but could possibly have infinitely many solutions. For example, "0<=x<=2; 0<=y<=2; x is an integer; y is an integer" has finite number of solutions, but "0<=x<=2; 0<=y<=2; x is real; y is real" has infinitely many solutions. (Continued...)

There is no such thing as "improving" the feasible region. What you can the equalities and inequalities that define your feasible region tighter. A trivial example would be writing "x>=20; x>=19.5; x integer" as "x>=20; x integer."

It is not clear what "improve the feasible region" is supposed to mean, although the last sentence seems to imply that the goal here is to "make the optimization problem easier to solve" in some way. Removing redundant/overlapping constraints or applying scaling to certain variables might reduce computational effort but they do nothing to change the feasibility of the problem. If it is feasible in one coordinate system then it should be feasible in any other coordinate system under some scale, translation, or nonlinear one-to-one transformation.

Improving the feasible region is kind of vague/ambiguous term. If the goal is to make the problem easier to solve, redundant constraints can be eliminated. Integer programs are harder to solve compared to linear programs and often LP relaxation is used to make the process easier. Valid inequalities can be used to generate the cutting planes that cut off non integral parts of the feasible region so as to make the optimization problem easier to solve.

Assuming this section discusses ways to simplify optimization problems, here are a few strategies to achieve that. First, ensuring the feasible region is convex makes the problem easier to solve due to the properties of convexity. It is even more advantageous if the feasible region is a bounded convex polygon. For unbounded feasible regions, attention should be directed towards the direction of the objective function. For example, it's acceptable to solve a minimization problem with a feasible region that is not bounded from above. Additionally, incorporating additional constraints in the form of cuts or user-defined restrictions on the decision variables can further restrict the solution space, potentially improving solve time.

A commenter says, "the decision variables are the physical quantities that need to be minimized or maximized." This statement needs to be corrected. The correct statement is that the decision variables are the quantities that need to be determined such that they minimize/maximize the objective function while satisfying the constraints.

To make this article complete in some sense here are some missing details about optimization formulations: An optimization formulation is mathematical model that has three components: an objective function that needs to be either minimized or maximized, the decision variables and the set of constraints. The constraints are restrictions imposed by the problem that need to be satisfied, and the decision variables are the physical quantities that are adjusted to optimize (minimize or maximize) the objective function. (Thanks to Ashkan Mohammadi, for pointing out an issue with an earlier version.)