Circuit Board Partitioning

Problem

A circuit board has a set of components that may have connections between them. The board must be divided in to two smaller boards with equal amount of components. Your task is to find a partition of the components into two boards so that connections between the boards is minimized (optimization problem) or an assignment where the number of connections is at most a given bound K (decision problem).

Input

A graph with each node representing a component and each edge representing a connection between two components and for the decision problem the maximum number of connections between the boards

Output

Local Search

Assignments for variables n1,n2..
n1 = 0; if node n1 belongs to first group
n2 = 1; if node n2 belongs to second group
Example output:

n1 = 1;
n2 = 1;
n3 = 0;

Linear Program

Assignments for variables n1,n2..
n1 = 0 if node n1 belongs to first group
n2 = 1 if node n2 belongs to second group

SAT

Assignments for boolean variables n1,n2..
n1 = 0 if node n1 belongs to first group
n2 = 1 if node n2 belongs to second group

Example Instances