File Exchange

## Submodular Function Optimization

version 1.2.0.0 (262 KB) by Andreas Krause

### Andreas Krause (view profile)

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

10 Downloads

Updated 22 Mar 2010

View License

Matlab Toolbox for Submodular Function Optimization (v 2.0)

By Andreas Krause (krausea@gmail.com).
Slides, videos and detailed references available at http://www.submodularity.org

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).

Jean Kaddour

### Jean Kaddour (view profile)

Thanks for that toolbox!

Frank Shen

### Frank Shen (view profile)

pretty helpful! thx

Manuel Osdoba

### Manuel Osdoba (view profile)

Nice toolbox, It saved much time.

Chi-Shuo Chuang

### Chi-Shuo Chuang (view profile)

User-friendly, thanks

Colorado Reed

### Colorado Reed (view profile)

Very helpful; thanks!

### Updates

 22 Mar 2010 1.2.0.0 * 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 15 Nov 2008 1.1.0.0 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! 1 Jul 2008 1.0.0.0 Updated documentation (v.991)
##### MATLAB Release Compatibility
Created with R2009b
Compatible with any release
##### Platform Compatibility
Windows macOS Linux