forest graph

Parametric maximum closure on precedence forests

Categories Combinatorial Optimization, Graphs and Matroids Tags ,

The Maximum Closure Problem asks for a maximum-weight closed subset of a precedence-constrained set of vertices; when vertex weights depend affinely on a scalar parameter $\lambda$, as in open-pit mine scheduling, the goal becomes computing the optimal closed set for every value of $\lambda$ at once. We address this problem when the precedence graph is … Read more

Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

Categories Global Optimization, Semi-definite Programming Tags , , ,

We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more