2.3 Multiscale Simplicial Flat Norm and Integer Lin- ear Programming The problem of finding the multiscale simplicial flat norm of the d -chain t (Equation 2.5) can be cast formally as the following optimization problem. The objective function is piecewise linear in the integer variables x and s . Using standard modeling techniques from linear optimization [7, pg. 18], we can reformulate the problem as the following integer linear program (ILP). The objective function coefficients need to be nonnegative for this formulation to work – indeed, we have w$_{i}$, v$_{j}$ , and λ nonnegative. Integer linear programming is NP-complete [37]. The linear programming relaxation of the ILP above is obtained by ignoring the integer restrictions on the variables. min ∑ m i $_{=1}$w$_{i}$ ( x + i + x − i ) + λ ( ∑ n j $_{=1}$v$_{j}$ ( s + j + s − j ) ) s.t. x + − x − = t − [ ∂$_{d}$$_{+1}$ ]( s + − s $^{−}$) x $^{+}$, x − ≥ 0 , s $^{+}$, s − ≥ 0 (2.9) 23 min ∑ m i $_{=1}$w$_{i}$ ( x + i + x − i ) + λ ( ∑ n j $_{=1}$v$_{j}$ ( s + j + s − j ) ) s.t. x + − x − = t − [ ∂$_{d}$$_{+1}$ ]( s + − s $^{−}$) x $^{+}$, x − ≥ 0 , s $^{+}$, s − ≥ 0 x $^{+}$, x − ∈ Z $^{m}$, s $^{+}$, s − ∈ Z $^{n}$. (2.8) minimize ∑ m i $_{=1}$w$_{i}$ | x$_{i}$ | + λ ( ∑ n j $_{=1}$v$_{j}$ ∣ $_{∣}$s$_{j}$ ∣ $_{∣}$) subject to x = t − [ ∂$_{d}$$_{+1}$ ] s , x ∈ Z $^{m}$, s ∈ Z $^{n}$. (2.7)