3
$\begingroup$

I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it.

I'll try to simplify, with a simple analogue, and after will explain the real world use case:

Analogue:

Imagine you have 2 buckets of springs. Each spring has 2 properties: resting length, and maximum stretching length. Some springs are basically just rods, and resting length = maximum stretch length.

Your job is to maximize length of joined springs (& rods) in each bucket, such that the length of the 2 joined springs in the 2 buckets match exactly.

Example:

A bucket of springs $S_k$ is a non-empty multiset of intervals $[i,j]$, where $i$ denotes the "resting length", and $j$ denotes the "maximal stretch length". For example, if the two buckets are

$$\begin{align*} S_1&=\{[2,4],[2,4],[4,4]\} \\ S_2&=\{[1,1],[2,4],[13,15]\} \end{align*}$$ then the maximum achievable length is 5, since $2 + 3 = 1 + 4$ and $2 \in [2,4]$ and $3 \in [2,4]$ and $1 \in [1,1]$ and $4 \in [2,4]$.

Note that if the last spring in $S_2$ would have been $[12,15]$ instead of $[13,15]$, the maximum length would have been $12$ (by the choice $4+4+4=12$). But since lengths in each bucket must match exactly, we end up with only $5$.

Real (boring) problem:

My use case is from the finance world. I'm trying to match buy orders & sell orders for different amounts. Some of the orders can be partially accepted, whilst other must be strictly accepted or rejected. The orders I can partially accept, also specify the minimum amount it must be accepted with.
Each order is a "spring" in the analogy, where "resting length" is minimum accepting amount, and "maximum stretching length" is the full amount. The 2 buckets are the buy orders & sell orders.
Also, note that for now I've been asked to maximize amounts, but a further complication of the algorithm would be to maximize both amount & price. Either by preferring amount over price, and when there's a choice, to prefer the better price (lower for buy, higher for sell), or by maximizing total revenue (sell price * amount - buy price * amount).

Just for fun

Try to generalize to any number of $n>1$ buckets. In a valid solution, all buckets must end up with the same total length.

P.S. To be clear, I haven't solved it efficiently myself. And I am still looking for an efficient way to do the matching. I'm interested in the subset of orders, and not just the maximal amount that can be matched. Also, this kind of reminds me of bean packing problem (NP complete), because of the strict orders (rods), but not quite. Even if it is NP complete, I'm still gonna implement it (inefficiently), since mostly it'll work on a small number of orders (pretty sure it's gonna be OK). But I have a hunch there's a dynamic algorithm somewhere that can be more efficient.

$\endgroup$
  • 2
    $\begingroup$ Even the non-generalized problem is NP-complete. Consider arbitrary $S_1$ and $S_2 = \{k\}$. Now you're looking at the given subset sum problem. You can do pseudo-polynomial time algorithms if the lengths are small and discrete. $\endgroup$ – orlp Sep 8 '18 at 23:14
  • $\begingroup$ You are right! I was so hunged on finding an algorithm, I haven't realy tried to find a reduction. And this one is so simple. Brilliant. Thanks! $\endgroup$ – gilad hoch Sep 8 '18 at 23:19
2
$\begingroup$

I would solve this problem with an SMT solver like z3. Example in Python:

import z3

buckets = [
    [(2, 4), (2, 4), (4, 4)],
    [(1, 1), (2, 4), (13, 15)],
]

solver = z3.Optimize()

m = z3.Int("m")

for bnr, bucket in enumerate(buckets):
    springs = []
    for b, (lo, hi) in enumerate(bucket):
        include_spring = z3.Bool(f"is{bnr},{b}")
        spring = z3.Real(f"s{bnr},{b}")
        solver.add(lo <= spring)
        solver.add(spring <= hi)
        springs.append(include_spring * spring)

    solver.add(z3.Sum(springs) == m)

solver.maximize(m)
solver.check()

model = solver.model()
print(solver.model())

The constraints are easy to express and SMT solvers are really quite powerful nowadays.

$\endgroup$
  • $\begingroup$ Im not familiar with SMT solvers (will go educate myself on the matter). But from reading the code block, it looks like modeling a constraint optimization problem. And Im not sure if the problem is reductible to linear programming (can be solved efficiently using e.g. simplex algorithm) or integer programming (NP hard). In any case, it's an overkill. And since i'm looking for something to integrate in a financial trading system, it has to be as fast as possible. I can't really use it. And besides, I can't shake the feeling this problem can be solved by a dynamic algorithm :-/ $\endgroup$ – gilad hoch Sep 8 '18 at 22:45
  • 1
    $\begingroup$ @giladhoch This is not a linear programming problem, I can tell you that much. $\endgroup$ – orlp Sep 8 '18 at 22:53
  • $\begingroup$ I guess since you proved the problem to be NP complete, there really isn't much point in searching for an optimal algorithm... $\endgroup$ – gilad hoch Sep 9 '18 at 0:05
  • $\begingroup$ @giladhoch I think you're underestimating the speed of modern SMT solvers. Try throwing some really complicated instances at the code above. $\endgroup$ – orlp Sep 9 '18 at 3:12
  • $\begingroup$ Maybe. But for my usecase, I'll need something I can run in a JVM, and it should give an answer preferably in a sub-millisecond. But lets say ill be happy to get a solution that will take 10ms in the worst case. $\endgroup$ – gilad hoch Sep 9 '18 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.