Skip to content
Glacius
OptimizationConcept reference

Feasible sets

The feasible set contains exactly the decisions satisfying all stated constraints.

1 min read1 figureSources & further reading
On this page 7 sections
  1. Overview
  2. A decision is feasible when it satisfies every stated constraint
  3. Resource restrictions are constraints too
  4. The boundary belongs to x+yle8, but not to x+y<8
  5. Key takeaway
  6. Sources & further reading
  7. Concept connections

01A decision is feasible when it satisfies every stated constraint#

A decision is feasible when it satisfies every stated constraint. Check their intersection, including the domain and each inequality.

A low objective value cannot compensate for breaking a constraint.

For x≥0, y≥0 and x+y≤8, the point (3,5) uses the entire budget and remains feasible.

Feasible decisions satisfy x≥0, y≥0, x+y≤8. Their intersection is the closed triangle with vertices (0,0),(8,0),(0,8). Candidate (3,5) lies on the included budget boundary.Feasible decisions satisfy x≥0, y≥0, x+y≤8. Their intersection is the closed triangle with vertices (0,0),(8,0),(0,8). Candidate (3,5) lies on the included budget boundary.
Figure 1Feasible decisions satisfy x≥0, y≥0, x+y≤8. Their intersection is the closed triangle with vertices (0,0),(8,0),(0,8). Candidate (3,5) lies on the included budget boundary.
Link to this figure ↗Download SVGDownload PNG
Check your reasoning

x,y≥0x,y\ge0, 1x+1y≤61x+1y\le6. Choose a feasible point.

  1. A(3,4)(3, 4)
  2. B(2,4)(2, 4)
  3. C(−2,1)(-2, 1)
Show answer and explanation
(2,4)(2, 4)

At (2, 4), both coordinates are nonnegative and use 6 units.

02Resource restrictions are constraints too#

Resource restrictions are constraints too. Add the usage from each quantity and compare it with the available capacity.

Nonnegativity is a separate requirement; a negative count cannot free up imaginary resources.

Check your reasoning

Nonnegative x,yx,y use 3x+2y3x+2y capacity units. Capacity is at most 1313. Choose a feasible point.

  1. A(3,2)(3, 2)
  2. B(4,1)(4, 1)
  3. C(0,−1)(0, -1)
Show answer and explanation
(3,2)(3, 2)

Uses 13; x,y≥0.

03The boundary belongs to x+yle8, but not to x+y<8#

The boundary belongs to x+y≤8x+y\le8, but not to x+y<8x+y<8. Read the comparison sign before accepting equality.

To repair an invalid candidate, test the replacement against every constraint again.

Check your reasoning

x,y≥0x,y\ge0, 2x+1y<82x+1y<8. A draft accepts (3,2)(3, 2). Choose a valid replacement.

  1. A(3,2)(3, 2)
  2. B(−1,2)(-1, 2)
  3. C(2,3)(2, 3)
Show answer and explanation
(2,3)(2, 3)

Nonnegative; 7<8 units.

Key takeaway

Check every constraint and its boundary symbol; cost alone does not make a point feasible.

  • Identify decisions satisfying all stated constraints.

Sources & further reading

  1. [1]
    Boyd & Vandenberghe §4.1.1 ↗Boyd & Vandenberghe §4.1.1 · Article

Reference this concept

Link to this page, a section, or an individual figure.

Glacius. “Feasible sets.” Math behind ML. /learn/o-feasible