  In this paper, we address computation of the degree $\mathop{\rm deg Det} A$
of Dieudonn\'e determinant $\mathop{\rm Det} A$ of \[ A = \sum_{k=1}^m A_k x_k
t^{c_k}, \] where $A_k$ are $n \times n$ matrices over a field $\mathbb{K}$,
$x_k$ are noncommutative variables, $t$ is a variable commuting with $x_k$,
$c_k$ are integers, and the degree is considered for $t$. This problem
generalizes noncommutative Edmonds' problem and fundamental combinatorial
optimization problems including the weighted linear matroid intersection
problem. It was shown that $\mathop{\rm deg Det} A$ is obtained by a discrete
convex optimization on a Euclidean building. We extend this framework by
incorporating a cost scaling technique, and show that $\mathop{\rm deg Det} A$
can be computed in time polynomial of $n,m,\log_2 C$, where $C:= \max_k |c_k|$.
We give a polyhedral interpretation of $\mathop{\rm deg Det}$, which says that
$\mathop{\rm deg Det} A$ is given by linear optimization over an integral
polytope with respect to objective vector $c = (c_k)$. Based on it, we show
that our algorithm becomes a strongly polynomial one. We apply this result to
an algebraic combinatorial optimization problem arising from a symbolic matrix
having $2 \times 2$-submatrix structure.
