Reach Us
+44-1522-440391

**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

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.

Integer Programming; Lifting; Polyhedral theory; Facets

Define a bounded integer program (IP) as max c^{T}x subject to Ax ≤ b, 0 ≤ x ≤ u, .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 . (If x ≥ l, then through translation one may assume x ≥ 0.) Let the convex hull of solutions be denoted as P^{IP}=conv (P). Define the restricted space of P when x_{i}=k to be and For 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 x_{j}=k_{j} for all j ∈ F is P_{F =K=}{x ∈ P: x_{j}=k_{j} for all j ∈ F} with as the respective convex hull.

¨An inequality is said to be valid for P^{IP} 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 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 be a valid inequality of P^{IP} where 0 ≤ k_{j} ≤ u_{j} for all j ∈ F. Lifting seeks to create a valid inequality of PIP, which takes the form

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 is valid inequality for where k_{j}=0 for all j ∈ F. Therefore, sequential up lifting assumes that is valid for and seeks to create an inequality of the form

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

Lifting can be approximate or exact. Exact lifting finds the strongest and/or possible. 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 u_{1} 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 x_{1=}=k* where k* ∈ {1, ..., u_{1}-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 be a valid inequality when x_{1}=k*where k* is integer and 0 ≤ k* ≤ u_{1}. For each 0 ≤ k ≤ u_{1} and define

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

And

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

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 x_{1}=0, and x_{1} 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 u_{1} 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 that is valid for .SLA up lifts x_{1 }by finding an α_{1∧ }that is the maximum value such that is valid for P^{IP}.

Set α_{1∧}:=M where

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

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

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

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

Change x_{1}’s objective coefficient in every pendant node to α_{1∧}

Create a single child constraint with no additional constraints.

*end if*

If and x* is non-integer, then begin

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

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

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

*end if*

*end while*

**Output**

If α_{1∧}= M, then α_{1∧}:=∞.

Report is a valid inequality for P^{IP}.

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

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

Solving this LP results in and . Two new child nodes are created. One adds on the constraint x_{1} ≤ 4 and the other x_{1} ≥ 5. The second node’s solution is and . Two new nodes are added, one with the constraint x_{2} ≤ 0 and the other with x_{2} ≥1. The LP solution to the left node, node 3, is and . 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 x_{1}+x_{2}. 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 .This node is fathomed, not because it is integer, but because

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

**Figure 1** provides a graphical view of lifting x_{1} into x_{2} ≤ 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 for each x_{1}=k for k=1, 2... u_{1}. 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**, x_{1}=1, x_{1}=3 and x_{1}=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 x_{2} 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 x_{1}+x_{2} ≤ 4, which intersects (4,0). If no integer solutions satisfy x_{1}+x_{2} ≤ 4, then the inequality is valid. However, node 5 finds such a violating point (2,3) and the objective function changes to .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 be a valid inequality of .Given a bounded integer program, the Sequential Lifting Algorithm terminates and reports a valid inequality , of P^{IP} . Furthermore, the coefficient α^{1∧ }returned from SLA is the equal to the α^{1∧} generated from Wolsey’s method. If defines a face of dimension r in ,then defines a face of dimension at least r+1 in P^{IP} as long as α_{1∧ }is finite.

**Proof: **Assume a node in the branching tree has an integer solution with z>β. Then 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 .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 . Consequently, SLA generates a valid inequality upon termination.

To show termination, observe that the IP is bounded. Thus, there can be at most integer solutions. The branching step can be implemented at most 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 subject to A_{x} ≤ b, x_{1} ≥ 1, 0 ≤ x_{i} ≤ u_{i} and is infeasible and both Wolsey’s method and SLA sets α_{1∧}=∞.

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

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

Finally, assume defines a face of dimension r in and so there exists r+1 affinely independent points in P_{x1}=0 that satisfy .Assume SLA terminates with afinite α_{1∧}. Then there exists some that determined the reported value of α_{1∧}. Furthermore, and . Clearly, 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 where Thus any integer solution is larger than β and α_{1∧} changes. From a computational standpoint, if a feasible point with x_{1} ≥ 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 (u_{1}, 0, 0, ..., 0) is always feasible and the starting value of α0 can be set equal to . 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 x_{1} into x_{2} ≤ 0 for would never terminate. Consequently, if SLA terminates for an unbounded integer program, then SLA determines the correct up lifting coefficient.

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 x_{1}=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 for x_{1} where and then up lifting .Thus, down lifting creates a valid inequality of the form .Now as in the up lifting case, the left hand side of this inequality becomes the objective function, Maximize ,and the constraints are the constraints of the integer program with the additional constraint of x_{1} ≤ u_{1}-1.

When an integer solution is found that is larger than β, the linear relaxation point, , is substituted into the 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 x_{1}=4, then x_{2} ≤ 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.

All objective functions are now changed to -1(4-x_{1})+x_{2}.

Node 3 also is integer with Z=1>β and x=(2, 3). Solving for α_{1v} in α_{1v} (4-2)+3=0 results in .Nodes 4 and 6 require branching, but eventually every node is either infeasible or .Thus, SLA terminates with .The reported valid inequality is or equivalently .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 x_{1}=k* where 0<k*<u_{1}, which is a combination of both down and up lifting. The substitution for down lifting is . The down lifting portion adds on the constraint x_{1} ≤ k*-1 to the root note. For an integer solution larger than β, a new value of α_{1v} is obtained by solving .

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

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

Notice that if ,and then one cannot sequentially lift x_{1} 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 x_{1}=k*=2, then x_{2} ≤ 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 to and add the constraint α1^(x_{1}-2)+x_{2}and add the constraint x_{1} ≥ k*+1=3. The optimal integer solution occurs at (4, 0), which sets . Any remaining nodes are easily fathomed. For the down lifting portion, set the objective function to and add the constraint x_{1} ≤ k*-1=1. The optimal integer solution is (0, 4), which sets . Since any inequality of the form α1x_{1}+x_{2} ≤ 3+2α1 is valid as long as .

To help clarify the idea that middle lifting may not result in a valid inequality, observe that x_{2} ≤ 1 is valid if x_{1}= 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∧} (x_{1}-3)+x_{2} and add the constraint x_{1} ≥ 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 . . Since no middle lifted inequality is valid. This is easily
verifiable in **Figure 3** as the point (3,1) is not an extreme point of *P ^{IP}*.

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 The a_{ij} were integers selected uniformly between 25 and 1, 000. (Note: Whena_{ij} <25, then the ui’s became extremely large and Wolsey’s could not finish in a reasonable time. So each a_{ij} ≥ 25.) The slackness, s, of the constraint determines the right hand side, .Various values of n were chosen as shown in Table 1.

The computational study starts with the valid inequality x_{1} ≤ u_{1} 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.

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?

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

- Karp RM (1972) Reducibility among combinatorial problems. Complexity of Computer Com- putations. The IBM Research Symposia Series 85-103.
- Land A, Doig A (1960) An automatic method of solving discrete programming problems. Econometrica 28: 497-520.
- Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization, John Wiley and Sons, New York.
- Gomory R (1969) Somepolyhedra related to combinatorial problems. Linear Algebra and it Applications 2: 451-588.
- Atamtürk A (2003) On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming 98: 145-175.
- Atamtürk A (2004) Sequence independent lifting for mixed-integer programming. Operations Research 52: 487-490.
- Balas E (1975) Facets of the knapsack polytope, Mathematical Programming 8: 146-164.
- Balas, E. and E. Zemel (1978). “Facets of the knapsack polytope from minimal covers,” SIAM Journal of Applied Mathematics 34: 119-148.
- Balas E, Zemel E (1984) Lifting and complementing yields all facets of positive zero- one programming polytopes. In: Cottle RW (ed.) Proceedings of the International Conference on Mathematical Programming, pp. 13-24.
- Balas E, Ng SM (1989) On the set covering polytope. II, Lifting the facets with coefficients in 0,1,2. Mathematical Programming 45: 1-20.
- Balas E, Fishetti M (1993) Lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets. Mathematical Programming 58: 325-352.
- Carr R (1996) Separating over classes of TSP inequalities defined by 0 node-lifting in polynomial time Integer Programming and Combinatorial Optimization. 5th International IPCO Conference Proceedings, pp. 460-474.
- Cho CD, Padberg MW, Rao MR (1983) On the uncapacitated plant location problem. II. Facets and lifting theorems. Mathematics of Operations Research 8: 590-612.
- Dahan X, Maza MM, Schost. E, Wu W, Xie Y (2005) Lifting techniques for triangular decompositions. Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation ISSA 05.
- De Farias IR JR, Johnson EL, Nemhauser GL (2002) Facets of the complementarity knap- sack polytope. Mathematics of Operations Research 27: 210-226.
- De Simone C (1990) Lifting facets of the cut polytope. Operations Research Letters 9: 341-344.
- Easton T, Hooker K (2008) Simultaneously lifting sets of variables and scaled multiple cover inequalities for knapsack polytopes. To appear in Discrete Optimization 5: 254-261.
- Felici G, Gentile C (2003) Zero-lifting for integer blocks structured problems. Journal of Combinatorial Optimization 7: 161-167.
- Gu Z, Nemhauser GL, Savelsbergh MWP (1998) Lifted cover inequalities for 0-1 integer programs: computation. Journal of Computing 10: 427-437.
- Gu Z, Nemhauser GL, Savelsbergh MWP (1999) Lifted cover inequalities for 0-1 integer programs: computation. Mathematical Programming 85: 439-467.
- Koster A, Hoesel S, Kolen A (1998) The partial constraint satisfaction problem: Facets and lifting. Operations Research Letters 23: 89-98.
- Nemhauser GL, Vance PH (1994) Lifted cover facets of the 0-1 knapsack polytope with GUB constraints. Operations Research Letters 16: 255-263.
- Park K (1997) Lifting cover inequalities for the precedence-constrained knapsack problem. Discrete Applied Mathematics 72: 219-241.
- Richard J, De Farias I, Nemhauser G (2003) Lifted inequalities for 0-1 mixed integer programming: Superlinear lifting Integer Programming 98: 115-143.
- Zemel E (1989) Easily computable facets of the knapsack polytope. Mathematics of Operations Research 14: 760-764.
- Hammer P, Johnson E, Peled U (1975) Facets of regular 0-1 polytopes. Mathematical Programming 8: 179-206.
- Padberg M (1973) On the facial structure of set packing polyhedral. Mathematical Programming 5: 199-215.
- Wolsey LA (1975) Faces for a linear inequality in 0-1 variables. Mathematical Programming 8: 165-178.
- Wolsey LA (1975b) Facets and strong valid inequalities for integer programs. Operations Research 24: 367-372.
- Gu Z, Nemhauser GL, Savelsbergh MWP (2000) Sequence independent lifting in mixed integer programming. Journal of Combinatorial Optimization 4: 109-129.
- Shebalov S, Klabjan D (2006) Sequence independent lifting for mixed integer programs with variable upper bounds. Mathematical Programming 105: 523-561.
- Wolsey LA (1977) Valid inequalities and superadditivity of 0/1 integer programs. Mathematics of Operations Research 2: 66-77.
- Santanu SD, Jean-Philippe PR (2006) Linear programming based lifting and its application to primal cutting plane algorithms. School of Industrial Engineering, Purdue University.
- Zemel E (1978) Lifting the facets of 0-1 polytopes. Mathematical Programming 15: 268-277.
- The CPLEX Solver on ILOG’s Home Page
- Gutierrez T (2007) Sequential lifting and simultaneous up lifting of integer variables, Kansas State University, Manhattan, Kansas.

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

- ACS Nano
- AI Algorithm
- Advanced Materials
- Advantages of E-Business
- Applied Engineering
- Applied Statistics
- Architect
- Architectural Drawing
- Architectural Engineering
- Artificial Intelligence
- Automated Mining
- Automation
- Behavior-based systems
- Bioengineering Application
- Biological Engineering
- Biomaterial Science
- Biomechanics
- Biomechanics and Robotics
- Biomedical Equipment
- Biomedical Instrumentation
- Biomedical Services
- Biomedical science
- Biomimetics
- Bioprocessing
- Bioreactors
- Biosensor elements
- Biotechnology Engineering
- Brittle Materials
- Building design
- Business & Management
- Cell Apoptosis
- Ceramics Engineering
- Cognitive Systems Engineering
- Commercialization of New Techniques
- Composite Materials
- Computational Neuroscience
- Concrete
- Construction
- Construction Engineering
- Construction Estimating Software
- Design and Microfabrication
- Digital Image Processing
- Dynamical System
- Electronic Material Development
- Engineering Drawing
- Entrepreneurship
- Fabric Formwork
- Fermentation Science
- Finance management
- Fuzzy Logic
- Gene Expressions
- Genetics
- Health care management
- Industrial Crystallization
- Industrial Engineering
- Industrial Robotics
- Intelligent Robotics
- Interior Design
- Interior Designing
- Internal Medicine
- Landscape Architecture
- Logistics
- Lovotics
- Management Cybernetics
- Manufacturing system
- Materials Engineering
- Materials Management
- Medical Device
- Medical Robotics
- Medication
- Metallic Materials (Ferrous & Nonferrous)
- Mobile Device
- Mobile Repots
- Molecular Electronics
- Molecular and Medicine science
- Nano Composites
- Nano Materials
- Nano Particles
- Nano Structures
- Neural Networks
- Neurorobotics
- Nonlinear Dynamics
- Operations Research
- Polymeric Materials
- Porous Materials
- Process Engineering
- Production and Operations Management
- Regenerative Medication
- Rehabilitation Technology
- Reliability engineering
- Robotic Rehabilitation
- Semiconductors
- Simulation
- Social Robots
- Sociology of Architecture
- Spintronics
- Stochastic control
- Supply Chain Management
- Technologies Management
- Telerobotics
- Tissue Engineering Development
- Urban Design
- Urban Planner
- swarm intelligence and robotics

- Advances in Robotics & Automation
- Engineering and Technology Journals
- Electrical Engineering Journals
- Software Engineering Journals
- Architectural Engineering Journals
- Automation Journals
- Management Journals
- Bioengineering Journals
- Aerospace Engineering Journals
- Instrumentation Engineering Journals
- Tissue Engineering Journals
- Engineering Journals
- Aeronautics Journal
- Material Sciences Journal
- Mechanical Engineering Journal
- Automobile Engineering Journal

- Total views:
**12548** - [From(publication date):

May-2015 - Jul 16, 2019] - Breakdown by view type
- HTML page views :
**8732** - PDF downloads :
**3816**

**Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals**

International Conferences 2019-20