For given values of constants $\forall i $ $a_i, b_i, c$ such that $a_i, b_i, c \in Q^+$ and $0 < a_i < 1$, find all variables $n_i$ such that

$$n_i \in Z^+$$ and $$c \ge \sum_{i}{\frac{b_i}{n_i} * \lceil{a_i * n_i}\rceil}$$ while minimizing the cost function $$\sum_i{n_i}$$

What I have found: $$n\in Z^+, x \in Q^+ \implies x \leq \frac{\lceil{nx}\rceil}{n} \leq \lceil{x}\rceil, $$

$$x = \frac{\lceil{nx}\rceil}{n} \implies nx \in Z^+$$

So one neccesary condition is $$c \ge \sum_{i}{b_i * a_i}$$ So one solution for the given problem is $$n_i \hspace{1mm}\mid n_i * a_i \in Z^+$$ BUT this solution DOESN'T necessarily optimize the cost function.


Suppose this is the problem $$2 \ge \frac{3}{n_1} * \lceil{\frac{3}{7} * n_1}\rceil + \frac{1}{n_2} * \lceil{\frac{2}{8} * n_2}\rceil$$

From brute force, I know that optimal solution to this problem is $$n_1 = 2, n_2 = 2$$ whereas if we take $n_i$ to be the smallest integer such that $n_i * a_i \in Z^+$, we get $$n_1 = 7, n_2 = 4$$ These satisfy the constraint equation but are not optimal.

Not exact solution but maybe close?

So I was thinking that maybe an iterative algorithmic solution might exist. What I found is this: Since $\frac{\lceil{n_i * a_i}\rceil}{n_i}$ is minimum at the minimum $n_i$ such $n_i a_i \in Z^+$, lets say $n_i=k$, $n_i$ needs to be searched over $[1,k]$ only. Further more, suppose there are two values of $n_i$ such that $n_i=l_1 \implies n_i * a_i = d_1, d_1 \in Z^+$ and $n_i=l_2 \implies n_i * a_i = d_1 + 1$ then $\frac{\lceil{n_i * a_i}\rceil}{n_i}$ is monotonically decreasing between $n_i = l_1 + 1$ and $n_i = l_2$. Maybe this information can be used to do binary search somehow. Any ideas?


I don't necessarily need a analytical solution. If someone can tell me how to use any software (such as ILP, matlab etc) to arrive at a solution, I will accept that too. Also, I am bit flexible on the cost function as long as it somewhat tries to minimize the values of all $n_i$ (such as $\sum{\frac{n_i}{b_i}}$ etc).


If it helps, you can also assume the following to make the problem easier: $$c \lt \sum{b_i}$$ $$c, b_i \in Z^+$$ $$n_i \leq N$$ for some given N. N should be around 10-20, so an iterative/algorithmic solution (not brute force) will also work.

  • $\begingroup$ This doesn't make any sense, so far as I can see. If $n_ia_i \in \mathbf Z^+,$ then so is $kn_ia_i $ for every $k\in \mathbf Z^+,$ so how can you say this "solution" minimizes the sum of the $n_i?$ Also, what if $a_i$ is irrational? $\endgroup$ – saulspatz Mar 12 '18 at 22:30
  • $\begingroup$ As I mentioned in the post, "so one solution for the given problem is always easy to find." BUT "this solution doesn't necessarily optimize the cost function". Also, I will edit the question to mention that all a, b, c are rationals. $\endgroup$ – Saksham Jain Mar 12 '18 at 22:35
  • $\begingroup$ Sorry, I missed that line. $\endgroup$ – saulspatz Mar 12 '18 at 22:49
  • $\begingroup$ Now I understand what you are saying. There is no solution unless $c\ge \sum{b_ia_i},$ and in that case, we can take $n_i$ to be the smallest positive integer such that $a_ic_i\in \mathbb Z^+,$ but that's not necessarily the optimum. Is this correct? $\endgroup$ – saulspatz Mar 12 '18 at 23:03
  • $\begingroup$ Yes, exactly. (One small correction in your comment $a_i * n_i \in Z^+$ instead of $a_i * c_i \in Z^+$) Btw, thanks for your comments! $\endgroup$ – Saksham Jain Mar 12 '18 at 23:31

This is a tentative answer only. I've come up with a simple greedy algorithm, which seems to work on the few examples I've tried, but I haven't proved that it actually works in all cases. Here's the idea.

The first thing we do is check that a feasible solution exists. If so, we set $n_i=1$ for all $i$. For each $i,$ we calculate the decrease in $(b_i/n_i)\lceil n_ia_i\rceil$ that would result from increasing $n_i$ to $n_i+1,$ and we sort the records in descending order of the decrease. We choose the biggest decrease, and recalculate what the next decrease would be. Then we resort and choose the biggest decrease again, continuing until we get the sum to le $\le c.$

I did this in python, using exact rational arithmetic. That probably isn't necessary in real life, but I want to use exact values when trying to establish the correctness of the algorithm. Because it's python the fastest thing to do is to keep calling the sort function. In a systems programming language, I'd use a min-heap.

Here's my code

# optimize.py
from fractions import Fraction 
from collections import namedtuple
import sys

Given positive rational numbers, C, a[i], b[i], with a[i] < 1, 1 <= i <= N,
find positive integers n[i] that minimize sum(n[i]), subject to
sum ( b[i]/n[i]* ceil(n[i]*a[i])) <= C

This problem arises in real-time scheduling.

Datum describes item i.  a,b are a[i], b[i], n is the current value of n[i].
value is the value of b[i]/n[i]* ceil(n[i]*a[i])
delta is the increase in the value if n[i] is increased by 1
Datum = namedtuple('Datum', 'i a b n value delta'.split())

def ceiling(f):
    q, r = divmod(f.numerator, f.denominator)
    return q if r == 0 else q+1

def datum(i, a, b):
    n = 1
    value = b
    delta = value-b/2*ceiling(2*a)
    return Datum(i,a,b,n,value,delta)

def readFile(filename):
    Input file should have the following format:
    Line 1: numerator and denominator of C (ints)
    For each i, one line of 4 ints:
    a[i].numerator a[i].denominator b[i].numerator b[i].denominator
    text = open(filename).read()
    text = list(map(int, text.strip().split())) 
    if (len(text) % 4 != 2): 
        print('Need 2 inputs for C and 4 for each i')
    C = Fraction(text[0],text[1])
    A = [Fraction(*a) for a in zip(text[2::4],text[3::4])] 
    B = [Fraction(*b) for b in zip(text[4::4] ,text[5::4])]
    data = [ ]
    for i, (a,b) in enumerate(zip(A,B)):
    s = sum(d.a*d.b for d in data) 
    if s > C:
        print('Sum is %s, bound is %s No feasible solution'%(s,C))
    return C, data

def solve(C, data):
    heat = sum(d.b for d in data)
    data.sort(key = lambda d:d.delta, reverse=True)
    while heat > C:
        d = data[0]
        heat -=d.delta
        a,b,n = d.a,d.b,d.n
        v = (b/n)*ceiling(n*a)
        delta = v - b/(n+1)*ceiling((n+1)*a)
        data[0] = Datum(d.i,a,b,n,v,delta)
        data.sort(key = lambda d:d.delta, reverse=True)
    data.sort(key=lambda d:d.i)
    return data

if __name__ =='__main__':
    C, data = readFile(sys.argv[1])
    data = solve(C, data)
    for d in data:
        print(d.a, d.b, d.n, ceiling(d.n*d.a))
    s = sum(d.b/d.n*ceiling(d.n*d.a) for d in data) 
    print('\nsum is %s bound is %s'%(s.__float__(), C))
    if s > C:
        print('FAILED AUDIT')   
        print('passed audit')

You'll notice that at the end, I'm printing out $\lceil n_ia_i\rceil.$ In the examples I've done so far (which are not many) this has always been $1$ for every $i$. I think this is probably true in general. I have been trying to prove it, in hopes that it will make proving the algorithm correct easier.

I want to put in a routine to test by brute force that the computed answer is actually optimal. So long as $\sum{n_i}$ isn't too big, this should be practicable.

I'll be happy to hear any thoughts you have on this.

  • $\begingroup$ It is ceiling function here, not the floor function. $\lceil{0.6}\rceil$ = 1 not 0. $\lfloor{0.6}\rfloor$ = 0. en.wikipedia.org/wiki/Floor_and_ceiling_functions - "The ceiling function maps ${\displaystyle x}$ to the least integer greater than or equal to ${\displaystyle x}$, denoted ${\displaystyle {\text{ceiling}}(x)=\lceil x\rceil }$ " $\endgroup$ – Saksham Jain Mar 13 '18 at 20:39
  • $\begingroup$ @SakshamJain I wondered why I didn't see that yesterday! Duh. $\endgroup$ – saulspatz Mar 13 '18 at 20: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.