Skip to main content

University Library, University of Illinois at Urbana-Champaign

Combinatorics at the University of Illinois at Urbana-Champaign: Home

Combinatorics and Optimization

"Often we have a working group on research problems. Each summer since 2004 this has taken the form of a REGS group (Research Experiences for Graduate Students) supported initially by our department's VIGRE grant, subsequently by departmental funding, and later by our MCTP grant. The grant has now ended, so for the present the REGS program will not continue on a formal basis.

Our weekly seminars include Graph theory and Combinatorics and Algebra-Geometry-Combinatorics. Weekly details are found in the Mathematics Department seminar schedule. Seminars in theoretical computer science in the Computer Science Department also often discuss topics in discrete mathematics."  from Combinatorics at the University of Illinois at Urbana-Champaign, Department of Mathematics, University of Illinois at Urbana-Champaign

Books on combinatorics and optimization can be found in the Mathemathics Library Stacks shelved under call number ranges 511.6 and 519.6, respectively.

What Is Combinatorics?

"combinatorics, also called combinatorial mathematics,  the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Included is the closely related area of combinatorial geometry.

One of the basic problems of combinatorics is to determine the number of possible configurations (e.g., graphs, designs, arrays) of a given type. Even when the rules specifying the configuration are relatively simple, enumeration may sometimes present formidable difficulties. The mathematician may have to be content with finding an approximate answer or at least a good lower and upper bound.

In mathematics, generally, an entity is said to “exist” if a mathematical example satisfies the abstract properties that define the entity. In this sense it may not be apparent that even a single configuration with certain specified properties exists. This situation gives rise to problems of existence and construction. There is again an important class of theorems that guarantee the existence of certain choices under appropriate hypotheses. Besides their intrinsic interest, these theorems may be used as existence theorems in various combinatorial problems.

Finally, there are problems of optimization. As an example, a function f, the economic function, assigns the numerical value f(x) to any configuration x with certain specified properties. In this case the problem is to choose a configuration x0 that minimizes f(x) or makes it ε = minimal—that is, for any number ε > 0, f(x0f(x) + ε, for all configurations x, with the specified properties."   from "combinatorics." Encyclopaedia Britannica. Encyclopaedia Britannica Online Academic Edition. Encyclopædia Britannica Inc., 2015. Web. 01 Jun. 2015.

"Combinatorics is the branch of mathematics studying the enumerationcombination, and permutation of sets of elements and the mathematical relations that characterize their properties."  from Combinatorics -- from Wolfram MathWorld.



What Is Optimization?

"optimization, also known as mathematical programming,  collection of mathematical principles and methods used for solving quantitative problems in many disciplines, including physicsbiologyengineeringeconomics, and business. The subject grew from a realization that quantitative problems in manifestly different disciplines have important mathematical elements in common. Because of this commonality, many problems can be formulated and solved by using the unified set of ideas and methods that make up the field of optimization.

The historic term mathematical programming, broadly synonymous with optimization, was coined in the 1940s before programming became equated with computer programming. Mathematical programming includes the study of the mathematical structure of optimization problems, the invention of methods for solving these problems, the study of the mathematical properties of these methods, and the implementation of these methods on computers. Faster computers have greatly expanded the size and complexity of optimization problems that can be solved. The development of optimization techniques has paralleled advances not only in computer science but also in operations research,numerical analysisgame theory, mathematical economics, control theory, and combinatorics.

Optimization problems typically have three fundamental elements. The first is a single numerical quantity, or objective function, that is to be maximized or minimized. The objective may be the expected return on a stock portfolio, a company’s production costs or profits, the time of arrival of a vehicle at a specified destination, or the vote share of a political candidate. The second element is a collection of variables, which are quantities whose values can be manipulated in order to optimize the objective. Examples include the quantities of stock to be bought or sold, the amounts of various resources to be allocated to different production activities, the route to be followed by a vehicle through a traffic network, or the policies to be advocated by a candidate. The third element of an optimization problem is a set of constraints, which are restrictions on the values that the variables can take. For instance, a manufacturing process cannot require more resources than are available, nor can it employ less than zero resources. Within this broad framework,optimization problems can have different mathematical properties. Problems in which the variables are continuous quantities (as in the resource allocation example) require a different approach from problems in which the variables are discrete or combinatorial quantities (as in the selection of a vehicle route from among a predefined set of possibilities).

An important class of optimization is known as linear programming. Linear indicates that no variables are raised to higher powers, such as squares. For this class, the problems involve minimizing (or maximizing) a linear objective function whose variables are real numbers that are constrained to satisfy a system of linear equalities and inequalities. Another important class of optimization is known as nonlinear programming. In nonlinear programming the variables are real numbers, and the objective or some of the constraints are nonlinear functions (possibly involving squares, square roots, trigonometric functions, or products of the variables). Both linear and nonlinear programming are discussed in this article. Other important classes of optimization problems not covered in this article include stochastic programming, in which the objective function or the constraints depend on random variables, so that the optimum is found in some “expected,” or probabilistic, sense; network optimization, which involves optimization of some property of a flow through a network, such as the maximization of the amount of material that can be transported between two given locations in the network; and combinatorial optimization, in which the solution must be found among a finite but very large set of possible values, such as the many possible ways to assign 20 manufacturing plants to 20 locations."   From "optimization." Encyclopaedia Britannica. Encyclopaedia Britannica Online Academic Edition. Encyclopædia Britannica Inc., 2015. Web. 01 Jun. 2015.



Mathematics Library

Mathematics Library's picture
Mathematics Library
216 Altgeld Hall
1409 West Green Street
Urbana, IL 61801
(217) 333-0258

Mathematics Library LibGuides