Skip to content

Fractional Programming

Fractional programming is used to find the extremum of a fraction. Formally, given \(a_i\) and \(b_i\), find a set of \(w_i\in\{0,1\}\) that minimizes or maximizes

\[ \displaystyle\frac{\sum\limits_{i=1}^na_i\times w_i}{\sum\limits_{i=1}^nb_i\times w_i} \]

In simpler terms, such problems are similar to: each item has two weights \(a\) and \(b\), select a number of items such that \(\displaystyle\frac{\sum a}{\sum b}\) is minimized or maximized.

Generally, fractional programming problems also have special constraints, such as "the denominator is at least \(W\)".

Solution

The general method for fractional programming problems is binary search on the answer. Suppose the current binary search answer is \(\textit{mid}\), then a set of \(\{w_i\}\) satisfying the condition will make the value greater than or equal to \(\textit{mid}\). Based on this condition, we can formulate an inequality and transform it:

\[ \displaystyle \begin{aligned} &\frac{\sum a_i\times w_i}{\sum b_i\times w_i}\ge mid\\ \Longrightarrow&\sum a_i\times w_i-mid\times \sum b_i\cdot w_i\ge 0\\ \Longrightarrow&\sum w_i\times(a_i-mid\times b_i)\ge 0 \end{aligned} \]

Then we only need to find the maximum value of the expression on the left side of the inequality. If the maximum is greater than \(0\), it means \(mid\) is feasible; otherwise, it is not feasible. The main difficulty in fractional programming lies in how to find the maximum or minimum of \(\displaystyle \sum w_i\times(a_i-mid\times b_i)\).

Dinkelbach Algorithm

The general idea of the Dinkelbach algorithm1 is to use the answer from the previous iteration as the new \(L\) for input, and iterate continuously until the answer converges.

Examples

LOJ 149 Fractional Programming

There are \(n\) items, each with two weights \(a\) and \(b\). Find a set of \(w_i\in\{0,1\}\) such that exactly \(k\) of the \(w_i\) are \(1\), maximizing \(\displaystyle\frac{\sum a_i\times w_i}{\sum b_i\times w_i}\).

Solution

Treat \(a_i-mid\times b_i\) as the weight of the \(i\)-th item, and greedily select the top \(k\) items with the largest weights. If the sum of weights is greater than \(0\), it is feasible; otherwise, it is not.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <algorithm>
#include <cstdio>
#include <functional>
using namespace std;

constexpr int N = 100000 + 10;
constexpr double eps = 1e-6;

int n, k;
int a[N], b[N];
double c[N];

bool check(double mid) {
  double s = 0;
  for (int i = 1; i <= n; i++) c[i] = a[i] - b[i] * mid;
  // Sort the weights in descending order
  sort(c + 1, c + n + 1, greater<double>());
  for (int i = 1; i <= k; ++i)  // Select the first k items
    s += c[i];
  return s >= 0;
}

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
  double L = 0, R = 1;
  while (R - L > eps) {
    double mid = (L + R) / 2;
    if (check(mid))  // mid is feasible, answer is larger than mid
      L = mid;
    else  // mid is not feasible, answer is smaller than mid
      R = mid;
  }
  printf("%.6lf\n", L);
  return 0;
}
Luogu P4377 Talent Show G

There are \(n\) items, each with two weights \(a\) and \(b\).

You need to determine a set of \(w_i\in\{0,1\}\) such that \(\displaystyle\frac{\sum w_i\times a_i}{\sum w_i\times b_i}\) is maximized.

The constraint is \(\displaystyle\sum w_i\times b_i \geq W\).

Solution

This problem has the additional constraint that the denominator must be at least \(W\), so the greedy algorithm from the previous problem can no longer be used.

Consider 0-1 knapsack. Treat \(b_i\) as the weight of the \(i\)-th item and \(a_i-mid\times b_i\) as the value of the \(i\)-th item, then the problem transforms into a knapsack problem. Thus, \(dp[n][W]\) is the maximum value.

During the DP process, if the total weight of items exceeds \(W\), it can be directly treated as \(W\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <algorithm>
#include <cstdio>
using namespace std;

constexpr int MAXN = 250 + 10;
constexpr int MAXW = 1000 + 10;
constexpr double eps = 1e-6;

int n, W;
int w[MAXN], t[MAXN];
double f[MAXW];

bool check(double mid) {
  double s = 0;
  for (int i = 1; i <= W; i++) f[i] = -1e9;
  for (int i = 1; i <= n; i++)
    for (int j = W; j >= 0; j--) {
      int k = min(W, j + w[i]);
      f[k] = max(f[k], f[j] + t[i] - mid * w[i]);
    }
  return f[W] >= 0;
}

int main() {
  scanf("%d %d", &n, &W);
  double L = 0, R = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &w[i], &t[i]);
    R += t[i];
  }
  while (R - L > eps) {
    double mid = (L + R) / 2;
    if (check(mid))
      L = mid;
    else
      R = mid;
  }
  printf("%d\n", (int)(L * 1000));
  return 0;
}
POJ2728 Desert King

Each edge has two weights \(a_i\) and \(b_i\). Find a spanning tree \(T\) such that \(\displaystyle\frac{\sum_{e\in T}a_e}{\sum_{e\in T}b_e}\) is minimized.

Solution

Treat \(a_i-mid\times b_i\) as the weight of each edge, then the minimum spanning tree gives the minimum value. This problem requires finding a minimum spanning tree in a complete graph, so Prim's algorithm should be used.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int N = 1000 + 10;
const double eps = 1e-5;

int n;
double d[N][N], c[N][N], dis[N];
int x[N], y[N], z[N];
bool vis[N];

bool ok(double m) {
  double ans = 0;
  for (int i = 1; i <= n; i++) vis[i] = false;
  dis[1] = 0;
  for (int i = 2; i <= n; i++) dis[i] = 1e18;
  for (int i = 1; i <= n; i++) {
    double mn = 1e18;
    int pt = -1;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && mn > dis[j]) {
        pt = j;
        mn = dis[j];
      }
    if (!~pt) break;
    vis[pt] = true;
    ans += mn;
    for (int j = 1; j <= n; j++)
      if (j != pt) dis[j] = min(dis[j], c[pt][j] - m * d[pt][j]);
  }
  return ans >= 0;
}

int main() {
  while (scanf("%d", &n) == 1) {
    if (n == 0) break;
    for (int i = 1; i <= n; i++) scanf("%d %d %d", &x[i], &y[i], &z[i]);
    for (int i = 1; i <= n; i++)
      for (int j = i + 1; j <= n; j++) {
        d[i][j] = d[j][i] =
            sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
        c[i][j] = c[j][i] = abs(z[i] - z[j]);
      }
    double l = 0, r = 10000000;
    while (r - l > eps) {
      double m = (l + r) / 2;
      if (ok(m))
        l = m;
      else
        r = m;
    }
    printf("%.3f\n", l);
  }
  return 0;
}
[HNOI2009] Minimum Cycle

Each edge has weight \(w\). Find a cycle \(C\) such that \(\displaystyle\frac{\sum_{e\in C}w}{|C|}\) is minimized.

Solution

Treat \(a_i-mid\) as the edge weight, then the cycle with the smallest weight is the minimum value.

Since we only need to check whether the minimum value is less than \(0\), we only need to determine whether there exists a negative cycle in the graph.

Additionally, there exists an algorithm with complexity \(O(nm)\) for this problem. If interested, you can read this article.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <algorithm>
#include <cstdio>
#include <tuple>
#include <vector>
using namespace std;

constexpr int N = 3000 + 10;
constexpr double eps = 1e-9;

int n, m;
double dis[N];
vector<pair<int, double>> g[N];

bool check(double mid) {  // Returns true if there is a negative cycle
  bool flag = false;
  dis[0] = 0;
  for (int i = 1; i <= n; ++i) dis[i] = 1e9;
  for (int t = 1; t <= n; ++t) {
    flag = false;
    for (int u = 0; u <= n; ++u)
      for (auto vw : g[u]) {
        int v;
        double w;
        tie(v, w) = vw;
        if (dis[v] > dis[u] + w - mid) {
          dis[v] = dis[u] + w - mid;
          flag = true;
        }
      }
    if (!flag) break;
  }
  return flag;
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    double w;
    scanf("%d %d %lf", &u, &v, &w);
    g[u].push_back({v, w});
  }
  for (int i = 1; i <= n; i++) g[0].push_back({i, 0});
  double L = -1e7, R = 1e7;
  while (R - L > eps) {
    double mid = (L + R) / 2;
    if (check(mid))
      R = mid;
    else
      L = mid;
  }
  printf("%.8lf\n", L);
  return 0;
}

Exercises

References and Notes

  1. Dinkelbach, Werner. "On nonlinear fractional programming." Management science 13.7 (1967): 492-498. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用