Ieor 4600 Mixed-Integer Rounding Inequalities
Download 16.66 Kb.
|
- Navigate this page:
- 0 ≤ x , and 0 ≤ y ≤4 (and y integral) . In addition, the following constraint must be satisfied: x + 5y ≥ 12
- K y + x
- Other cases and forms of the MIR inequality 1.
| IEOR 4600
Mixed-Integer Rounding Inequalities As the name suggests, mixed-integer rounding inequalities (MIR inequalities for short) arise in the context of mxed-integer programs, that is to say, optimization problems where some of the variables are required to take integral values (and some are not). Suppose that, from a mixed-integer program, we isolate two variables: 0 ≤ x, and 0 ≤ y ≤4 (and y integral). In addition, the following constraint must be satisfied: x + 5y ≥ 12. The following figure shows the feasible region for the continuous relaxation of this set (i.e. what we get by dropping the requirement that y be integral). 
On the other hand, the following figure shows the feasible region when y is required to be integral. In this figure, the heavy blue lines constitute the feasible region – all the points in those five lines, and just those points, are feasible. 
The convex hull of the feasible region for the mixed integer set is given in the next figure: 
Looking at this figure, we are interested in the line joining the points (0,3) and (2,2). This line is important, because it defines a part of the boundary of the convex hull of the mixed-integer set which is not a part of the boundary of the feasible region. The next figure highlights this inequality. 
In this figure, the yellow triangle is the chunk of the feasible region for the continuous relaxation that is cut-off by the new inequality. This inequality, x + 2y ≥ 6, is the MIR inequality arising from our initial system. Comment: notice that in deriving this inequality, we never really used the fact that y is nonnegative (or even the upper bound on y). The general form of this process is as follows. We start with a system with two variables, say x and y, where x is nonnegative and y is required to be integral. In addition, we are given a constraint of the form: x + Cy ≥ b, where C > 0 and b are given values. To derive an MIR inequality from this set we write f = b – C└ b/C┘ (here, └ b/C┘ is the floor, or “round-down”, of b/C). Then the MIR inequality is: x + f y ≥ f ┌ b/C┐ (MIR) where ┌ b/C┐ is the ceiling, or “round-up” of b/C. In the example above, C = 5 and b = 12, so f = 2 and ┌ b/C┐ = 3. In the most effective use of the MIR inequalities, the variables x and y may not appear directly in a problem we are interested in – rather, x and y are variables that we obtain by aggregating other variables that we explicitly have. For example, y may be a sum of existing integer variables. Likewise, the inequality x + Cy ≥ b itself may be something that we can deduce from the structure of the problem. As an example, suppose that we are given a mixed-integer program that contains continuous variables x1, x2, …., xn, and 0/1 variables y1, y2, …, yn, together with the inequalities: x1 + x2 + … + xn ≥ D, (1) 0 ≤ xj ≤ K yj for all j (2) Here, D and K are positive constants that are part of the data. Formulations of this type frequently arise as part of more complex problems. The x variables describe amounts “produced” or “shipped”, and constraint (1) states a minimum production amount. The y variables control production – in order to have xj > 0, we need yj = 1 (and, typically, we will pay a fixed cost). For the sake of simplicity, consider the set of indices {1, 2, 3}. Then we can combine (1) and (2) to derive the inequality: K(y1 + y2 + y3) + x4 +… + xn ≥ D, (3) If we introduce two new variables, y = y1 + y2 + y3 and x = x4 +… + xn , then (3) can be rewritten as: K y + x ≥ D, (4) Notice that y is integral, and that x is continuous and nonnegative – so we can generate an MIR inequality from (4). This will be an inequality of the form f y + x ≥ B, (5) for appropriate numbers r and B computed from K and D as described before. In deriving this inequality from (1) and (2), we picked the set {1, 2, 3} just to drive the example, but clearly the same construction would work with any subset of the indices. In general, n could be large, so the number of such subsets will be enormous. So, the question arises: how can we select which sets of indices to use? One way to answer the question is to place it in the context of a cutting-plane algorithm. We don’t want to include into our formulation all possible inequalities (5) – rather, we will just include those that are violated by a solution to the LP-relaxation of our problem. Can you think of a procedure that will find the most violated inequality (5), given a fractional solution to the problem? Hint: no matter how we choose the set of indices used to obtain the aggregated variables y and x, the values r and B will always be the same. Other cases and forms of the MIR inequality 1. As mentioned in the discussion leading to inequality MIR given above, we did not need b > 0. As an example, suppose that we have the system x + 2 y ≥ -11, where y is integral and x nonnegative. If you plot the feasible region, you will see that the corresponding inequality is x + y ≥ -5, which is just a special case of (MIR) with f = 1. 2. Suppose we have a system of the form: 15.2 + x ≥ y, (6) where x is nonnegative and y is integral. As before, the idea is that this system is just part of a bigger problem, but we are focusing on part of the formulation in order to tighten it. We can rewrite (6) as x - y ≥ -15.2, (7) If we (implicitly) introduce a new integral variable, z, defined as z = - y, then (7) becomes x + z ≥ -15.2, (8) Using C = 1, this is just an example that can be handled with the usual MIR inequality. What is this inequality, in terms of x and y? 3. Consider the system y1 + 2 y2 + s / 11 ≥ 72/11 (9) where the yi are integral variables, and s is a nonnegative variable. We can handle this system in a number of ways. (a) First, since the yi are integral, then we can (implicitly) treat the quantity y1 + 2 y2 as an integral variable. Similarly, s/11 can be viewed as a nonnegative variable. So, from (9) we get the MIR inequality (with C = 1 and b = 72/11, obtaining f = 6/11): 6/11( y1 + 2 y2 ) + s / 11 ≥ 42/11 (10) (b) Suppose that, in addition to (9), we also have that the yi are nonnegative (and not just integral). Now we will instead treat 2y2 as an integer variable, and y1 + s /11 as a nonnegative variable Then, from (9) we get the MIR inequality (with C = 2, and b = 72/11, obtaining f = 3/11): y1 + 3 / 11 y2 + s / 11 ≥ 12/11 (11) There are many possible uses of the reasoning that led us to the basic MIR inequality given above. What always works is that you should isolate which variables you want to view as integral or not, then aggregate them into one integral variable and one continuous variable, then plot the feasible region and look for a triangle to “clip”. Download 16.66 Kb. Share with your friends:
|