Finding the penumbra of a Constraint Satisfaction Problem
Much of the attention paid to optimization variants of the constraint satisfaction problem (CSP) has focused on satisfying some number of constraints (MAX-CSP), or in the Boolean case on picking the solution which assigns as many variables as possible the value 1 (MAX-ONES, there is also MIN-ONES).

Instead, you are asking about a variant that could be called MAXIMUM PARTIAL CSP.  This was studied at least as far back as the late 1960s, but I'm not aware of it having an established name.  It is a natural problem, and it would be good to see more work investigating it.  Thank you for providing another potential application for this problem!


Ambler, A. P. and Barrow, H. G. and Brown, C. M. and Burstall, R. M. and Popplestone, R. J., A versatile system for computer-controlled assembly, Artificial Intelligence 6 129–156, 1975. doi: 10.1016/0004-3702(75)90006-5


A set of variable-value assignments is called a partial assignment.  One can write a variable-value assignment as a (variable, value) tuple.  Partial assignments are then simply functions from variables to values.  Props are partial assignments that don't violate any constraint.  Equivalently, a prop contains no partial assignment forbidden by some constraint (as a subset).

One way to express the optimization problem is as follows.


  MAXIMUM PARTIAL CSP:
  Input: CSP instance
  Output: prop $f$
  Criterion: maximize $|f|$


In an instance with $n$ variables, clearly a prop of cardinality $n$ will be a solution.  There may exist large props, with cardinality up to $n-1$, that are not contained in any solution.

In the terminology you propose, the set of props with maximum cardinality $k$ forms the penumbra, perhaps even with some additional leeway $d$ (so cardinality at least $k-d$).

The second part of your question also appears highly interesting, but I am not aware of any work related to it.



Footnote: The term prop is from my thesis; it is meant to convey the idea that such partial assignments are proper, and also that they support the set of solutions.  This is in contrast to a nogood, which is the accepted term to describe a partial assignment that cannot be extended to a solution.  The word "nogood" was introduced by Richard Stallman and Gerald Sussman in 1976, when RMS was still an AI researcher instead of software freedom activist.


Stallman, Richard M. and Sussman, Gerald Jay, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, MIT Artificial Intelligence Laboratory Memo No. 380, 1976. (PDF)