http://ipa.iwr.uni-heidelberg.de/ipabib/Papers/Lellmann-et-al-09b.pdf
also
(file:///C:/Users/msfcfname/Downloads/dissertation-keysers--modeling-of-image-variability-for-recognition--2006.pdf
Nonlinear deformation models Writing is nature’s way of showing us how sloppy our thinking is. – Guindon Math is nature’s way of showing us how sloppy our writing is. – L. Lamport In this chapter, we discuss different two-dimensional non-linear deformation models for image recognition. The tangent distance as discussed in the previous chapter effectively models global variability of the image, but it is sensitive to local non-linear image transformations, which can be modeled using the approaches presented here. Starting from a true two-dimensional model, we proceed to pseudo-two-dimensional and zero-order deformation models. Experiments show that it is most important to include suitable representations of the local image context of each pixel to increase the recognition performance. With these methods, we achieve very competitive results across five different handwritten character recognition tasks, in particular an error rate of 0.5% on the MNIST task. We also show that the same methods can be used for the categorization of medical images. Using the methods presented here, the previous best error rate of 8.0% on the IRMA-1617 task could be considerably reduced by about one third to 5.3%. In a recent international competition of medical image categorization held within the ImageCLEF 2005 evaluation, the best result among those handed in by twelve groups was achieved using one of the models presented here. Furthermore, improvements in the domain of image sequence recognition (sign language word recognition, gesture recognition) can be achieved by modeling the image variability with these deformation models)
http://projecteuclid.org/download/pdf_1/euclid.jdg/1214429996
RIEMANNIAN STRUCTURES OF PRESCRIBED GAUSSIAN CURVATURE FOR COMPACT 2-MANIFOLDS MELVYN S. BERGER Let (M,g) denote a smooth (say C3 ) compact two-dimensional manifold, equipped with some Riemannian metric g. Then, as is well-known, M admits a metric gc of constant Gaussian curvature c in fact the metrics g and gc can be chosen to be conformally equivalent. Here, we determine sufficient conditions for a given non-simply connected manifold M to admit a Riemannian structure g (conformally equivalent to g) with arbitrarily prescribed (Holder continuous) Gaussian curvature K(x). If the Euler-Poincare characteristic χ(M) of M is negative, the sufficient condition we obtain is that K(x) < 0 over M. Note that this condition is independent of g, and this result is obtained by solving an isoperimetric variational problem for g. If K(x) is of variable sign for χ(M) < 0, or if χ(M) > 0, then the desired critical point may not be an absolute minimum and our methods do not succeed. If χ(M) = 0, our methods apply when K(x) satisfies an integral condition with respect to the given metric g (see § 3) this result is perhaps not unreasonable since, for χ(M) < 0, distinct Riemannian structures on M need not be conformally equivalent. 1. Preliminaries By passing (if necessary) to the orientable two-sheeted covering space of M, we may suppose M is orientable and admits a Riemannian structure with metric tensor g, Gaussian curvature k(x), and volume element dV. If K(x) is a given (Holder continuous) function defined on M, we shall attempt to determine a metric tensor g, conformal with g, whose Gaussian curvature k(x) = K(x) at each point of M, i.e., we shall seek a smooth function a defined on M such that g = e 2σg and k(x) = K(x). To find the equation which will determine σ in terms of the given data K(x), k(x) and g, we recall that in terms of isothermal parameters (u, v) on M an element of arc length can be written ds2 = γ{du2 + dv2 }, and the Gaussian curvature can be written (1) k= -irψogγ)uu + (log r ),,} Setting γ' = γ exp 2σ, in place of γ in (1), we obtain the desired equation
Convex Optimization for Multi-Class Image Labeling with a Novel Family of Total Variation Based Regularizers J. Lellmann, F. Becker and C. Schnorr ¨ Image and Pattern Analysis & HCI Dept. of Mathematics and Computer Science, University of Heidelberg {lellmann,becker,schnoerr}@math.uni-heidelberg.de Abstract We introduce a linearly weighted variant of the total variation for vector fields in order to formulate regularizers for multi-class labeling problems with non-trivial interclass distances. We characterize the possible distances, show that Euclidean distances can be exactly represented, and review some methods to approximate non-Euclidean distances in order to define novel total variation based regularizers. We show that the convex relaxed problem can be efficiently optimized to a prescribed accuracy with optimality certificates using Nesterov’s method, and evaluate and compare our approach on several synthetical and realworld examples. 1. Introduction 1.1. Overview and Motivation The multi-class image labeling problem consists in finding, for each pixel x in the image domain Ω ⊆ R d , a label ℓ(x) ∈ {1, . . . , l} which assigns one of l class labels to x so that the labeling function ℓ adheres to some data fidelity as well as spatial coherency constraints. We consider a partial linearization of this combinatorial problem: Identify label i with the i-th unit vector e i ∈ R l , set E := {e 1 , . . . , el}, and find inf u:Ω→E f(u), f(u) := Z Ω hu(x), s(x)i dx | {z } data term + J(u). | {z } regularizer (1) The data term assigns to each label u(x) = e i a local cost si(x), while the regularizer J enforces the desired spatial coherency. In terms of Markov Random Fields, the data and regularization terms can be thought of as unary and pairwise potentials, respectively. To tackle the combinatorial nature Figure 1. Application of our convex optimization approach to color segmentation. Top row: Original image and segmentation into 12 regions using standard Potts distance. Bottom row: Segmentations using non-uniform distances to selectively suppress background (left) or foreground (right) structures while allowing for fine details in the other regions. Our framework applies not only to color vectors, but to arbitrary local features and data terms. of (1), the problem is relaxed, inf u∈C Z Ω hu(x), s(x)idx + J(u), (2) where C := {u : Ω → R l |ui(x) > 0, Pl i=1 ui(x) = 1} is a convex set which constrains each u(x) to the unit simplex. As the data term was linearized, the local costs s may be arbitrarily complex, possibly derived from a probabilistic model, without affecting the overall problem class. In particular, any convex regularizer J yields a continuous convex problem, which can be globally optimized. It is thus interesting to examine the expressiveness of convex regularizers. In this paper, we study a class of convex total variation (TV) based regularizers, J(u) = Z Ω kD(Au)kF dx , (3)
http://www.esi2.us.es/~mbilbao/combiopt.htm
Combinatorial and Integer Optimization
Karla L. Hoffman (George Mason University)
Manfred Padberg (New York University)
Contents
Introduction
Combinatorial optimization problems are concerned with the efficient allocation of limited resources to meet desired objectives when the values of some or all of the variables are restricted to be integral. Constraints on basic resources, such as labor, supplies, or capital restrict the possible alternatives that are considered feasible. Still, in most such problems, there are many possible alternatives to consider and one overall goal determines which of these alternatives is best. For example, most airlines need to determine crews chedules which minimize the total operating cost; automotive manufacturers may want to determine the design of a fleet of cars which will maximize their share of the market; a flexible manufacturing facility needs to schedule the production for a plant without having much advance notice as to what parts will need to be produced that day. In today's changing and competitive industrial environment the difference between using a quickly derived “solution” and using sophisticated mathematical models to find an optimal solution can determine whether or not a company survives.
The versatility of the combinatorial optimization model stems from the fact that in many practical problems, activities and resources, such as machines, airplanes and people, are indivisible. Also, many problems have only a finite number of alternative choices and consequently can appropriately be formulated as combinatorial optimization problems — the word combinatorial referring to the fact that only a finite number of alternative feasible solutions exists. Combinatorial optimization models are often referred to as integer programming models where programming refers to “planning” so that these are models used in planning where some or all of the decisions can take on only a finite number of alternative possibilities.
Combinatorial optimization is the process of finding one or more best (optimal) solutions in a well defined discrete problem space. Such problems occur in almost all fields of management (e.g., finance, marketing, production, scheduling, inventory control, facility location and layout, data-base management), as well as in many engineering disciplines (e.g., optimal design of waterways or bridges, VLSI-circuitry design and testing, the layout of circuits to minimize the area dedicated to wires, design and analysis of data networks, solid-waste management, determination of ground states of spin-glasses, determination of minimum energy states for alloy construction, energy resource-planning models, logistics of electrical power generation and transport, the scheduling of lines in flexible manufacturing facilities, and problems in crystallography). A survey of related applications of combinatorial optimization was given in Grötschel (1992).
We assume throughout this discussion that both the function to be optimized and the functional form of the constraints restricting the possible solutions are linear functions. Although some research has centered on approaches to problems where some or all of the functions are nonlinear, most of the research to date covers only the linear case. A survey of nonlinear integer programming approaches was given in Cooper and Farhangian (1985).
The general linear integer model is
subject to:
where B is the set of zero-one variables, I is the set of integer variables, C is the set of continuous variables, and the ~ symbol in the first set of constraints denotes the fact that the constraints I = 1, …, m can be either ≤, ≥, or =. The data lj and uj are the lower and upper bound values, respectively, for variable xj. As we are discussing the integer case, there must be some variable in B union I. If C and I are equal to the empty set, then the problem is referred to as a pure 0–1 linear-programming problem; if C is the empty set, the problem is called a pure integer (linear) programming problem. Otherwise, the problem is a mixed integer (linear) programming problem. Throughout this discussion, we will call the set of points satisfying all constraints S, and the set of points satisfying all but the integrality restrictions P.
Some applications of combinatorial optimization
We describe some classical combinatorial optimization models to provide both an overview of the diversity and versatility of this field and to show that the solution of large real-world instances of such problems requires the solution method exploit the specialized mathematical structure of the specific application.
Knapsack problems — Suppose one wants to fill a knapsack that can hold a total weight of W with some combination of items from a list of n possible items each with weight wi and value vi so that the value of the items packed into the knapsack is maximized. This problem has a single linear constraint (that the weight of the items in the knapsack not exceed W), a linear objective function which sums the values of the items in the knapsack, and the added restriction that each item either be in the knapsack or not — a fractional amount of the item is not possible. For solution approaches specific to the knapsack problem, see Martello and Toth (1990).
Although this problem might seem almost too simple to have much applicability, the knapsack problem is important to cryptographers and to those interested in protecting computer files, electronic transfers of funds and electronic mail. These applications use a “key” to allow entry into secure information. Often the keys are designed based on linear combinations of some collection of data items which must equal a certain value. This problem is also structurally important in that most integer programming problems are generalizations of this problem (i.e., there are many knapsack constraints which together compose the problem). Approaches for the solution of multiple knapsack problems are often based on examining each constraint separately.
An important example of a multiple knapsack problem is the capital budgeting problem. This problem is one of finding a subset of the thousands of capital projects under consideration that yields the greatest return on investment, while satisfying specified financial, regulatory and project relationship requirements (Markowitz and Manne, 1957; Weingartner, 1963).
Network and graph problems — Many optimization problems can be represented by a network where a network (or graph) is defined by nodes and by arcs connecting those nodes. Many practical problems arise around physical networks such as city streets, highways, rail systems, communication networks, and integrated circuits. In addition, there are many problems which can be modeled as networks even when there is no underlying physical network. For example, one can think of the assignment problem where one wishes to assign a set of persons to some set of jobs in a way that minimizes the cost of the assignment. Here one set of nodes represents the people to be assigned, another set of nodes represents the possible jobs, and there is an arc connecting a person to a job if that person is capable of performing that job.
Space-time networks are often used in scheduling applications. Here one wishes to meet specific demands at different points in time. To model this problem, different nodes represent the same entity at different points in time. An example of the many scheduling problems that can be represented as a space-time network is the airline fleet assignment problem, which requires that one assign specific planes to pre-scheduled flights at minimum cost. Each flight must have one and only one plane assigned to it, and a plane can be assigned to a flight only if it is large enough to service that flight and only if it is on the ground at the appropriate airport, serviced and ready to depart when the flight is scheduled to take off. The nodes represent specific airports at various points in time and the arcs represent the flows of airplanes of a variety of types into and out of each airport. There are layover arcs that permit a plane to stay on the ground from one time period to the next, service arcs which force a plane to be out of duty for a specified amount of time, and connecting arcs which allow a plane to fly from one airport to another without passengers. A general survey of network applications is given inAhuja et al. (1993) and solution procedures in Ahuja et al. (1995).
In addition, there are many graph-theoretic problems which examine the properties of the underlying graph or network. Such problems include the Chinese postman problemwhere one wishes to find a path (a connected sequence of edges) through the graph that starts and ends at the same node, that covers every edge of the graph at least once, and that has the shortest length possible. If one adds the restriction that each node must be visited exactly one time and drops the requirement that each edge be traversed, the problem becomes the notoriously difficult traveling salesman problem. Other graph problems include the vertex coloring problem, the object of which is to determine the minimum number of colors needed to color each vertex of the graph in order that no pair of adjacent nodes (nodes connected by an edge) share the same color; the edge coloring problem, whose object is to find a minimum total weight collection of edges such that each node is incident to at least one edge; the maximum clique problem, whose object is to find the largest subgraph of the original graph such that every node is connected to every other node in the subgraph; and the minimum cut problem, whose object is to find a minimum weight collection of edges which (if removed) would disconnect a set of nodes s from a set of nodes t.
Although these combinatorial optimization problems on graphs might appear, at first glance, to be interesting mathematically but have little application to the decision making in management or engineering, their domain of applicability is extraordinarily broad. The traveling salesman problem has applications in routing and scheduling, in large scale circuitry design and in strategic defense. The four-color problem (Can a map be colored in four colors or less?) is a special case of the vertex coloring problem. Both the clique problem and the minimum cut problem have important implications for the reliability of large systems.
Approximating nonlinear functions by piecewise linear functions — The versatility of the integer programming model might best be exemplified by the fact that many nonlinear programming problems can be modeled as mixed-integer linear programs. The “trick” in this case, is to find a piecewiselinear approximation to each nonlinear function. The simplest example of such a transformation is the fixed charge problem where the cost function has both a fixed charge for initiating the activity as well as marginal costs associated with activities. One example of a fixed-charge problem is the facility location problem where one wishes to locate facilities such that the combined cost of building the facility (a one time fixed cost) and the cost of production and shipping to customers (marginal costs based on the amount shipped and produced) is minimized. The fact that nothing can be produced in the facility unless the facility exists, creates a discontinuity in the cost function at zero. This function can be transformed to a linear function by the introduction of additional variables that take on only the values zero or one. Similar transformations allow one to model separable nonlinear functions as integer (linear) programming problems.
Scheduling problems which are rule-based — There are many problems where it is impossible to write down all of the restrictions in a mathematically “clean” way. Such problems often arise in scheduling where there are a myriad of labor restrictions, corporate scheduling preferences and other rules related to what constitutes a “feasible schedule.” Such problems can be solved by generating all, or some reasonable large subset of the feasible schedules for each worker. One associates a matrix with such problems whose rows correspond to the tasks considered and whose columns correspond to individual workers, teams or crews. A column of the matrix has an entry of one in those rows that correspond to tasks that the worker will be assigned and a zero otherwise. Each “feasible” schedule defines one column of the constraint matrix and associated with each such schedule is a value. Thus the matrix of constraints consists of all zeroes and ones and the sense of the inequality indicates whether that job must be covered by exactly a specified number of people (called set partitioning), that it must be covered by at least a specific number (called set covering) or that it must be covered by not more than a specified number (called set packing). The optimization problem is then the problem of finding the best collection of columns which satisfy these restrictions. Surveys on set partitioning, covering and packing, are given in Balas and Padberg (1976) and Padberg (1979).
Formulation considerations
The versatility of the integer programming formulation, as illustrated by the above examples, should provide sufficient explanation for the high activity in the field of combinatorial optimization which is concerned with developing solution procedures for such problems. Since there are often different ways of mathematically representing the same problem, and since obtaining an optimal solution to a large integer programming problem in a reasonable amount of computer time may well depend on the way it is “formulated,” much recent research has been directed toward the reformulation of integer programming problems. In this regard, it is sometimes advantageous to increase (rather than decrease) the number of integer variables, the number of constraints or both. More will be said about this in the section on solution techniques for integer programming. Discussions of alternative formulation approaches are given in Guignard and Spielberg (1981) and Williams (1985) and a description of approaches to “automatic” reformulation or preprocessing are described in Andersen and Andersen (1995), Brearley, Mitra and Williams (1975) and Hoffman and Padberg (1991). We now give a short description of solution approaches to these problems.
Recently, a variety of difficult problems have been solved by reformulating them as either set-covering or set-partitioning problems having an extraordinary number of variables. Because, for even small instances of the problem, the problem size cannot be explicitly solved, techniques known as column generation, which began with the seminal work of Gilmore and Gomory (1961) on the cutting stock problem, are employed. An overview of such transformations methods can be found in Barnhart et al. (1998). For specific implementations to the vehicle routing problem, see Desrochers et al. (1989); for the bandwidth packing problem, see Parker and Ryan (1994); for the generalized assignment problem, see Savelsbergh (1997); and for alternative column-generation strategies for solving the cutting stock problem, see Barnhart et al. (1998).
Bramel and Simchi-Levi (1997) have shown that the set-partitioning formulation for the vehicle routing problem with time windows is a tight formulation, that is, the relative gap between the fractional linear programming solutions and the global integer solution are close. Similar results have been obtained for the bin-packing problem (Chan et al., 1998) and for the machine-scheduling problem (Chang et al., 1998).
Once the problem has been formulated (or reformulated) into an integer programming problem, solution approaches for obtaining optimal — or at least near optimal — solutions must be found. We now give a short description of solution approaches to these large, combinatorial difficult optimization problem.
Solution techniques for integer programming
Solving combinatorial optimization problems, that is, finding an optimal solution to such problems, can be a difficult task. The difficulty arises from the fact that unlike linear programming, for example, whose feasible region is a convex set, in combinatorial problems, one must search a lattice of feasible points or, in the mixed-integer case, a set of disjoint halflines or line segments to find an optimal solution. Thus, unlike linear programming where, due to the convexity of the problem, we can exploit the fact that any local solution is a global optimum, integer programming problems have many local optima and finding a global optimum to the problem requires one to prove that a particular solution dominates all feasible points by arguments other than the calculus-based derivative approaches of convex programming.
There are, at least, three different approaches for solving integer programming problems, although they are frequently combined into “hybrid” solution procedures in computational practice. They are:
- enumerative techniques;
- relaxation and decomposition techniques; and
- cutting planes approaches based on polyhedral combinatorics.
Enumerative approaches — The simplest approach to solving a pure integer programming problem is to enumerate all finitely many possibilities. However, due to the “combinatorial explosion” resulting from the parameter “size,” only the smallest instances could be solved by such an approach. Sometimes one can implicitly eliminate many possibilities by domination or feasibility arguments. Besides straightforward or implicit enumeration, the most commonly used enumerative approach is called branch and bound, where the “branching” refers to the enumeration part of the solution technique and bounding refers to the fathoming of possible solutions by comparison to a known upper or lower bound on the solution value (Land and Doig, 1960). To obtain an upper bound on the problem (we presume a maximization problem), the problem is relaxed in a way which makes the solution to the relaxed problem, relatively easy to solve.
All commercial branch-and-bound codes relax the problem by dropping the integrality conditions and solve the resultant continuous linear programming problem over the setP. If the solution to the relaxed linear programming problem satisfies the integrality restrictions, the solution obtained is optimal. If the linear program is infeasible, then so is the integer program. Otherwise, at least one of the integer variables is fractional in the linear programming solution. One chooses one or more such fractional variables and “branches” to create two or more subproblems which exclude the prior solution but do not eliminate any feasible integer solutions. These new problems constitute on a branching tree, and a linear programming problem is solved for each node created. Nodes can be fathomed if the solution to the subproblem is infeasible, satisfies all of the integrality restrictions, or has an objective function value worse than a known integer solution. A variety of strategies that have been used within the general branch-and-bound framework is described in Johnson and Powell (1978).
Lagrangian Relaxation and Decomposition Methods — Relaxing the integrality restriction is not the only approach to relaxing the problem. An alternative approach to the solution to integer programming problems is to take a set of “complicating” constraints into the objective function in a Lagrangian fashion (with fixed multipliers that are changed iteratively). This approach is known as Lagrangian relaxation. By removing the complicating constraints from the constraint set, the resulting sub-problem is frequently considerably easier to solve. The latter is a necessity for the approach to work because the subproblems must be solved repetitively until optimal values for the multipliers are found. The bound found by Lagrangian relaxation can be tighter than that found by linear programming, but only at the expense of solving subproblems inintegers, that is, only if the subproblems do not have the Integrality Property. (A problem has the integrality property if the solution to the Lagrangian problem is unchanged when the integrality restriction is removed). Lagrangian relaxation requires that one understand the structure of the problem being solved in order to then relax the constraints that are “complicating” (Fisher, 1981). A related approach which attempts to strengthen the bounds of Lagrangian relaxation, is called Lagrangian decomposition (Guignard and Kim, 1987). This approach consists of isolating sets of constraints so as to one obtain separate, easy problems to solve over each of the subsets. The dimension of the problem is increased by creating linking variables which link the subsets. All Lagrangian approaches are problem dependent and no underlying general theory — applicable to say, an arbitrary zero-one problems — has evolved.
Most Lagrangian-based strategies provide approaches which deal with special row structures. Other problems may possess special column structure, such that when some subset of the variables are assigned specific values, the problem reduces to one that is easy to solve. Benders decomposition algorithm fixes the complicating variables, and solves the resulting problem iteratively (Benders, 1962). Based on the problem's associated dual, the algorithm must then find a cutting plane (i.e., a linear inequality) which “cuts off” the current solution point but no integer feasible points. This cut is added to the collection of inequalities and the problem is resolved.
Since each of the decomposition approaches described above provide a bound on the integer solution, they can be incorporated into a branch and bound algorithm, instead of the more commonly used linear programming relaxation. However, these algorithms are special-purpose algorithms in that they exploit the “constraint pattern” or special structure of the problem.
Cutting Plane algorithms based on polyhedral combinatorics — Significant computational advances in exact optimization have taken place. Both the size and the complexity of the problems solved have been increased considerably when polyhedral theory, developed over the past twenty five years, was applied to numerical problem solving. The underlying idea of polyhedral combinatorics is to replace the constraint set of an integer programming problem by an alternative convexification of the feasible points and extreme rays of the problem.
H. Weyl (1935) established the fact that a convex polyhedron can alternatively be defined as the intersection of finitely many halfspaces or as the convex hull plus the conical hull of some finite number of vectors or points. If the data of the original problem formulation are rational numbers, then Weyl's theorem implies the existence of a finite system of linear inequalities whose solution set coincides with the convex hull of the mixed-integer points in S which we denote conv(S). Thus, if we can list the set of linear inequalities that completely define the convexification of S, then we can solve the integer programming problem by linear programming. In this context, Gomory (1958)derived a “cutting plane” algorithm for integer programming problems which can be viewed as a constructive proof of Weyl's theorem.
Although Gomory's algorithm converges to an optimal solution in finite number of steps, the convergence to an optimum is extraordinarily slow due to the fact that these algebraically-derived cuts are “weak” in the sense that they frequently do not even define supporting hyperplanes to the convex hull of feasible points. Since one is interested in a linear constraint set for conv(S) which is as small as possible, one is led to the consider minimal systems of linear inequalities such that each inequality defines a facet of the polyhedron conv(S). When viewed as cutting planes for the original problem then the linear inequalities that define facets of the polyhedron conv(S) are “best possible” cuts — they cannot be made “stronger” in any sense of the word without losing some feasible integer or mixed-integer solutions to the problem. Considerable research activity has focused on identifying part (or all) of those linear inequalities for specific combinatorial optimization problems — problem-dependent implementations, of course, that are however derived from an underlying general theme due to Weyl's theorem which applies generally. Since for most interesting integer-programming problems the minimal number of inequalities necessary to describe this polyhedron is exponential in the number of variables, one is led to wonder whether such an approach could ever be computationally practical. It is therefore all the more remarkable that the implementation of cutting plane algorithms based on polyhedral theory has been successful in solving problems of sizes previously believed intractable. The numerical success of the approach can be explained, in part, by the fact that we are interested in provingoptimality of a single extreme point of conv(S). We therefore do not require the complete description of S but rather only a partial description of S in the neighborhood of the optimal solution.
Thus, a general cutting plane approach relaxes in a first step the integrality restrictions on the variables and solves the resulting linear program over the set P. If the linear program is unbounded or infeasible, so is the integer program. If the solution to the linear program is integer, then one has solved the integer program. If not, then one solves a facet-identification problem whose objective is to find a linear inequality that “cuts off” the fractional linear programming solution while assuring that all feasible integer points satisfy the inequality — that is, an inequality that “separates” the fractional point from the polyhedron conv(S). The algorithm continues until: 1) an integer solution is found (we have successfully solved the problem); 2) the linear program is infeasible and therefore the integer problem is infeasible; or 3) no cut is identified by the facet-identification procedures either because a full description of the facial structure is not known or because the facet-identification procedures are inexact, that is, one is unable to algorithmically generate cuts of a known form. If we terminate the cutting plane procedure because of the third possibility, then, in general, the process has “tightened” the linear programming formulation so that the resulting linear programming solution value is much closer to the integer solution value. We next explain how much of the research and development of integer programming methods can be incorporated into a super-algorithm which uses all that is known about the problem. This method is called “branch-and-cut” (Padberg and Rinaldi, 1991; Hoffman and Padberg, 1985, 1991, 1993).
The major components of this algorithm consist of automatic reformulation procedures, heuristics which provide “good” feasible integer solutions, and cutting plane procedures which tighten the linear programming relaxation to the combinatorial problem under consideration — all of which is embedded into a tree-search framework as in the branch-and-bound approach to integer programming. Whenever possible, the procedure permanently fixes variables (by reduced cost implications and logical implications) and does comparable conditional fixing throughout the search-tree. These four components are combined so as to guarantee optimality of the solution obtained at the end of the calculation. However, the algorithm may also be stopped early to produce suboptimal solutions along with a bound on the remaining error. The cutting planes generated by the algorithm are facets of the convex hull of feasible integer solutions or good polyhedral approximations thereof and as such they are the “tightest cuts” possible. Lifting procedures assure that the cuts generated are valid throughout the search tree which aids the search process considerably and is a substantial difference to traditional (Gomory) cutting-pane approaches.
Mounting empirical evidence indicates that both pure and mixed integer programming problems can be solved to proven optimality in economically feasible computation times by methods based on the polyhedral structure of integer programs. For applications which use this branch-and-cut approach, see, among others, Barahona et al. (1988),Chopra et al. (1991), Grötschel et al. (1989), Magnanti and Vachani (1990), Pochet and Wolsey (1991), and Van Roy and Wolsey (1987). A direct outcome of these research efforts is that similar preprocessing and constraint generation procedures can be found in commercial software packages for combinatorial problems.
The computational successes for difficult combinatorial optimization problems reflects the intense effort devoted to developing the underlying polyhedral structure of these problems. Thus, to use this approach, one must be able to both identify specific mathematical structures inherent in the problem and then study the polyhedron associated with that structure. As more structures are understood, and can be detected automatically, we will see larger classes of problems solved by these methods. These codes will certainly be complex, but they are likely to lead to methods for solving to optimality — with reasonable computational effort — many of the difficult combinatorial problems for which only heuristic “guesses” are known today. Different from decomposition methods, the related computational successes are based on a mathematical understanding of the problem and not just the “structure,” that is, the particular constraint “pattern” itself.
We briefly note some topics related to combinatorial and integer programming. One such topic is the complexity of integer programming problems (Garey and Johnson, 1979). Another topic is that of heuristics solution approaches — that is, techniques for obtaining “good” but not necessarily optimal solutions to integer programming problems quickly and, in general, without any guarantee as to their “closeness” to an optimal solution. Heuristics are, however, important for a variety of reasons. They may provide the only usable solution to very difficult optimization problems for which the current exact algorithms are incapable of providing an optimal solution in reasonable times; when heuristics are used within an exact algorithm, they provide a bound to fix variables and to fathom branches on a search-tree. Recent research into heuristic algorithms has applied techniques from the physical sciences to the approximate solution of combinatorial problems. For surveys of research in simulated annealing (based on the physical properties of heat), genetic algorithms (based on properties of natural mutation) and neural networks (models of brain function), see Hansen (1986),Mühlenbein (1992), and Beyer and Ogier (1991), respectively. Glover and Laguna (1992) has generalized some of the attributes of these methods into a method called tabu-search. Worst-case and probabilistic analysis of heuristics are discussed in Cornuejols et al. (1980), Rinnooy Kan (1986), and Karp (1976). A more recent area of research relates issues in computational logic to those associated with combinatorial optimization, see McAloon and Tretkoff (1996). For general text books on integer programming and related topics, Grötschel, Lovasz and Schrijver (1988), Nemhauser and Wolsey (1988), Padberg (1995), Padberg and Rijal (1996), Parker and Rardin (1988), andSchrijver (1986).
References
Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. (1993). Network Flows: Theory, Algorithms and Applications. Prentice-Hall, New Jersey.
Ahuja, R. K., Magnanti, T. L., Orlin, J. B., and Reddy, M. R. (1995). “Applications of Network Optimization,” Chapter 1 of Handbooks of Operations Research and Management Science, Vol. 7, Network Models, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, Elsevier North Holland, 1–84.
Anderson, E. D. and Anderson, K. D. (1995). “Presolving in Linear Programing,” Mathematical Programming, 71, 221–245.
Balas, E. and Padberg, M. (1976). “Set Partitioning: A Survey,” SIAM Review, 18, 710–760.
Barahona, M., Grötschel, M., Jünger, G., and Reinelt, G. (1988). “An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design,” Operations Research, 36, 493–513.
Barnhart, C., Johnson, E. D., Nemhauser, G. L., Savelsbergh, M. W. P., and Vance, P. H. (1998). “Branch and Price Column Generation for Solving Huge Integer Programs,” Operations Research, 46, 316–329.
Benders, J. F. (1962). “Partitioning Procedures for Solving Mixed-variables Programming Problems,” Numerische Mathematik, 4, 238–252.
Beyer, D. and Ogier, R. (1991). “Tabu Learning: a Neural Network Search Method for Solving Nonconvex 0ptimization Problems,” Proceedings of the International Joint Conference on Neural Networks. IEEE and INNS, Singapore.
Bramel, J. and Simchi-Levi, D. (1998). On the effectiveness of set covering formulations for the vehicle routing problem with time windows” Technical Report, Dept. of Industrial Engineering and Mgmt. Sci., Northwestern University, Evanston, Illinois.
Brearley, A. L., Mitra, G., and Williams, H. P. (1975). “Analysis of mathematical programming problems prior to applying the simplex method,” Mathematical Programming, 8, 54–83.
Chan, L. M. A., Muriel, A., and Simchi-Levi, D. (1998). “Parallel machine scheduling, linear programming and parameter list scheduling heuristics,” Technical Report, Dept. of Industrial Engineering and Mgmt. Sci., Northwestern University, Evanston, Illinois.
Chang, L. M. A., Simchi-Levi, D., and Bramel, J. (1998). “Worst-case analysis, linear programming and the bin-packing problem,” Technical Report, Dept of Industrial Engineering and Mgmt. Sci., Northwestern University, Evanston, Illinois.
Chopra, S., Gorres, E., and Rao, M. R. (1992). “Solving the Steiner tree problem on a graph using branch and cut,” ORSA Journal on Computing, 4, 320–335.
Cooper, M. W. and Farhangian, K. (1985). “Multicriteria optimization for nonlinear integer-variable problems,” Large Scale Systems, 9, 73–78.
Cornuejols, G., Nemhauser, G. L., and Wolsey, L. A. (1980). “Worst case and probabilistic analysis of algorithms for a location problem,” Operations Research, 28, 847–858.
Desrochers, M. and Sosumis, F. (1989) “A column generation approach to the urban transit crew scheduling problem,” Transportation Science, 23, 1–13.
Fisher, M. L. (1981). “The Lagrangian method for solving integer programming problems,” Management Science, 27, 1–18.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.
Gilmore, P. C. and Gomory, R. E. (1961). “A linear programming approach to the cutting stock problem,” Operations Research, 9, 849–859.
Glover, F. and Laguna, M. (1993). “Tabu Search,” in Modern Heuristic Techniques for Combinatorial Optimization, C. R. Reeves, ed. Scientific Pubs., Oxford, England, 71–140.
Gomory, R. E. (1958). “Outline of an algorithm for integer solution to linear programs,” Bulletin American Mathematical Society, 64, 275–278.
Gomory, R. E. (1960). “Solving linear programming problems in integers,” Combinatorial Analysis, R. E. Bellman and M. Hall, Jr., eds., American Mathematical Society, 211–216.
Grötschel, M. (1992). “Discrete mathematics in manufacturing,” Preprint SC92-3, ZIB.
Grötschel, M., Lovasz, L., and Schrijver, A. (1988). Geometric Algorithms and Combinatorial Optimization, Springer, Berlin.
Grötschel, M., Monma, C. L., and Stoer, M. (1989). “Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraint,” Report No. 187, Schwerpunktprogramm der Deutschen Forschungs-gemeinschaft, Universität Augsburg.
Guignard, M. and Spielberg, K. (1981). “Logical Reduction Methods in Zero-one Programming: Minimal Preferred Inequalities,” Operations Research, 29, 49–74.
Guignard, M. and Kim, S. (1987). “Lagrangian decomposition: a model yielding stronger Lagrangian bounds,” Mathematical Programming, 39, 215–228.
Hansen, P. (1986). “The steepest ascent mildest descent heuristic for combinatorial programming,” Proceedings of Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.
Hansen, P., Jaumard, B., and Mathod, V. (1993) “Constrained nonlinear 0–1 programming” INFORMS Journal on Computing, 5, 97–119.
Hoffman, K. L. and Padberg, M. (1985). “LP-based Combinatorial Problem Solving,” Annals Operations Research, 4, 145–194.
Hoffman, K. L. and Padberg, M. (1991). “Improving the LP-representation of zero-one linear programs for branch-and-cut,” ORSA Journal Computing, 3, 121–134.
Hoffman, K. L. and Padberg, M. (1993). “Solving air-line crew scheduling problems by branch-and-cut,” Management Science, 39, 657–682.
Johnson, E. L. and Powell, S. (1978). “Integer programming codes,” Design and Implementation of Optimization Software (ed. H. J. Greenberg), NATO Advanced Study Institute Series, Sijthoff & Noordhoff, 225–248.
Karp, R. M. (1976). “Probabilistic analysis of partitioning algorithms for the traveling salesman problem,” in Algorithms and Complexity: New Directions and Recent Results (J. F. Traub, ed.) Academic Press, New York, 1–19.
Land, A. H. and Doig, A. G. (1960). “An automatic method for solving discrete programming problems,” Econometrica, 28, 97–520.
Magnanti, T. L. and Vachani, R. (1990). “A strong cutting plane algorithm for production scheduling with changeover costs,” Operations Research, 38, 456–473.
Martello, S. and Toth, P. (1990). Knapsack Problems, John Wiley, New York.
Markowitz, H. and Manne, A. (1957). “On the solution of discrete programming problems,” Econometrica, 2, 84–110.
McAloon, K. and Tretkoff, C. (1996). Optimization and Computational Logic, John Wiley, New York.
Mühlenbein, H. (1992). “Parallel genetic algorithms in combinatorial optimization,” Computer Science and Operations Research, Osman Blaci, ed., Pergamon Press, New York.
Nemhauser, G. L. and Wolsey, L. A. (1988). Integer and Combinatorial Optimization, John Wiley, New York.
Padberg, M. (1979). “Covering, packing and knapsack problems,” Mathematical Programming, 47, 19–46.
Padberg, M. (1995). Linear Optimization and Extensions, Springer Verlag, Heidelberg.
Padberg, M. and Rijal, M. P. (1996) Location Scheduling and Design in Integer Programming,” Kluwer Academic, Norwell, Massachusetts.
Padberg, M. and Rinaldi, G. (1991). “A branch–and cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Review, 33, 60–100.
Parker, R. G. and Rardin, R. L. (1988). Discrete Optimization, Academic Press, San Diego.
Pochet, Y. and Wolsey, L. A. (1991). “Solving Multi-item Lot Sizing Problems Using Strong Cutting Planes,” Management Science, 37, 53–67.
Rinooy Kan, A. H. G. (1986). “An introduction to the analysis of approximation algorithms,” Discrete Applied Mathematics, 14, 111–134.
Savelsbergh, M. W. P. (1997). “A branch-and-price algorithm for the generalized assignment problem,” Operations Research, 45, 831–841.
Schrijver, A. (1984). Linear and Integer Programming, John Wiley, New York.
Van Roy, T. J. and Wolsey, L. A. (1987). “Solving Mixed Integer Programming Problems Using Automatic Reformulation,” Operations Research, 35, 45–57.
Weingartner, H. (1963). Mathematical Programming and the Analysis of Capital Budgeting Problems, Prentice Hall, Englewood Cliffs, New Jersey.
Weyl, H. (1935). “Elementare Theorie der konvexen Polyheder,” Comm. Math. Helv, 7, 290 (Translated in Contributions to the Theory of Games, 1(3), 1950).
Williams, H. P. (1985). Model Building in Mathematical Programming, 2nd ed. John Wiley, New York.
This text originally appeared in Encyclopedia of Operations Research and Management Science (ISBN 079237827x)
[PDF]Convex Optimization for Multi-Class Image Labeling with a ...
ipa.iwr.uni-heidelberg.de/ipabib/Papers/Lellmann-et-al-09b.pdf
by J Lellmann - Cited by 45 - Related articles
that the labeling function ℓ adheres to some data fidelity as well as spatial coherency ... In terms of Markov Random Fields, the data and regularization terms can ...
You visited this page on 3/27/16.
[PDF]Convex Multi-Class Image Labeling by Simplex ...
hci.iwr.uni-heidelberg.de/.../lellmann08multiclasst...
Heidelberg University
by J Lellmann - Cited by 90 - Related articles
Nov 6, 2008 - each pixel x ∈ Ω into one out of L classes, based on an arbitrary ... setting, which – under anisotropic discretization – can be solved using graph cuts. ...... with pairwise relationships: Metric labeling and markov random fields.[PDF]Convex Multi-Class Image Labeling by Simplex ...
ipa.iwr.uni-heidelberg.de/dokuwiki/Papers/Lellmann-et-al-09a.pdf
by J Lellmann - Cited by 90 - Related articles
each pixel x ∈ Ω into one out of L classes, based on an arbitrary vector-valued similarity function ... In contrast to the binary case with anisotropic discretization [2[PDF]preprint - Biomedical Imaging Group - EPFL
bigwww.epfl.ch/.../storath201...
École Polytechnique Fédérale de Lausanne
by M Storath - Cited by 1 - Related articles
1, we get the simple (anisotropic) discretization which cor- responds to ∇uij ..... [[PDF]Preprint - Biomedical Imaging Group - EPFL
bigwww.epfl.ch/.../storath140...
École Polytechnique Fédérale de Lausanne
by M STORATH - Cited by 11 - Related articles
discrepancy principle [47] or the L-curve method [35]. In this paper we choose the .... (b) Anisotropic discretization. (13.4 sec). ...... Markov random fields with smoothness-based priors, IEEE Transactions on Pattern Anal- ysis and Machine[PDF]cmap.polytechnique.fr - Ecole polytechnique
blanche.polytechnique.fr/preprint/repository/578.pdf
by A Chambolle - 2005 - Cited by 289 - Related articles
Jun 20, 2005 - Providing a sharp a posteriori L2 or, even better, L∞ error estimate for the ... Exact optimization for Markov random fields with convex pri- ors.[PDF]Convex Optimization for Multi-Class Image Labeling with a ...
https://pdfs.semanticscholar.org/.../534cfd97142a59d6e4b03a035d36fa2...
by J Lellmann - Cited by 45 - Related articles
In terms of Markov Random Fields, the data and regularization terms can be ... losing global optimality. For anisotropic discretization, the binary case can be for-.[PDF]Joint Image Reconstruction and Segmentation Using the ...
arxiv.org/pdf/1405.5850
arXiv
by M Storath - 2014 - Cited by 7 - Related articles
explaining the basic approach using an anisotropic discretization of (1). ... The constraints are now part of the (multivariate) target functional L. The parameter ...... Image Analysis, Random Fields and Markov Chain Monte Carlo Methods: A.[PDF]137 - Mathematical and Statistical Sciences
www.math.ualberta.ca/ijnam/...8.../2011-01-08.pdf
University of Alberta
by XUEC TAI - Cited by 10 - Related articles
consider anisotropic discretization of the TV term. .... Choose initial values for c0, setl = 0. ...... Exact optimization for Markov random fields with convex priors.[PDF]DOMAIN DECOMPOSITION METHODS WITH GRAPH ...
ftp://ftp.math.ucla.edu/.../cam09-54...
University of California, Los Angeles
by XUEC TAI - Cited by 10 - Related articles
we consider anisotropic discretization of the TV term. The anisotropic discretizationdepends on the .... c(vp,l,vq,l) = γ · wpq, ∀p ∈ P, ∀q ∈ Nk(p), ∀l ∈ 1,...n − 1. (3.14) ..... Exact optimization for Markov random fields with convex priors.
Contents
No comments:
Post a Comment