How to write the optimization constraint of the following problem

Question

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{ij}\le d$.

So I start with the objective $$\max \sum_{i}^n \sum_{i<j} A_{ij}$$ and one more constraint $\sum_{j} A_{ij} = 1, \, \forall i=1 \cdots n$, which basically require there is no shared node in two links.

My question is how to formulate the constraint such that the weight is limited if $A_{ij} = 1$?

Answer 1

For some graph(actually many), it does not have a maximum matching which cover all vertices(nodes). So, I think that you need to reduce your constraint: $\Sigma_j A_{ij}\leq1,\; \forall i$.

Answer 2

The linear program you have written down--maximize the sum of the edge weights given that the sum of the weights of the edges incident to $v$ is at most 1 for every vertex $v$--is NOT guaranteed to find an integer solution i.e., a matching, for all instances. For example, consider the 3-cycle. Then the weighting that will maximize your objective function has each edge in the 3-cycle given a weight of $\frac{1}{2}$.

Fortunately though, maximum matching is polynomial-time solvable regardless. If two vertices $u$ and $v$ cannot be matched together due to the sum of their weights being too high, can't you just remove the edge between $u$ and $v$?

I hope this answers your question, your question was rather vaguely worded so I am not positive if this answers what you were asking.