Maximize number of assigned variables in constraint satisfaction

Question

What are some known algorithms (or resources to find algorithms) to find the assignment that maximizes the number of assigned variables in a constraint satisfaction problem (in case no satisfying assignment is present)?

Answer 1

For linear equations, linear algebra can be used to find the number of degrees of freedom, and hence the number of assignable independent variables.

Edit:

Upon closer thought on you problem, I think the Simplex Algorithm might help you. It is an optimizing algorithm to find the best integer solution to a linear optimizing problem.

Edit 2:

Let the feasible region be the supplied depots.

Example:

Let's say you have 2 depot types, X and Y.

X requires 5 oil and 7 steel to be supplied.

Y requires 8 oil and 2 steel to be supplied.

You want to maximize the number supplied depots:

function to maximize = X + Y

Conditions:

X <= total number of depots of type X Y <= total number of depots of type Y 5X + 8Y < total oil supply 7X + 2Y < total steel supply

Apply the Simplex algorithm, and voila!

Answer 2

Could it be that you want to maximize the number of satisfied constraints, instead of assigned variables? I thought about what you might gain from maximizing the number assigned variables (until you trivially see at least one constraint violated), and it appears to me that you want something along the line of the largest subset of constraints that are satisfiable. Otherwise I probably don't understand your optimization criterion.

In case you want this largest subset of satisfiable constraints an idea is to convert your problem to a constraint optimization problem, find the assignment that minimizes the number of violated constraints, and then pick all those of your constraints which this assignment satisfies to construct a largest subset of satisfiable constraints.

I will use the framework of weighted constraint satisfaction problem (WCSP) in the following.

Given that you represent your constraints as tables of allowed or disallowed partial assignments, you can convert a constraint by simply assigning allowed assignments cost 0 and disallowed assignments cost 1. That is, whenever a variable assignment is not allowed by a constraint, it will incur a cost. The assignment that minimizes the costs consequently minimizes the number of constraints it violates, which is equivalent to maximizing the number of satisfied constraints. Once you have such an assignment it should be easy to construct a largest subset of satisfiable constraints by iterating over all constraints and check whether the assignment satisfies them or not. A good solver for WCSP is toulbar2, which computes such least cost assignments to a given WCSP.

Constructing a WCSP from your constraint satisfaction problem (CSP) is simple in case you do represent constraints as tables. Weighted constraints are just tables of the form

X_1 X_2 … X_n   c

1    1 …   1    0 

1    2 …   1    0 

... 

2    2 …   3    1

2    2 …   4    1

Here we have a constraint over n variables X_1, …, X_n, where variables may accept values from finite domains {1,2} and {1,2,3,4}. Assuming that you mark an allowed tuple with "T" and a disallowed one with "F", converting amounts to replacing the "T" with cost 0 and "F" with cost 1.

Note that this is not the actual WCSP format. The format is described in detail in the toulbar2 package linked above.

Of course, more compact representations of constraints will require a more elaborate conversion, which can grow arbitrarily complex depending on your representation. That is then the point where you might want to look into something else.