1. Mathematical Programming Problems



3 - Valid Inequalities in Integer Programming

Recently, several computational studies have focused on applying polyhedral theory for solving pure and mixed integer problems. These studies have been motivated by the success obtained by Crowder, Johnson and Padberg (1983) in using polyhedral theory to derive cutting planes for solving real large-scale pure zero-one problems, and by Grötschel (1980) for the travelling salesman problem.

The use of cutting planes for solving integer problems began in 1954 with the work of Dantzig, Fulkerson and Johnson (1954) for solving the travelling salesman problem. By 1958, Gomory (1958) developed a finitely convergent algorithm for solving general integer problems. The main problem with Gomory's algorithm is that although finite, it has poor convergence properties. Classical cutting planes provide "weak" cuts that frequently do not even define supporting hyperplanes for the underlying polytopes (Padberg and Rinaldi, 1991). Empirical evidence has shown that for a cutting plane algorithm to perform efficiently, it is necessary to use cuts that are strong in the sense that they define facets or faces of high dimension of the convex hull of solutions.

The key for the success of the cutting plane algorithms used by Crowder et al. and Grötschel is that the cuts used in their algorithms define facets or faces of high dimensions of the convex hull of the feasible points. Computational studies by Crowder et al. and others (e.g.: Hoffman and Padberg, 1993; Johnson et al., 1985; Pochet and Wolsey, 1991; Van Roy and Wolsey, 1987) have shown that the polyhedral characterization of a substructure of a complex problem is useful to tighten the problem formulation and yields efficient cutting plane algorithms, although the facets of these substructures are not necessarily facets for the larger problem. Another feature of the cutting planes derived from the polyhedral structure of the underlying problem is that they can be used efficiently in a hybrid algorithm that combines cutting plane and branch and bound, since the cuts generated at individual nodes of the tree are valid for the entire tree.

To have an efficient cutting plane algorithm, theory and computation must be combined. First the polyhedral structure of the problem has to be investigated. This part consists of deriving valid inequalities and proving that they define high dimensional faces for the underlying polyhedron. The computation consists, in part, of designing algorithms and/or fast heuristics to solve the separation problem.

The aim of this chapter is to review techniques for developing general purpose cutting plane algorithms. In this sense some general procedures for generation of valid inequalities are reviewed, as well as valid inequalities for two well known problems: the knapsack problem and the fixed-charge network problem. These two problems are easily identified as subproblems of more complex pure and mixed integer problems.

The use of faces and facets for subproblems present in more complex problems has become a common feature in general purpose systems for solving mixed zero-one problems. Examples are: MINTO (Nemhauser et al., 1994), MPSARX (Van Roy and Wolsey, 1987), CPLEX (Cplex Optimization, 1994), and OSL (IBM corporation, 1991).

This chapter is organized as follows. Section 3.1 contains concepts from linear algebra and polyhedral theory that are necessary for the following sections. Section 3.2 presents general procedures for generating valid inequalities. Sections 3.3 and 3.4 study valid inequalities for the knapsack polytope and for the fixed-charge network polytope, respectively.

3.1 - Polyhedral theory

In this section we summarise the concepts and results from linear algebra and polyhedral theory that are necessary for study of polyhedral cuts. A more detailed discussion on this subject can be found in Grötschel and Padberg (1985), Nemhauser and Wolsey (1988) and Pulleyblank (1989).

Definition 3.1 - Convex and Affine Combination - Given vectors [pic] and scalars [pic], if there exists an [pic] such that [pic]and [pic], [pic],[pic], then [pic] is called a convex combination of [pic]. The vector [pic] is called an affine combination of [pic] if [pic]and [pic].

Definition 3.2 - Convex and Affine Hull - The set of all convex combinations of finitely many vectors in [pic], where [pic] and [pic], is called the convex hull of [pic] and is denoted by [pic]. Similarly an affine hull of [pic] is the set of all affine combinations of finitely many vectors in [pic], where [pic] and [pic], and is denoted by [pic].

Definition 3.3 - Linear Independence - A set of points [pic] is linearly independent if the unique solution for [pic]is [pic],[pic].

Definition 3.4 - Affine Independence - A set of points [pic] is affine independent if the unique solution for [pic], [pic] is [pic],[pic].

Note that linear independence implies affine independence, but the converse is not true. Affine independence is more important than linear independence in polyhedral combinatorics because it is invariant under translations of the origin. For example in [pic] the vectors (0,1) and (1,2) are both linear and affine independent, but the vectors (1,1) and (2,2) are only affine independent. However the second set of vectors are obtained by adding (1,0) to the first set of vectors. The next proposition characterizes an affine and a linear subspace.

Proposition 3.1 - A set [pic] is an affine subspace if and only if there is an (m,n)-matrix [pic] and a vector [pic] such that: [pic], [pic] is a linear subspace if and only if there is an (m,n)-matrix [pic] such that [pic].

Definition 3.5 - Affine and Linear Rank - The affine rank of a set [pic] is the cardinality of the largest affine independent subset of [pic]. Similarly the linear rank of a set [pic] is the cardinality of the largest linear independent subset of [pic].

The affine and linear rank are related as follows.

Proposition 3.2 - For every subset [pic]:

i) If the null vector is in the [pic], then the affine rank of [pic] is equal to the linear rank+1.

ii) If the null vector is not in the [pic], then the affine rank of [pic] is equal to the linear rank.

Definition 3.6 - The maximum number of linearly independent rows or equivalently, independent columns of a (m,n) matrix [pic] is the rank of [pic] and is denoted by [pic].

Proposition 3.3 - If [pic], the maximum number of affine independent solutions of [pic] is [pic].

The following results are important for the characterization of the set of feasible solutions of a mathematical programming problem.

Definition 3.7 - Hyperplane - Sets of the form [pic]where [pic] and [pic] are called hyperplanes[1].

Proposition 3.4 - Hyperplanes are affine subspaces. Every affine subspace different from Rn is an intersection of hyperplanes.

Definition 3.8 - A set [pic] is called full-dimensional if [pic], i.e. there is no hyperplane containing [pic]. If[pic], then [pic] is called a minimal equation system for [pic] if [pic] and [pic] has full rank.

Definition 3.9 - Polyhedron - An intersection of finitely many half-spaces is called a polyhedron. Every polyhedron can be represented in the form [pic]. [pic] is called a rational polyhedron if there exist an (m',n) matrix [pic] and a vector [pic] with rational coefficients such that [pic]. A polytope is a bounded polyhedron, i.e. [pic] such that [pic].

The next results will be helpful to obtain the minimal representation of a polyhedron [pic].

Definition 3.10 - Valid Inequality - An inequality [pic] (or [pic]) is called valid with respect to [pic] if [pic], i.e. if [pic] is contained in the half-space defined by[pic], or equivalently [pic].

Proposition 3.5 - If [pic] is valid for [pic], it is valid for [pic].

Definition 3.11 - Proper Valid Inequality - A valid inequality is called proper for [pic] if it is satisfied as a strict inequality by at least one point [pic].

Definition 3.12 - Supporting Inequality - A valid inequality is called supporting for the set [pic] if [pic].

Definition 3.13 - Face - A subset F of a polyhedron [pic] is called a face of [pic] if there exist a supporting inequality [pic] with respect to [pic] such that [pic]. The inequality [pic] is said to define [pic]. It is called proper if [pic].

Definition 3.14 - Two valid inequalities [pic]and [pic] are equivalent if [pic] for some [pic]. If there exists [pic] such that [pic] and [pic], then [pic] dominates or is stronger than [pic].

Definition 3.15 - Maximal - A maximal valid inequality is one that is not dominated by any other valid inequality for [pic].

Definition 3.16 - Facet - A facet of a polyhedron [pic] is a proper nonempty face that is maximal with respect to set inclusion.

Usually in combinatorial optimization problems the polyhedra are given as the convex hulls of finite sets of points. To apply mathematical programming techniques to solve these problems it is necessary to describe the convex hulls as systems of linear inequalities. A major problem is to define systems with as few inequalities as possible and therefore facet-defining inequalities have a very important role. The following theorem can be used to establish whether a valid inequality defines a facet.

Theorem 3.1 - Let [pic] be a polyhedron and assume that [pic] is an (m,n)-matrix, [pic] such that [pic]. Let [pic] be a nonempty proper face of [pic]. Then the following statements are equivalent:

a) [pic] is a facet of [pic];

b) [pic]

c) If [pic] for all [pic], then there exists a scalar [pic] and a vector [pic] such that[pic] and [pic].

Theorem 3.2 below summarizes important results concerning the characterization of the minimal set of inequalities necessary to represent a polyhedron P. A system of equations and inequalities,[pic] and [pic] is said to be complete with respect to a polyhedron [pic], if [pic].

Theorem 3.2 - Let [pic] be a polyhedron and ,[pic] and [pic] be a complete nonredundant system for [pic], where [pic] is (m,n)-matrix and [pic] is a (k,n)-matrix. Then the following holds:

a) [pic]

b) [pic] and [pic] have dimension n-m

c) every inequality [pic] of the system [pic] defines a facet [pic] of [pic], where [pic], [pic].

d) if [pic] [pic]; [pic], [pic] is any other complete and nonredundant system for [pic], then

d1) [pic]

d2) [pic] for some [pic], [pic]

d3) [pic] for some [pic], [pic] and[pic], [pic].

Theorem 3.2 implies that a full-dimensional polyhedron [pic] is defined by a unique (up to multiplication by positive scalars) nonredundant and complete inequality system. Moreover, for every facet [pic] of [pic] there is a unique (up to multiplication by a positive scalar) inequality defining [pic]. If a polytope [pic] is given as the convex hull of finitely many points, then it follows that to get a complete inequality description of [pic], for every facet of [pic], it is necessary to know (at least) one inequality defining it. Moreover, if one wants to find a complete nonredundant system ,[pic], [pic] for [pic], it is necessary to prove that [pic] is a minimal equation system for [pic], [pic] contains no implicit equations, every inequality of[pic] defines a facet of [pic] , and [pic] contains no equivalent inequalities.

To conclude this section some results about the relationship between integer and linear problems are presented.

Theorem 3.3 - If [pic], where [pic] is an integer (m,n+1) matrix, and [pic] then [pic] is a rational polyhedron.

Theorem 3.3 suggests that we can solve the integer program:

[pic], where [pic] (IP)

by solving the linear program:

[pic]. (CIP)

The above results extend to mixed-integer sets with rational data.

Proposition 3.6 - To establish the dimension of a face to [pic] it is sufficient to consider only points in [pic].

Theorem 3.4 - Given [pic], [pic] it follows that:

a) The objective value of (IP) is not bounded from below if and only if the objective value of (CIP) is not bounded from below.

b) If (CIP) has a bounded optimal solution, then it has an optimal solution (namely an extreme point of [pic]) that is an optimal solution to (IP).

c) if [pic] is an optimum solution to (IP) then [pic] is an optimal solution to (CIP).

This theorem says that it is possible to solve the integer program (IP) by solving the linear program (CIP). Since, generally, a set of linear inequalities that define [pic] is not known, the problem (IP) is formulated using some polyhedron [pic] such that [pic]. Therefore reducing (IP) to an (LP) amounts to deducing a linear inequality representation of [pic], or at least the relevant inequalities with respect to an objective function [pic], from the linear inequality representation of [pic] and the integrality requirements.

3.2. General characterization of valid inequalities

As seen in the previous section the major concern about applying polyhedral theory to solve mixed integer programming problems is to find a suitable system of inequalities that defines the convex hull of the feasible region of these problems. This section will focus on general procedures to obtain systems of inequalities describing [pic], where [pic] is the set of feasible points of the following integer programming problem:

[pic]. (IP)

3.2.1 - Disjunctive Characterisation

The disjunctive characterisation of valid inequalities is based on describing a discrete feasible space as a finite disjunction of system of inequalities. The disjunctive model of discrete problems is then given by:

[pic] (3.1)

where [pic] is a finite index set and [pic] are finitely many linear programming spaces to which[pic] may belong.

Sets of valid inequalities for any system of inequalities written in the disjunctive format (3.1) can be generated using the Disjunctive Procedure below.

Disjunctive Procedure

i) Given positive multipliers [pic] reduce the system of inequalities defining [pic] to a single inequality [pic]

ii) The inequality[pic] is valid for (3.1). Where [pic] denotes the [pic] component of [pic].

A good choice of multipliers ( uh : h∈H) can produce quite strong valid inequalities (Parker and Rardin, 1988). Theorem 3.5 (Parker and Rardin, 1988) below shows that if each of the systems [pic]is feasible, or can be made feasible by changing the right hand side, or has the same [pic] matrix as an element of the disjunction that is feasible, then all valid inequalities for [pic] can be generated using the disjunctive procedure.

Theorem 3.5 - Sufficiency of the Disjunctive Procedure - Let [pic] be the feasible set of a finite disjunctive form (3.1). If for each [pic]:

i) [pic]is nonempty; or

ii) there exist [pic] such that [pic]is nonempty and bounded; or

iii) There exist [pic] with [pic] and [pic]is nonempty

every maximal valid inequality for [pic] can be computed via the disjunctive principle by an appropriate choice of nonnegative [pic].

An application of the Disjunctive Procedure given in Nemhauser and Wolsey (1988) is to derive a valid inequality to the standard disjunction that appears in enumeration algorithms for IP. Suppose

[pic].

The feasible set [pic] is contained in[pic] where:

[pic] and [pic]

If [pic] is not integral, [pic] is the standard disjunction [pic] or [pic] used in enumeration algorithms. Rewriting [pic] and [pic] as :

[pic] and [pic]

and using ii) of the Disjunctive Procedure, with [pic], the following valid inequality may derived:

[pic]

where [pic], for [pic].

Balas (1979a) used the disjunctive principle to show that for some classes of problems it is possible to obtain the convex hull of (IP) by considering the disjunction one variable at a time. The problems of these classes are those that can be formulated in a conjunctive normal form, i.e. a conjunction where the terms do not contain further conjunctions:

[pic]

and are facial, i.e. each inequality [pic] defines a face of [pic] for all [pic].

This fact is important because calculating facets of the convex hull of points satisfying one disjunction is much easier than calculating facets for the convex hull of the full disjunctive set. The class of disjunctive programs that have the facial property includes zero-one programming problems (pure or mixed) but not the general integer problem.

Theorem 3.6 (Parker and Rardin, 1988; see also Nemhauser and Wolsey, 1988) below formalises the method for constructing the convex hull of solutions to a bounded, facial, disjunctive program. Imposing the disjunction one by one at each step a ‘partial’ convex hull, i.e. the convex hull of the set defined by the inequalities generated earlier plus one of the disjunctions, is calculated.

Theorem 3.6 - Let [pic]be a nonempty bounded polyhedral set and

[pic]

with all inequalities [pic] defining faces if [pic] is facial. Also for any sequencing of [pic] of the elements of I, define:

[pic]

with [pic]. Then for [pic]

[pic]

where [pic] denotes the convex hull of set [pic].

Balas et al. (1993a, 1993b) proposes a lift and project methodology to generate valid inequalities that is equivalent to the sequential convexification procedure for facial disjunctive problems defined by theorem 3.6. The methodology yields a class of finitely convergent cutting planes for mixed zero-one problems. It is based on sequentially lifting the LP relaxation into a higher dimensional space and then projecting back the resulting polyhedra into the original space.

3.2.2 - Superadditive Characterisation

The Disjunctive Procedure described above generates the coefficients [pic] of a valid inequality by taking nonnegative linear combinations of the corresponding constraint columns, [pic], minimising or maximising over the elements of the disjunction. Thinking of this process as one of computing [pic] as a function [pic], the question of whether there are other characterisations of the function [pic] that produce valid inequalities arises (Parker and Radin, 1988).

Definition 3.17 - Superadditive Function - A function [pic] is called Superadditive over [pic] if:

[pic]

Definition 3.18 - Nondecreasing Function - A function [pic] is called nondecreasing over [pic] if [pic] and [pic] imply [pic].

A function with these two properties yields valid inequalities. This result is formalised in proposition 3.7 (Nemhauser and Wolsey, 1988) below.

Proposition 3.7 - If[pic] is Superadditive and nondecreasing with [pic], then

[pic]

is a valid inequality for [pic].

The generality of proposition 3.7 introduces several potential methods for generating valid inequalities. Three examples suggested in Nemhauser and Wolsey (1988) are presented below.

i) [pic] (to guarantee that the function is nondecreasing);

ii) [pic]. We have to show that [pic]. But

[pic]

iii) [pic].

The next theorem (Nemhauser and Wolsey, 1988) shows that [pic] can be described using only superadditive valid inequalities.

Theorem 3.7 - Every valid inequality for a nonempty set [pic] is equivalent to or dominated by a superadditive valid inequality.

3.2.3 - Chvátal-Gomory Characterisation

Consider the bounded pure integer program :

[pic].

In general, coefficients A, b, c may take any real values, but assume that the upper bounds are integers. Let [pic], with [pic]. Then a valid inequality for [pic] can be algebraically justified using the following three-step procedure (Nemhauser and Wolsey, 1988).

Chvátal-Gomory Procedure (C-G procedure)

i)[pic] for all [pic], [pic].

ii)[pic], since [pic]implies [pic].

iii) [pic], for all [pic], since [pic] implies [pic].

This procedure takes both the names of Chvátal and Gomory because Chvátal developed it explicitly in 1973 and Gomory implicitly in 1958-63. Chvátal proved that finitely many such simple steps can derive every needed inequality for [pic]. Therefore, the minimum number of steps needed is called the ‘Chvátal rank’ of the inequality (Nemhauser and Wolsey, 1988; Parker and Rardin, 1988).

Like the disjunctive and the supperadditive analogues, Theorem 3.8 (Parker and Rardin, 1988) shows that all the valid inequalities necessary to obtain [pic] can be generated by the C-G procedure.

Theorem 3.8 - Consider the problem [pic]and the feasible region given by [pic]. Then any integer supporting inequality for [pic] can be derived by a finite sequence of applications of the C-G procedure, each new inequality being added to the linear system, [pic], from which the next is derived.

Example: Given[pic] where [pic] show that [pic] is a facet for [pic] using the C-G procedure.

i) We have to find a vector [pic] such that [pic]. One solution for this system of inequalities is :

[pic]( 2/45, 250/990, 0)

The valid inequality is : [pic].

ii) [pic]

iii) [pic]

Dietritch and Escudero (1994) show that the clique inequalities (chapter 2) and the minimal cover inequalities (section 3.3) as well as the inequalities resulting from the application of the myopic coefficient reduction (chapter 2) can be obtained by applying the CG-procedure.

Vanderbeck and Wolsey (1992) solve a simple integer programming problem involving production of a single item and start-up costs (The Lasdon-Terjung production model) using the inequalities derived by the C-G procedure as cutting planes. Solving the model using the standard Branch and Bound method leads to a prohibitively large search trees. Using the C-G inequalities as cutting planes in the root node substantially reduced the size of the search tree, and for some instances eliminated the need to branch.

3.2.4 - Boolean, Geometrical and Combinatorial Characterisation

The three procedures presented above provide finite algorithms to solve integer problems. Although finite, in practice these algorithms are likely to converge slowly, and thus have limited practical application. However, they suggest simple ways to derive sets of valid inequalities or to show that a given one is valid. They also give a more general way to look at the classical Cutting Plane method introduced by Gomory in the sixties. Moreover, since the valid inequalities are satisfied by all points in [pic], they can be used in a hybrid algorithm that combines Cutting Plane and Branch and Bound, where the cuts are generated at each node of the tree. Still, these characterisations of valid inequalities do not exhaust all the possibilities of obtaining valid inequalities for integer problems.

An important approach that has been widely applied is to explore the boolean, geometrical or combinatorial structure of the problem to generate facets or faces of higher dimensions of the underlying polytope. Examples of problems which have their polyhedral structure described by such methods are : assignment problems (e.g. Aboudi and Nemhauser, 1991; Aboudi et al., 1991; Padberg and Alevras, 1993); design of communications networks (e.g. Grötschel et al., 1992); fixed-charge network problems (e.g. Van Roy and Wolsey, 1985;1986); knapsack problems (e.g. Balas, 1975; Wolsey, 1975); lot-sizing problems (e.g. Pochet and Wolsey, 1991; Clark and Armentano, 1995); plant location problems ( Leung and Magnanti, 1987); production scheduling (Magnanti and Vachini, 1990). However, this approach is problem dependent and there is no general process for generating valid inequalities based on it. Yet, if these problems are identified as subproblems within more generic ones, then the known valid inequalities may be applied. Valid inequalities derived from GUB constraints have been described by several authors including Wilson (1990) and Wolsey (1990). The knapsack and the fixed-charge network problems are two well structured problems whose polyhedral description can be useful for solving pure and mixed zero-one problems. Sections 3.3 and 3.4 examine valid inequalities for the knapsack and the fixed-charge network polytope respectively. The conditions under which these valid inequalities define facets and procedures for identifying violated inequalities are also discussed.

3.2.5 - Fenchel cuts

Boyd (1993, 1994a, 1994b) derives valid inequalities using a different approach. He addresses the problem of generating cutting planes by considering algorithms that focus directly on the separation problem without assuming any a priori knowledge about the facial structure of a polyhedron. The methodology is applicable to mixed integer as well as pure integer problems.

Consider the integer problem (IP). Let [pic] be some polyhedron containing the feasible integer points for (IP) and [pic]be the optimal solution to the linear relaxation of problem (IP). The methodology presented attempts to identify a valid inequality that is not satisfied by [pic] but contains [pic]. Given [pic], define [pic] and [pic]. According to theorem 3.9 (Boyd, 1994b) below, there is a valid inequality separating [pic] from [pic] if and only if [pic].

Theorem 3.9 - There exists a value [pic] for which [pic] if and only if there exists a hyperplane [pic]separating [pic] from[pic].

Due to similarities with Fenchel duality the inequalities [pic] are referred to as Fenchel cuts. Observing that for any scalar [pic], [pic] it follows that if [pic]achieves a positive value it achieves a positive value on any full dimensional set that has the origin on its strict interior. This implies that there is considerable freedom when choosing the domain for optimizing function [pic]. However the depth of the Fenchel cuts depends on the choice of a domain [pic]. Boyd (1993) observes that if the set [pic] represents the unit sphere in an arbitrary norm, the Fenchel cut associated with the optimal solution of the problem:

[pic] (Q)

represents the deepest cutting plane separating [pic] and [pic] as measured by the dual norm.

The solution of problem (Q) can be simplified considering the properties of the function [pic]stated in the following two theorems (Boyd, 1994b).

Theorem 3.10 - The function [pic] is piecewise linear and concave. Specifically, [pic] can be expressed as

[pic]

where [pic] is the set of extreme points of [pic].

Theorem 3.11 - If [pic]satisfies [pic]then [pic] is a subgradient of [pic]at[pic].

Although subgradient techniques or generalized programming are the common methods employed to solve problems such as Q, the application of these methods to generate Fenchel cuts in practice proved to be very inefficient as pointed out by Boyd (1993). Defining [pic]as a linear constraint set and finding a suitable relaxation of the set of feasible points for (IP) allowed the use of the simplex method as an alternative. In fact, it proved to be essential in efficiently generating Fenchel cuts (Boyd, 1993). The convergence of a cutting plane algorithm using Fenchel cuts is discussed in Boyd (1995).

Boyd (1993, 1994b) shows the computational value of the methodology by applying it to a collection of real-world pure zero-one problems taken from the MIPLIB library (see chapter 5). From the seven problems examined, four were solved to optimality without the aid of branch and bound, and six had the integer gap closed by over 98% (Boyd, 1994b).

-----------------------

 [1]Given a set [pic] and a subset [pic], denote by[pic] the subset obtained by deleting from [pic] the elements in [pic].

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download