M♮-Convex Function Partition Problem


M♮-Convex Function Partition Problem

Input
w_1, ..., w_m: Z_+^n → R : M♮-convex functions[3]
z ∈ Z_+^n
Problem
minimize w_1(x_1) + ... + w_m(x_m)
subject to x_1 + ... + x_m = z,
x_1, ..., x_m ∈ Z_+^n

If z = (1, ..., 1) and x_1, ..., x_m ∈ {0,1}^n, this problem is reduced to Valuated Matroid Partition Problem; each vector corresponds to an indicator of a set. Valuated Matorid Partition Problem can be solved in polynomial time[2]. For a general case, M♮-Convex Function Partition Problem can also be solved in polynomial time by similar algorithm with scaling[1,3].

Since M♮-concave function (negative of M♮-convex function) is submodular, this contains a solvable subclass of Submodular Welfare Problem, which is NP-hard in general.

Source Code (in C++)

We implemented a successive shortest path algorithm without scaling. It is a pseudo-polynomial time algorithm.

The program is provided in a C++ header file. To use the algorithm, you only need to #include the header file to your program, call the algorithm, and compile it; see the example below. We provide some user-friendly interfaces (2-partition case, 3-partition case, {0,1} case, ...). Please also see README for more detail.

Usage

Here is an example of the usage of the program. Put #include "mgconv_partition.hpp" on your code and call the "mgconv_partition" function. This is "example1.cpp" in the archive above.

example1.cpp

#include <cstdio>
#include <cmath>
#include "mgconv_partition.hpp" // include the header

// define M#-convex functions
double f(int n, int x[]) {
  if (x[0] == 0 && x[1] == 0) return  0;
  if (x[0] == 1 && x[1] == 0) return -3;
  if (x[0] == 0 && x[1] == 1) return -2;
  if (x[0] == 1 && x[1] == 1) return -1;
}
double g(int n, int x[]) {
  if (x[0] == 0 && x[1] == 0) return  0;
  if (x[0] == 1 && x[1] == 0) return -2;
  if (x[0] == 0 && x[1] == 1) return  0;
  if (x[0] == 1 && x[1] == 1) return -2;
}

int main() {
  const int n = 2;
  int x[n], y[n];

  // minimize f(x) + g(y) subject to x + y = (1,1), x, y \in {0,1}^2
  double opt = mgconv_partition(2, x, y, f, g);

  printf("optimal value = %lf\n", opt);
  printf("x = ");
  for (int i = 0; i < n; ++i) printf("%d", x[i]);
  printf("\ny = ");
  for (int i = 0; i < n; ++i) printf("%d", y[i]);
  printf("\n");
}

Result

> g++ example1.cpp

> ./a.out
optimal value = -4.000000
x = 01
y = 10

Performance

The following Table 1 and Figure 1, 2 show the number of function evaluations and the real time for randomly generated three Quadratic M♮-convex function partition problem. It says that the number of function evaluations is O(n^3) and the real time is O(n^5). Note that a function evaluation tooks O(n^2) time in this example. This is "example3.cpp" in the archive.

Table 1. Number of function evaluations and real time. Computed on a Intel Xeon E3-1230 (3.20 Ghz), 8GB memory.

dimension #function evaluations time[sec]
10 670 0.00
20 4179 0.00
30 12876 0.03
40 27955 0.09
50 53860 0.28
60 91967 0.67
70 144638 1.40
80 214593 2.69
90 304786 4.76
100 412745 7.85
110 543028 12.44
120 688715 18.64
130 859950 27.11
140 1052615 37.85
150 1269444 52.16
160 1520255 70.92
170 1844250 97.39
180 2073775 122.14
190 2486862 162.55
200 2892269 210.82
function-evaluation.png

Figure 1. Number of function evaluations vs. dimension n. The green line is for n^3.

realtime.png

Figure 2. Real time vs. dimension n. The green line is for n^5.

References

[1] S. Iwata, S. Moriguchi and K. Murota: "A capacity scaling algorithm for M-convex submodular flow", Mathematical Programming, Vol.103 (2005), No.1, 181--202.
[2] K. Murota: "Matrices and Matroids for Systems Analysis", Springer-Verlag, 2000.
[3] K. Murota: "Discrete Convex Analysis", SIAM, 2003.

DCP Project

Last Modified: 2012.10.20. / Published: 2012.08.16.

Takanori MAEHARA (maehara@nii.ac.jp)