alexa
Reach Us +44-1522-440391
Sequential Lifting of General Integer Variables for Integer Programs | OMICS International
ISSN: 2169-0316
Industrial Engineering & Management
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on Medical, Pharma, Engineering, Science, Technology and Business
All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Sequential Lifting of General Integer Variables for Integer Programs

Todd Easton*

Industrial and Manufacturing Systems Engineering, Kansas State University, 2037 Durland Hall, Manhattan, Kansas 66506, USA

*Corresponding Author:
Todd Easton
Industrial and Manufacturing Systems
Engineering, Kansas State University
2037 Durland Hall, Manhattan, Kansas
66506, USA
Tel: 785 532-3478
E-mail: [email protected]

Received February 18, 2015; Accepted May 12, 2015; Published May 14, 2015

Citation: Easton T (2015) Sequential Lifting of General Integer Variables for Integer Programs. Ind Eng Manage 4:158. doi:10.4172/2169-0316.1000158

Copyright: © 2015 Easton T. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Visit for more related articles at Industrial Engineering & Management

Abstract

Lifting integer variables is a widely used technique to create strong cutting planes. In 1975, Wolsey introduced a method to compute the exact sequential lifting coefficients of bounded integer variables by solving many integer programs. This paper presents a new technique to perform exact sequentially up and down lifting of general integer variables. The technique requires solving only a single branching tree. Some computational results demonstrate that this new sequential lifting technique performed approximately 11 times faster than Wolsey?s technique.

Keywords

Integer Programming; Lifting; Polyhedral theory; Facets

Introduction

Define a bounded integer program (IP) as max cTx subject to Ax ≤ b, 0 ≤ x ≤ u, Equation.IPs is NP-complete [1] and IPs is typically solved by branch and bound [2], which has an exponential run time. A common method that typically decreases the computational effort of branch and bound involves the addition of valid inequalities to the IP formulation. This paper presents a new technique to perform exact sequential lifting, which modifies a weak valid inequality into a stronger valid inequality.

First, define an IP’s feasible region to be Equation. (If x ≥ l, then through translation one may assume x ≥ 0.) Let the convex hull of solutions be denoted as PIP=conv (P). Define the restricted space of P when xi=k to be Equation and EquationFor convenience, this restricted space definition can be extended to any number of equalities or inequalities in the obvious manner. That is, let and F ⊂ N where N={1... n}, then the restricted space of P when xj=kj for all j Equation∈ F is PF =K={x ∈ P: xj=kj for all j ∈ F} with Equation as the respective convex hull.

¨An inequality Equation is said to be valid for PIP if and only if every x ∈ P satisfies this inequality. A valid inequality induces a face of dimension r in PIP if and only if the maximum number of affinely independent points in P that satisfy Equation is r+1. A face of dimension r is a facet if the dimension of PIP is equal to r+1. Nemhauser and Wolsey [3] provide more information about polyhedral theory with respect to integer programs.

Generating a weak valid inequality is trivial. Lifting, introduced by Gomory [4], is a technique used to modify a weak inequality into a stronger inequality. Numerous researchers have used lifting to create useful cutting planes for various problems. A small subset of these articles is [4-25]. Briefly, let E⊆ N={1, 2 . . .n} and F ⊆ N\E be any nonempty set. Now let Equation be a valid inequality of PIP where 0 ≤ kj ≤ uj for all j ∈ F. Lifting seeks to create a valid inequality of PIP, which takes the form Equation

There are various types of lifting, such as sequential, simultaneous, approximate and exact, up, middle and down lifting techniques. For distinction, and α denote the coefficients that are obtained through up and down lifting, respectively, and α represents a lifted coefficient that is either up or down lifted.

Of these lifting techniques, sequential up lifting is the most widely used technique [7, 8, 25-29]. Sequential lifting requires |F |=1 and up lifting assumes Equation is valid inequality for Equation where kj=0 for all j ∈ F. Therefore, sequential up lifting assumes that Equation is valid for Equation and seeks to create an inequality of the form Equation

Sequential down lifting assumes Equation is valid for Equation and obtain s and inequality of the form Equation where γ is typically equal to Equation . There is also a sequential lifting when Equation is valid for Equation where where k∗∈ {1... u1-1}, which is roughly a combination of both up and down lifting.

Lifting can be approximate or exact. Exact lifting finds the strongest Equationand/or Equationpossible. Thus, exact sequential up lifting finds the maximum value of α1∧ that still maintains the validity of the inequality. If such a value of α1∧ is obtained, then the dimension of the face induced by the sequentially lifted inequality increases by at least 1 in the unrestricted polyhedron.

Approximate lifting techniques obtain coefficients that maintain valid inequalities, but at times these coefficients could be strengthened. These approximate lifting techniques do not necessarily increase the dimension of the induced face, but rather trade the computational effort required for exact lifting for a theoretically weaker inequality. Some such approximate lifting results include sequential up lifting [7] and sequence independent lifting [6,30-32]. Other work has used a linear relaxation or just a portion of the original problem to approximate the lifting coefficients [29,33].

Simultaneous lifting requires |F | ≥ 2. Zemel [34] provided an exact technique to simultaneously up lift sets of binary integer variables. This technique solves an exponential number of integers programs and then finds extreme points of the polar created from the solutions to these integer programs. This method yields numerous inequalities, but is computationally intensive. Recently, [17] created a linear-time algorithm that exactly up lifts sets of binary variables into a cover inequality generated from a single binary knapsack constraint (a single nonnegative less than or equal to constraint, {x ∈ {0, 1}n:ax ≤ b, a ≥ 0}). Observe that the aforementioned sequence independent lifting references could also be viewed as an approximate method to up lift sets of integer variables.

Prior to this research Wolsey [29] provided the only known technique to exactly perform sequential lifting of general integer variables. His method requires the solution to u1 integer programs. This paper presents a new technique to perform exact sequential lifting of general integer variables. This new technique requires the solution to only a single branching tree for both up and down lifting and two branching trees if lifting over a valid inequality when x1==k* where k* ∈ {1, ..., u1-1}.

The remainder of the paper is organized as follows. Section 2 presents the new technique to sequentially up lift integer variables and compares this to Wolsey’s existing technique. Some computational results are contained in Section 3 that demonstrate that this new method is faster than Wolsey’s method. A conclusion and some directions for future research are discussed in Section 4.

Up Lifting Integer Variables

Wolsey [29] introduced a method to exactly lift general integer variables. This technique is derived directly from his theorem which states:

Theorem 2.1: Given a general integer programming instance, le Equation be a valid inequality when x1=k*where k* is integer and 0 ≤ k* ≤ u1. For each 0 ≤ k ≤ u1 and Equation define Equation

Equation

If, for a specific k, the problem is infeasible, then let Equation. Now let and

Equation

And

Equation

The sequentially lifted inequalities are Equation and such an inequality is valid for any α1 such that Equation.Furthermore, if Equation defines an r dimensional face of Equationthen Equation defines a face of dimension at least r+1 as long as α1 is finite and Equation

As mentioned in the introduction, of the many possible values of k* the most frequently used is k*=0, which is called up lifting. That is, a valid inequality is obtained when x1=0, and x1 is up lifted into this inequality. From Theorem 2.1 it is easy to see that Wolsey’s up lifting method requires the solution to u1 integer programs and the right hand side β does not change.

Now the attention turns toward the purpose of this paper, which produces a new technique to up lift general integer variables. The algorithm creates an inequality that increases the dimension of the face, but may not necessarily be a valid inequality (guess too high of a value for α1∧). A modifiable branching tree is then used to check to see if the inequality is valid. If the inequality is not valid or equivalently there exists a point violating the proposed inequality, then α1∧ is decreased according to this feasible point and the objective function is reset with this new α1∧. This process continues until all nodes are fathomed.

The input to the Sequential Lifting Algorithm (SLA) is composed of the constraints and bounds of a general integer program and an inequality Equation that is valid for Equation.SLA up lifts x1 by finding an α1∧ that is the maximum value such that Equation is valid for PIP.

The Sequential Lifting Algorithm (SLA)

Set α1∧:=M where Equation

Begin a modified branch and bound tree by letting the following LP be the unfathomed root node of the tree.

Equation

While there exist unfathomed nodes in the branch and bound tree, begin. Select an unfathomed node and solve the linear relaxation with the solution denoted by Equation

If Equation or the linear relaxation is infeasible, then fathom the node

If the solution to the node is an integer solution with Equation then begin

Equation

Change x1’s objective coefficient in every pendant node to α1∧

Create a single child constraint with no additional constraints.

end if

If Equationand x* is non-integer, then begin

Create two new children nodes by branching on any Equation that is non-integer.

One node has the parent’s LP with the added inequality Equation

The other child’s node has the parent’s LP and adds the inequality Equation

end if

end while

Output

If α1∧= M, then α1∧:=∞.

Report Equation is a valid inequality for PIP.

The following example demonstrates this algorithm and provides some fundamental insights into the differences between Wolsey’s method and SLA. The branching tree is explored according to a depth first left strategy.

Example 2.2: Consider an integer program with feasible region defined by

Equation

First observe that Equation that defines a face of dimension 0 from the point (0, 4). Figure 1 provides the branching tree to exactly up lift x1. SLA begins with the root node given by the LP

Equation

industrial-engineering-management-branching-tree-up

Figure 1: Branching tree to up lift x1 into x2 ≤ 4.

Solving this LP results in Equation and Equation. Two new child nodes are created. One adds on the constraint x1 ≤ 4 and the other x1 ≥ 5. The second node’s solution is Equation and Equation. Two new nodes are added, one with the constraint x2 ≤ 0 and the other with x2 ≥1. The LP solution to the left node, node 3, is Equation and Equation . This is an integer solution and 4m>β=4. So α1∧ is changed so that 4 × α1∧+0=4 and α1∧=1. The objective function of all remaining LPs is changed to x1+x2. Unlike branch and bound, this node is not fathomed; instead a single child node is added with the same LP as its parent, but with the updated objective value. The solution to node 4 is Equation.This node is fathomed, not because it is integer, but because Equation

Node 5’s solution is Equation and Equation.The α1∧ is updated so that 2 × α1∧+3=4 and Equation. All remaining nodes have the new objective of Equation and a single child node is added. The complete tree is shown in Figure 1. The final value of Equation sequentially up lifted inequality being Equation

Figure 1 provides a graphical view of lifting x1 into x2 ≤ 4 and is used to discuss the difference between this new technique and Wolsey’s technique. Wolsey’s method uses a single IP to find the maximum value of Equation for each x1=k for k=1, 2... u1. In this example the points that give the optimal solutions are (1, 3), (2, 3), (3, 1) and (4, 0). Wolsey’s method uses this point to obtain the candidate α1∧ where this point would meet the new inequality at equality. In this case, the candidate α1∧ values would have been 1, 1/ 2 , 1 and 1, respectively. The method then takes the minimum of these values as α1∧=1, which guarantees a valid inequality and increases the dimension by at least 1. In Figure 1, x1=1, x1=3 and x1=4 all have identical candidate α1∧ values, because they are on the same line. Essentially, Wolsey’s method checks every possible extreme point and accepts the best α1∧ value that maintains validity. Clearly some work is typically waisted.

In contrast, SLA begins by starting with an objective function that is nearly parallel to the x2 axis. As soon as an integer solution is discovered with value larger than 4, α1∧ is changed so intersect this point. In this case, it happens at node 4 with the point (4, 0). The inequality now tested for validity is x1+x2 ≤ 4, which intersects (4,0). If no integer solutions satisfy x1+x2 ≤ 4, then the inequality is valid. However, node 5 finds such a violating point (2,3) and the objective function changes to Equation.Observe that (2, 3) meets this inequality at equality. Eventually, the tree is fathomed and there are no integer solutions with a value larger than 4 to the objective function. Thus, the inequality is valid.

Essentially SLA maintains inequalities that guarantee to increase the dimension of the face (an additional point meets the inequality at equality), but may not necessarily be valid. Once the algorithm terminates, the inequality is clearly valid since there does not exist a feasible point with a value larger than β. Since α1∧ is calculated from a feasible point, the dimension of the lifted inequality’s face also increases in the unrestricted polyhedron. SLA seeks to obtain the lifting coefficient by coming through the inside of the polyhedron; whereas, Wolsey’s method seeks to obtain the lifting coefficient by identifying all extreme points.

One may attempt to incorrectly argue that SLA is Wolsey’s method. The erroneous argument states that the root node should have u children with each branch having xi set to a different integer between 0 and u. Such an IP would only generate a single objective function. This single IP could not accurately calculate the lifting coefficient. Thus, SLA is not merely an extension of Wolsey’s method, but a new method to perform sequential lifting.

The main theoretical result of the paper, which states that SLA terminates with a valid inequality, can now be presented. Furthermore, this inequality results in the same coefficient as Wolsey’s method, and, under a feasibility assumption, the dimension of the inequality increases over the non-restricted polyhedron.

Theorem 2.3: Let Equation be a valid inequality of Equation.Given a bounded integer program, the Sequential Lifting Algorithm terminates and reports a valid inequality Equation , of PIP . Furthermore, the coefficient α1∧ returned from SLA is the equal to the α1∧ generated from Wolsey’s method. If Equation defines a face of dimension r in Equation,then Equation defines a face of dimension at least r+1 in PIP as long as α1∧ is finite.

Proof: Assume a node in the branching tree has an integer solution with z>β. Then Equation Clearly, this new value of α1∧ is strictly less than the previous value of α1∧. Thus, the values of α1∧ monotonically decrease as the branching tree progresses.

Due to the monotonically decreasing nature of the α1∧, any integer solution contained in the feasible solution space of a node that is fathomed because z ≤ β satisfies the returned inequality Equation.There are no integer solutions in the solution space of an infeasible node. Since SLA only fathoms nodes under these two conditions and SLA terminates when every node is fathomed, there does not exist an x ∈ P such that Equation. Consequently, SLA generates a valid inequality upon termination.

To show termination, observe that the IP is bounded. Thus, there can be at most Equation integer solutions. The branching step can be implemented at most Equation times. In such a scenario, the solution to every child would either be integer or infeasible. Any solution to an integer with value larger than β, creates an additional child. The solution x values of this child node must be identical to its parent’s solution and thus the objective value is equal to β. This new node is then fathomed. Thus, each node is fathomed in a finite number of steps and SLA terminates.

Assume SLA terminates with α1∧=∞. In such a case, no integer solutions were encountered in the branching tree. Thus, the solution to Maximize Equation subject to Ax ≤ b, x1 ≥ 1, 0 ≤ xi ≤ ui and Equationis infeasible and both Wolsey’s method and SLA sets α1∧=∞.

Assume SLA terminates with α1∧ being finite. Let Equation be the integer solution that determined the reported value of α1∧. Since Equation an integer between 1 and u1, Wolsey’s method solves an integer program of the form Maximize Equation subject to Ax ≤ b, x1 ≥ 1, 0 ≤ xi ≤ ui and Equation .The solution to this integer program must be identical to Equation or there is a contradiction to optimality of either an LP or IP. Thus, Wolsey’s coefficient is at most Equation

For contradiction, assume Wolsey’s coefficient is less than α1∧. Then there exists Equation such that Equation.Let Equation be the solution to Wolsey’s Equation. Clearly Equation, since Equation is integer, this contradicts the prior argument on the validity of SLA. Consequently, SLA and Wolsey’s method both produce identical coefficients.

Finally, assume Equation defines a face of dimension r in Equation and so there exists r+1 affinely independent points in Px1=0 that satisfy Equation.Assume SLA terminates with afinite α1∧. Then there exists some Equationthat determined the reported value of α1∧. Furthermore, Equation and Equation. Clearly, Equation is affinity independent from these other r+1 points and thus the face of the lifted inequality is at least r+1 and the result follows.

A few comments can now be made that describe how to improve SLA. Theoretically, SLA requires Equation where Equation Thus any integer solution is larger than β and α1∧ changes. From a computational standpoint, if a feasible point with x1 ≥ 1 is known, then the starting value of α1∧ can be changed so that this feasible point satisfies the up lifted in equality at equality. Multiple knapsack problems (all nonnegative coefficients and less than or equal to constraints) provide an excellent example. In such problems, the point (u1, 0, 0, ..., 0) is always feasible and the starting value of α0 can be set equal to Equation . In Example 2.2, the point (4, 0) is1trivially valid and α1∧ could have been set to 1 to start SLA. This may reduce computational effort.

An additional advantage to SLA is that it may enable exact up lifting over unbounded integer programs. Wolsey’s method does not enable this type of lifting as solving an infinite number of IPs is not possible. However, SLA may not terminate for an unbounded integer program as a critical assumption for the finite termination proof is no longer valid. For instance, implementing SLA to lift x1 into x2 ≤ 0 for Equation would never terminate. Consequently, if SLA terminates for an unbounded integer program, then SLA determines the correct up lifting coefficient.

Sequential Down Lifting and Lifting when x1=k*

With a fundamental understanding of up lifting, it is now straightforward to modify SLA into algorithms that can down lift and lift over a valid inequality when x1=k*. For brevity two new algorithms and theorems for these other types of lifting are not presented. Rather changes are described that enable the reader to trivially extend SLA to these other two sequential lifting types through variable substitution. An example of each algorithm is also provided to aid with comprehension.

Down lifting can be viewed as substituting Equation for x1 where Equationand then up lifting Equation.Thus, down lifting creates a valid inequality of the form Equation.Now as in the up lifting case, the left hand side of this inequality becomes the objective function, Maximize Equation,and the constraints are the constraints of the integer program with the additional constraint of x1 ≤ u1-1.

When an integer solution is found that is larger than β, the linear relaxation point, Equation, is substituted into the equation Equation to solve for the new estimate of α1v. Everything else is identical and trivial to determine with knowledge of this substitution. The following example provides a demonstration of down lifting using SLA.

Example 3.1: Returning to Example 2.2, if x1=4, then x2 ≤ 0 is a valid inequality that defines a face of dimension 0 due to the point (4, 0). The down lifted branching tree is shown in Figure 2 using a depth first left node evaluation strategy. The first integer solution is found at node 2 with a Z=4M+4>0=β and x=(0, 4). Solving for α1v in α1v (4- 0)+4=0 results in α1v=-1.

industrial-engineering-management-graphically-lifting

Figure 2: Graphically Lifting x1 in Example 2.2.

All objective functions are now changed to -1(4-x1)+x2.

Node 3 also is integer with Z=1>β and x=(2, 3). Solving for α1v in α1v (4-2)+3=0 results in Equation.Nodes 4 and 6 require branching, but eventually every node is either infeasible or Equation.Thus, SLA terminates with Equation.The reported valid inequality is Equation or equivalently Equation.Observe that this inequality has dimension 1 because the point (2, 3) meets this inequality at equality and is affinely independent from (4, 0).

equality and is affinely independent from (4, 0). The attention now turns toward sequentially lifting over a valid inequality when x1=k* where 0<k*<u1, which is a combination of both down and up lifting. The substitution for down lifting is Equation. The down lifting portion adds on the constraint x1 ≤ k*-1 to the root note. For an integer solution larger than β, a new value of α1v is obtained by solving Equation.

In contrast, the up lifting adds on the constraint x1 ≥ k*+1 to the root node and results in a lifted inequality taking the form Equation. When an integer solution is encountered with a Equation , a new α1∧ is obtained by solving Equation

In contrast to up and down lifting, middle lifting may not produce a valid inequality. In fact, a middle lifted inequality takes the form Equation .This inequality is only valid when Equation.

Notice that if Equation,and then one cannot sequentially lift x1 using middle lifting as any such inequality would be invalid. The following example demonstrates these concepts.

Example 3.2: Reexamining example 2.2 and if x1=k*=2, then x2 ≤ 3 is valid inequality that defines a face of dimension 0 from the point (2, 3). To find the proposed up lifted coefficient, set the objective function toEquation and add the constraint α1^(x1-2)+x2and add the constraint x1 ≥ k*+1=3. The optimal integer solution occurs at (4, 0), which sets Equation . Any remaining nodes are easily fathomed. For the down lifting portion, set the objective function to Equation and add the constraint x1 ≤ k*-1=1. The optimal integer solution is (0, 4), which sets Equation. Since Equation any inequality of the form α1x1+x2 ≤ 3+2α1 is valid as long as Equation.

To help clarify the idea that middle lifting may not result in a valid inequality, observe that x2 ≤ 1 is valid if x1= k*=3. This inequality defines a face of dimension 0 from the point (3, 1). To find the proposed up lifted coefficient, set the objective function to α1∧ (x1-3)+x2 and add the constraint x1 ≥ k*+1=4. The optimal integer solution is (0,4), which sets α1v=1. Any remaining nodes are easily fathomed. For the down lifting portion, the optimal integer solution is (2, 3), which sets . Equation. Since Equation no middle lifted inequality is valid. This is easily verifiable in Figure 3 as the point (3,1) is not an extreme point of PIP.

industrial-engineering-management-branching-tree-down

Figure 3: Branching tree to down lift x1 into x2 ≤ 0.

Computational Results

This section demonstrates that SLA is substantially faster than Wolsey’s method. All computational results were performed on an Intel Core i7-2600 chip at a 3.4 GHz processor with 8 Gb of RAM and the integer programs were solved using CPLEX 10.0 [35] at its default settings.

The problems chosen for this study were generated from random multiple knapsack poly tope Equation The aij were integers selected uniformly between 25 and 1, 000. (Note: Whenaij <25, then the ui’s became extremely large and Wolsey’s could not finish in a reasonable time. So each aij ≥ 25.) The slackness, s, of the constraint determines the right hand side, Equation.Various values of n were chosen as shown in Table 1.

The computational study starts with the valid inequality x1 ≤ u1 and sequentially up lifts every other variable until the inequality becomes facet-defining. Fifty random knapsack instances are created for each problem size. Table 1 reports the total time in seconds required to lift all of the variables. Thus, when n=10, the total time columns represent the time required to sequentially up lift 9 variables for each of the 50 problems or 450 variables with either Wolsey’s Algorithm or SLA. In addition, the total number of integer programs that Wolsey’s method solved is also reported.

Table 1 shows the computational superiority of SLA. On average SLA lifted variables eleven times faster than Wolsey’s method. SLA was at least as fast in every instance. As expected, the larger the average upper bound the greater improvement of SLA. For instance, the largest bounds occurred with the slack coefficient of 2 and when there are fifty variables. The average of these 150 instances shows that SLA is about 25 times faster than Wolsey’s method. Some additional computational results [36] demonstrate SLA’s superiority over Wolsey’s method.

Conclusion and Future Research

Since Wolsey’s paper in 1975 and prior to this work, there has only been one method to perform exact sequential lifting. This existing method requires solving ui+1 integer programs where ui is the upper bound for variable i. This paper presents a new technique, SLA, to perform exact sequential lifting of bounded integer programs. SLA requires solving a single branching tree for both up and down lifting, and only two branching trees for middle lifting. SLA, under reasonable assumptions, becomes the first method for sequential lifting of unbounded integer programs.

A computational study compared the amount of computational effort required to sequentially up lift many variables using both Wolsey’s method and SLA. SLA performed 11 times faster than Wolsey’s method. Thus, SLA is both theoretically and computationally superior to the existing method. It is recommended that researchers performing sequential lifting implement SLA instead of Wolsey’s method.

The creation of SLA also raises several important research questions. Can SLA’s new method and theory be extended to perform exact simultaneous lifting? Can the concepts behind SLA be extended into a new method to obtain approximate lifting coefficients (terminating SLA prior to each node being fathomed)? Can polynomial time methods be developed to create sequentially lifted inequalities?

Acknowledgment

The authors would like to thank Ricardo Fukasawa for some critical insight into down lifting.

References

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Relevant Topics

Article Usage

  • Total views: 12548
  • [From(publication date):
    May-2015 - Jul 16, 2019]
  • Breakdown by view type
  • HTML page views : 8732
  • PDF downloads : 3816
Top