Finding largest f satisfying a property given f is non-decreasing in its arguments

Question

this has been bugging me for a while.

Lets say you have a function f x y where x and y are integers and you know that f is strictly non-decreasing in its arguments,

i.e. f (x+1) y >= f x y and f x (y+1) >= f x y.

What would be the fastest way to find the largest f x y satisfying a property given that x and y are bounded.

I was thinking that this might be a variation of saddleback search and I was wondering if there was a name for this type of problem.

Also, more specifically I was wondering if there was a faster way to solve this problem if you knew that f was the multiplication operator.

Thanks!

Edit: Seeing the comments below, the property can be anything

Given a property g (where g takes a value and returns a boolean) I am simply looking for the largest f such that g(f) == True

For example, a naive implementation (in haskell) would be:

maximise :: (Int -> Int -> Int) -> (Int -> Bool) -> Int -> Int -> Int
maximise f g xLim yLim = head . filter g . reverse . sort $ results
    where results = [f x y | x <- [1..xLim], y <- [1..yLim]]

Answer 1

Let's draw an example grid for your problem to help think about it. Here's an example plot of f for each x and y. It is monotone in each argument, which is an interesting constraint we might be able to do something clever with.

+------- x --------->
| 0  0  1  1  1  2 
| 0  1  1  2  2  4
y 1  1  3  4  6  6
| 1  2  3  6  6  7
| 7  7  7  7  7  7
v

Since we don't know anything about the property, we can't really do better than to list the values in the range of f in decreasing order. The question is how to do that efficiently.

The first thing that comes to mind is to traverse it like a graph starting at the lower-right corner. Here is my attempt:

import Data.Maybe (listToMaybe)

maximise :: (Ord b, Num b) => (Int -> Int -> b) -> (b -> Bool) -> Int -> Int -> Maybe b
maximise f p xLim yLim = 
    listToMaybe . filter p . map (negate . snd) $ 
       enumIncreasing measure successors (xLim,yLim)
  where
    measure (x,y) = negate $ f x y
    successors (x,y) = [ (x-1,y) | x > 0 ] ++ [ (x,y-1) | y > 0 ] ]

The signature is not as general as it could be (Num should not be necessary, but I needed it to negate the measure function because enumIncreasing returns an increasing rather than a decreasing list -- I could have also done it with a newtype wrapper).

Using this function, we can find the largest odd number which can be written as a product of two numbers <= 100:

ghci> maximise (*) odd 100 100
Just 9801

I wrote enumIncreasing using meldable-heap on hackage to solve this problem, but it is pretty general. You could tweak the above to add additional constraints on the domain, etc.

Answer 2

The answer depends on what's expensive. The case that might be intersting is when f is expensive.

What you might want to do is look at pareto-optimality. Suppose you have two points

(1, 2)    and    (3, 4)

Then you know that the latter point is going to be a better solution, so long as f is a nondecreasing function. However, of course, if you have points,

(1, 2)    and    (2, 1)

then you can't know. So, one solution would be to establish a pareto-optimal frontier of points that the predicate g permits, and then evaluate these though f.