Character of solution

From Glossary

Jump to: navigation, search

The idea is to define character by solution status. In linear [integer] programming, columns might be partitioned into

  • basic vs. nonbasic at Lower bound vs. nonbasic at Upper bound
  • positive in some optimal solution vs. zero in every optimal solution

Rows might be partitioned into

  • inactive vs. active
  • non-binding vs. binding
  • positive dual price in some optimal solution vs. zero dual price in every optimal solution

Only some rows and columns might be partitioned, and others are free to change. The character is the property we want to fix by the partition. For example, if the LP has activities for operating a plant, we might want to specify the plant operation as a character of the solution, never mind specific levels (or maybe some minimal throughput is specified).

Then, one conducts sensitivity analysis by asking for preservation of the character. Classical LP sensitivity analysis does this by preserving the optimality of the basis; interior point analysis seeks to preserve the optimality of the partition. Both are special cases, and one might want to focus on only a portion of the LP. Here are some properties of interest:

  1. If the character holds at [c', b'] and at [c", b"], it holds for all [c, b] in their line segment.
  2. The stability region is a convex set.

This notion of character extends naturally to combinatorial optimization, such as preserving a key portion of a TSP tour or job-order in a schedule.

Personal tools