Without more information about f and g, this problem is NP-hard to solve. The topic is quite broad, check the family of [Branch and Bound][1] algorithms, depending of additional information you can do better than NP-hard (however, I am not confident enough to tell you that monotonicity is of any value at using this methods, but I think so).


  [1]: https://en.wikipedia.org/wiki/Branch_and_bound