M♮-Convex Function Partition Problem

• M♮-Convex Function Partition Problem
• Source Code (in C++)
• Usage
• Performance
• References

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.

• mgconv_partition-20120905.tar.gz
• mgconv_partition-20120905.zip

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.

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

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.

Last Modified: 2018.02.17. / Published: 2012.08.16.