Summary: Given a multigraph \(G=(V,E)\) with a positive rational weight \(w(e)\) on each edge \(e\), the weighted density problem (WDP) is to find a subset \(U\) of \(V\), with \(| U|\geq 3\) and odd, that maximizes \(2w(U)/(| U|-1)\), where \(w(U)\) is the total weight of all edges with both ends in \(U\), and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize \(\mathbf 1^T\boldsymbol x\) subject to \( A\boldsymbol x=\boldsymbol w\), \(\boldsymbol x\geq\mathbf 0\), where \(A\) is the edge-matching incidence matrix of \(G\). These two problems are closely related to the celebrated Goldberg-Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when \(w(e)=1\) for all edges \(e\), determining whether WDP can be solved in polynomial time was posed by \textit{T. R. Jensen} and \textit{B. Toft} [in: Topics in chromatic graph theory. Cambridge: Cambridge University Press. 327--357 (2015; Zbl 1377.05064)] and by \textit{M. Stiebitz} et al. [Graph edge coloring. Vizing's theorem and Goldberg's conjecture. Hoboken, NJ: John Wiley \& Sons (2012; Zbl 1339.05001)] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring.