Code covered by the BSD License  

Highlights from
Submodular Function Optimization

5.0 | 3 ratings Rate this file 69 Downloads (last 30 days) File Size: 262 KB File ID: #20504 Version: 1.2
image thumbnail

Submodular Function Optimization



28 Jun 2008 (Updated )

This toolbox provides functions for maximizing and minimizing submodular set functions.

| Watch this File

File Information

Matlab Toolbox for Submodular Function Optimization (v 2.0)

By Andreas Krause (
Slides, videos and detailed references available at

Tested in MATLAB 7.0.1 (R14), 7.2.0 (R2006a), 7.4.0 (R2007a, MAC), 7.9.0 (MAC)

This toolbox provides functions for optimizing submodular set functions, i.e., functions that take a subset A of a finite ground set V to the real numbers, satisfying

$$F(A)+F(B)\geq F(A\cup B)+F(A\cap B)$$

It also presents several examples of applying submodular function optimization to important machine learning problems, such as clustering, inference in probabilistic models and experimental design. There is a demo script: sfo_tutorial.m

Some information on conventions:

All algorithms will use function objects (see sfo_tutorial.m for examples). For example, to measure variance reduction in a Gaussian model, call
  F = sfo_fn_varred(sigma,V)
where sigma is the covariance matrix and V is the ground set, e.g., 1:size(sigma,1) They will also take an index set V, and A must be a subset of V.

Implemented algorithms:

1) Minimization:

* sfo_min_norm_point: Fujishige's minimum-norm-point algorithm for minimizing general submodular functions
* sfo_queyranne: Queyranne's algorithm for minimizing symmetric submodular functions
* sfo_ssp: Submodular-supermodular procedure of Narasimhan & Bilmes for minimizing the difference of two submodular functions
* sfo_s_t_min_cut: For solving min F(A) s.t. s in A, t not in A
* sfo_minbound: Return an online bound on the minimum solution
* sfo_greedy_splitting: Greedy splitting algorithm for clustering of Zhao et al

2) Maximization:

* sfo_polyhedrongreedy: For solving an LP over the submodular polytope
* sfo_greedy_lazy: The greedy algorithm for constrained maximization / coverage using lazy evaluations
* sfo_greedy_welfare: The greedy algorithm for solving allocation problems
* sfo_cover: Greedy coverage algorithm using lazy evaluations
* sfo_celf: The CELF algorithm of Leskovec et al. for budgeted maximization
* sfo_ls_lazy: Local search algorithm for maximizing nonnegative submodular functions
* sfo_saturate: The _SATURATE_ algorithm of Krause et al. for robust optimization of submodular functions
* sfo_max_dca_lazy: The Data Correcting algorithm of Goldengorin et al. for maximizing general (not necessarily nondecreasing) submodular functions
* sfo_maxbound: Return an online bound on the maximum solution
* sfo_pspiel: pSPIEL algorithm for trading off information and communication cost
* sfo_pspiel_orienteering: pSPIEL algorithm for submodular orienteering
* sfo_balance: eSPASS algorithm for simultaneous placement and balanced scheduling

3) Miscellaneous

* sfo_lovaszext: Computes the Lovasz extension for a submodular function
* sfo_mi_cluster: Example clustering algorithm using both maximization and minimization
* sfo_pspiel_get_path: Convert a tree into a path using the MST heuristic algorithm
* sfo_pspiel_get_cost: Compute the Steiner cost of a tree / path

4) Submodular functions:

* sfo_fn_cutfun: Cut function
* sfo_fn_detect: Outbreak detection / facility location
* sfo_fn_infogain: Information gain about gaussian random variables
* sfo_fn_entropy: Entropy of Gaussian random variables
* sfo_fn_mi: Gaussian mutual information
* sfo_fn_varred: Variance reduction (truncatable, for use in SATURATE)
* sfo_fn_example: Two-element submodular function example from tutorial slides
* sfo_fn_iwata: Iwata's test function for testing minimization code
* sfo_fn_ising: Energy function for Ising model for image denoising
* sfo_fn_residual: For defining residual submodular functions
* sfo_fn_invert: For defining F(A) = F'(V\A)-F(V)
* sfo_fn_lincomb: For defining linear combinations of submodular functions

If you use the toolbox for your research, please cite
A. Krause. "SFO: A Toolbox for Submodular Function Optimization". Journal of Machine Learning Research (2010).

MATLAB release MATLAB 7.9 (R2009b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (3)
11 Jul 2015 Manuel Osdoba

Nice toolbox, It saved much time.

10 Jul 2015 Chi-Shuo Chuang

User-friendly, thanks

31 Jan 2013 Colorado Reed

Very helpful; thanks!

15 Nov 2008 1.1

Changes in version 1.00:
  Added pSPIEL for informative path planning
  Added eSPASS for simultaneous placement and scheduling
  New convention for submodular functions (incremental computations, etc.) Much faster!

22 Mar 2010 1.2

* Modified specification of optional parameters (using sfo_opt)
* Added sfo_ls_lazy for maximizing nonnegative submodular functions
* Added sfo_fn_infogain, sfo_fn_lincomb, sfo_fn_invert, additional documentation and more examples

Contact us