This chapter introduces the structure of the book and reviews the elements of algebra, graphs, networks and linear inequalities. The concepts of submodular and supermodular systems and their associated base polyhedra by following the historical generalization sequence of matroids, polymatroids and submodular systems are introduced. The algorithmic aspects of submodular systems and basic structures of base polyhedra are considered. A class of network flow problems with submodular boundary constraints, which is called the neoflow problem, is discussed. Submodular functions are discrete analogues of convex functions. A theory of submodular functions from the point of view of convex analysis, which is called the submodular analysis, is developed. The nonlinear optimization problems with submodular constraints are considered. The chapter also considers a neoflow problem (the submodular flow problem) with a separable convex cost function.

This chapter discusses the basic concepts on matroids, polymatroids and submodular systems and shows the natural generalization sequences of these concepts from matroids to submodular systems. The fundamental combinatorial structures of submodular systems and associated polyhedra are examined. A matroid is an abstraction of linear independence and dependence structure of the set of columns of a matrix. Matroids and polymatroids are examples of a submodular system. Some nonpolymatroidal submodular systems are (1) cut functions; (2) cross-free families; (3) submodular functions arising from concave functions; and (4) Monge matrices. The chapter discusses the basic properties of submodular systems. A linear optimization problem over the base polyhedron is considered and an algorithm, called a greedy algorithm, for solving the problem is given.

This chapter considers the generalizations of classical flow problems of Ford and Fulkerson to flow problems with boundary constraints described by submodular functions. The flow problems discussed in the chapter are the submodular flow problem, the independent flow problem and the polymatroidal flow problem, and they are equivalent. Thus, the class of these flow problems and other possible equivalent ones, the neoflow problem. A theory and algorithms for the neoflow problem are given. The problem of finding a maximum common sub-base of two submodular systems and some related problems is discussed. Discrete separation theorem is proved by the use of the intersection theorem. The chapter discusses the equivalence among the neoflow problems and gives algorithms for solving them. The equivalence is with respect to the capability of modeling flow problems. Different models may require different oracles for algorithms.

This chapter discusses the submodular analysis. Submodular (or supermodular) functions on distributive lattices share similar structures with convex (or concave) functions on convex sets. The chapter develops a theory of submodular and supermodular functions based on the duality in convex analysis. The convex (concave) conjugate function of a submodular (supermodular) function is defined; and a Fenchel-type duality theorem for submodular and supermodular functions is shown. The chapter also defines the subgradients and subdifferentials of a submodular function and examines the relationship among these concepts and the polyhedra, such as the submodular and supermodular polyhedra and the base polyhedron associated with the submodular function. The chapter considers the optimization problems with objective functions and constraints described by submodular functions, which are called submodular programs. Related to the principal partition, the concept of principal structure of a submodular system is introduced.

This chapter discusses a class of nonlinear optimization problems with constraints described by submodular functions that includes problems of minimizing separable convex functions over base polyhedra with and without integer constraints. Efficient algorithms for solving these problems are also discussed in the chapter. The lexicographically optimal base is unique and that the problem can be solved by the decomposition algorithm. The problem of maximizing the minimum (or minimizing the maximum) of a nonlinear objective function over the base polyhedron B(f) is described. The problem of allocating resources in a fair manner that generalizes the max-min and min-max problems is also considered. The discrete max-min and min-max problems are reduced to continuous ones. The submodular flow problem where the cost function is given by a separable convex function is also considered.

This chapter discusses the developments in algorithms for submodular function minimization. There are problems that rely on algorithms for general submodular function minimization. The min-max relation because of Edmonds is essential in submodular function minimization. The chapter describes a weakly polynomial algorithm for submodular function minimization. The key techniques are augmenting-path and scaling techniques and an exchange operation technique to search for augmenting paths developed for submodular flows. In searching for a δ-augmenting path, the original IFF algorithm interchanges adjacent W- and non W-elements to shift forward each W-element. Schrijver's Algorithm is a combinatorial, strongly polynomial algorithm for submodular function minimization, independently and differently from the IFF algorithm. In Schrijver's algorithm, updating the expression of a current base as a convex combination of affinely independent extreme bases is inevitable to achieve polynomiality of the algorithm, as without such a reduction of the size of the set of extreme bases, the number of extreme bases to express a current base becomes exponential before the algorithm terminates. The chapter describes the further progress in submodular function minimization.

This chapter describes the essence of discrete convex analysis in a compact way with the help of the theory of submodular functions and the ordinary convex analysis. Only polyhedral convex functions are considered. Historical notes about developments in discrete convex analysis are given. The chapter reviews the theory of ordinary convex analysis, focusing on locally polyhedral convex functions, and also gives definitions of some concepts about discrete convexity. There are several operations on base polyhedra that are closed within the class of base polyhedra. Similar operations such as a truncation and its dual can be adapted to define the corresponding operations on M-convex functions. The chapter shows a one-to-one conjugacy correspondence between the set of integer-valued domain-integral L-convex functions and that of integer-valued domain-integral M-convex functions. M-convex functions have the exchange property. The exchange property is adopted as the defining axiom for M-convex functions in Murota's discrete convex analysis. Proximity theorems are concerned with solutions of relaxed or restricted problems modified from an original one and show how close to an optimal solution of the original problem the approximate solutions are.

This chapter introduces the methods for studying the properties of electrical networks, which are independent of the device characteristic. Only topological constraints are used—namely, Krichoff's current law (KCL) and Kirchoff's voltage law (KVL). These methods are also called “network topological.” The chapter presents applications to circuit simulation and circuit partitioning and establishes the relations between the optimization problems that arise naturally, while using these methods, to the central problems in the theory of submodular functions. There are more immediate applications possible. The most popular general purpose simulator currently running—SPICE—uses the modified nodal analysis approach. In this approach, the devices are divided into two classes, generalized admittance type whose currents can be written in terms of voltages appearing somewhere in the circuit, and the remaining devices. The final variables in terms of which the solution is carried out is the set of all nodal voltages and current variables. The resulting coefficient matrix is very sparse but suffers from several defects.

This chapter provides an overview of sets. A set (or collection) is specified by the elements (or members) that belong to it. If element x belongs to the set X, and is written as x ∈ X (x ∉ X). Two sets are equal if they have the same members. A set is finite if it has a finite number of elements. Otherwise, it is infinite. A set is often specified by actually listing its members, for example, {e1, e2, e3}, is the set with members e1, e2, e3. The chapter also describes vectors, matrices, and related notions. The set of all vectors linearly dependent on a collection C of vectors can be shown to form a vector space, which is generated by or spanned by C. Generally, maximal and minimal members of a collection of sets may not be largest and smallest in terms of size.

This chapter discusses graphs and related notions. Graphs should be visualized as points joined by lines with or without arrows rather than be thought of as formal objects. A graph G is a triple (V(G), E(G), iG ) where V(G) i s a finite set of vertices, E(G) is a finite set of edges, and iG is an incidence function, which associates with each edge a pair of vertices, not necessarily distinct, called its end points or end. Vertices are also called “nodes” or “junctions” while edges are also called “arcs” or “branches.” An edge may have a single end point; such edges are called “selfloops.” A vertex may have no edges incident on it; such vertices are isolated. A connected graph with each vertex having degree two is called a “circuit graph” or a “polygon graph.”