• Author / Uploaded
• simran

Citation preview

INTEGER PROGRAMMING

(With special emphasis on choosing plant locations in Capital Budgeting; Flight scheduling- to ensure maximum output)

Compiled by: Simran Katyal (14108006) Hansin Garg (14108011)

Section 1: Background of this Technique Over the last 20 years, the combination of faster computers, more reliable data, and improved algorithms has resulted in easy solutions of many integer programs of practical interest. Integer programming models are used in a wide variety of applications, including scheduling, resource assignment, production planning, supply chain design, auction design, telecommunication networks, cellular networks and many others.

Section 2: Introduction I.

An integer-programming problem is a mathematical optimization or feasibility program in which some or all of the variables are

restricted to be integers. The term also refers to Integer Linear Programming (ILP), in which the objective function and the constraints are linear. II.

Linear programming (linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

Section 3: Abstract

I.

The foundation of much of analytical decision-making is linear programming. In a linear program, there are variables, constraints, and an objective function. The variables, or decisions, take on numerical values. Constraints are used to limit the values to a feasible region. These constraints must be linear in the decision variables. The objective function then defines which particular assignment of feasible values to the variables is optimal: it is the one that maximizes (or minimizes, depending on the type of the objective) the objective function. The objective function must also be linear in the variables.

II.

Integer programming adds additional constraints to linear programming. An integer program begins with a linear program,

and adds the requirement that some or all of the variables take on integer values. III.

There are two main reasons for using integer variables when modeling problems as a linear program:  The integer variables represent quantities that can only be integer. For example, it is not possible to build 3.7 cars.  The integer variables represent decisions and so should only take on the value 0 or 1.

These considerations occur frequently in practice and so integer linear programming can be used in many applications areas.

KEYWORDS 1. Integer Programming 2. Linear Programming 3. Optimization 4. Capital Budgeting 5. Scheduling 6. Objective Function 7. Constraints

Section 4: Literature Review

1) In 1947, G.B. Dantzig conceived the Simplex Method to solve military planning problems asked by the US Air Force that were written as a linear program, that is a system of linear equations.

2) Fleet Assignment Integer programming model (By: Jeph Abara): By considering available resources like aircraft and gates, American airlines creates a schedule with repeating patterns of flights within it, that comprises of over 2300 flights per day to 150 cities using more than 500 jets. The objective of the fleet assignment process is to assign as many flight segments as possible in a schedule to American Airline’s ten fleet types, while optimizing a certain objective function (saving operating costs or maximizing profit) and meeting operational constraints (restriction of certain flights to operate within certain aircraft types, restriction on the number of aircraft that can remain overnight at particular stations, limits on arrivals and departures at a station during the day. The integer program formulation, on being given a schedule with the departure and arrival times indicated, solves the fleet assignment problem by determining which flights should be assigned to which aircraft types to optimize the objective function.

Section 5: Formulation

A) An integer linear program in canonical form is expressed as:

B) An ILP in standard form is expressed as:

Where the entries of c,b are vectors and A is a matrix, having integer values.

Variants:  Mixed integer linear programming (MILP) involves problems in which only some of the variables, xi, are constrained to be integers, while other variables are allowed to be non-integers.  Zero-one linear programming involves problems in which the variables are restricted to be either 0 or 1. Note that any bounded integer variable can be expressed as a combination of binary variables.

 The region depicted in Green is the feasible region for solving the

linear equations in x1 and x2 (after plotting the constraints). Note that x1 and x2 are required to be Integers for it to be an Integer Linear Programming function.

Section 6: Case Studies

a) Capital Budgeting: In a typical capital-budgeting problem, decisions involve the selection of a number of potential investments. The investment decisions might be to choose among possible plant locations, to select a configuration of capital equipment, or to settle upon a set of research-and-development projects. Often it makes no sense to consider partial investments in these activities, and so the problem becomes a go–no-go integer program. The decision variables are taken to be xj = 0 or 1, indicating that the jth investment is rejected or accepted. Assuming that cj is the contribution resulting from the jth investment and that aij is the amount of resource i, such as cash or manpower, used on the j th investment, we can state the problem formally as:

Maximize: ∑Xn Subject to:

= cjxj

(j= 1,2…n)

∑Xn = aijxj ≤ bi (i= 1,2...m) Xj= 0 or 1

(j= 1,2...n)

Objective of investigation: The objective is to maximize total contribution from all investments without exceeding the limited availability bi of any resource.

b) Scheduling: The entire class of problems referred to as sequencing, scheduling, and routing are inherently integer programs. As a specific example, consider the scheduling of airline flight personnel. The airline has a number of routing ‘‘legs’’ to be flown, such as 10 A.M. New York to Chicago, or 6 P.M. Chicago to Los Angeles. The airline must schedule its personnel crews on routes to cover these flights. One crew, for example, might be scheduled to fly a route containing the two legs just mentioned. The decision variables, then, specify the scheduling of the crews to routes: Xj = 1 If a crew is assigned to route j; 1 Otherwise. Let aij = 1 1

If leg i is included on route j; Otherwise.

And cj = Cost for assigning a crew to route j.

The coefficients aij define the acceptable combinations of legs and routes, taking into account such characteristics as sequencing of legs for making connections between flights and for including in the routes ground time for maintenance. The model becomes: Minimize:

∑Xn= cjxj

Subject to:

∑aijxj= 1

(j= 1,2…n) (i = 1, 2…m)

Xj = 0 or 1 (j = 1, 2…n) The ith constraint requires that one crew must be assigned on a route to fly leg i.

c) Warehouse Location: In modeling distribution systems, decisions must be made about tradeoffs between transportation costs and costs for operating distribution centers. As an example, suppose that a manager must decide which of ‘n’ warehouses to use for meeting the demands of ‘m’ customers for a good. The decisions to be made are which warehouses to operate and how much to ship from any warehouse to any customer. Let Yi = 1 If warehouse i is opened 1 If warehouse i is not opened.

Xij = Amount to be sent from warehouse i to customer j.

The relevant costs are: i. Fi = Fixed operating cost for warehouse i, if opened (for example, a cost to lease the warehouse). ii. Cij = Per-unit operating cost at warehouse i plus the transportation cost for shipping from warehouse i to customer j. There are two types of constraints for the model: i. The demand dj of each customer must be filled from the warehouses. ii. Goods can be shipped from a warehouse only if it is opened.

The model is: Minimize:

∑∑ cijxij + ∑fiyi

Subject to:

∑xij = dj ∑xij − yi(∑dj) ≤ 0

(i= 1,2…m), (j= 1,2…n) (j= 1,2…n) (i= 1,2…m)

xij ≥ 0 (i= 1,2…m) (j= 1, 2...n) yi = 0 or 1

(i= 1,2…m)

d) Furniture Manufacturer:

Section 7: Scope of this technique

 An industrial application: An enterprise manufactures boards (such as printed circuit boards). Holes, into which elements will be inserted, are to be drilled into the boards. From the technical drawing, we can determine the distance cij between the ith and jth hole to be drilled for i, j = 1,2…n. A computer numerical control (CNC) machine will process the boards automatically. The goal is to determine an optimal path so that its length (hence, the total machining time per board) is minimal.

 Classical (one-dimensional) formulation: A building contractor needs steel rods of lengths l1, l2...lm to reinforce a construction. The contractor needs b1 pieces of rods of length l1, it needs b2 pieces of rods of length ℓ2, and it needs bm pieces of rods of length lm. Steel works supply rods of a few standard lengths L1, L2…Ln. A rod of length Lj costs cj for j = 1, 2…n. The goal is to determine how many rods to order from the steel works and how to cut them to reinforce the construction with minimum purchase expenses.

 Classical formulation: A travelling salesman is to visit n cities, having some business in each of them. The salesman is to visit each city exactly once. The distance of the city i from the city j is cij for i, j = 1, 2…n. The goal is to determine the order of the cities in which the salesman is to visit them so that the salesman’s travelling expenses are minimal.

 Transport formulation: A company has to deliver goods/ a mail-order firm has to deliver parcels ton customers/ addressees. (A postal service provides regular collection of mail from post boxes or regular transport of packets from post offices in the city; a refuse collection service provides regular collection of rubbish from the dustbins that are located at n spots; etc.) The distance between the places i and j, which are to be serviced, is cij for i, j = 1, 2… n. The goal is to determine an optimal – shortest – round-trip.

Section 8: References TITLE

AUTHOR 

SOURCE

Applying Integer Linear Programming to the Fleet Assignment Problem

Jeph Abara

Interfaces, Volume 19, Number 4, July­August 1989 (pp. 20­28)

Optimal planning in large multi­site production networks

Christian H. Timpe, Josef Kallrath

A Bound on Solutions of Linear Integer Equalities and Inequalities Multi­project Scheduling with Limited Resources

European Journal of Operational Research, 126 (2000), pp. 422­ 435 Von zur Gathen, J. and Proc Amer. Math. Soc. 72 155­ Sievekmg, M. (1978). A 158 A. A. B. Pritsken, L. J. Watters, and P. M. Wolfe.

Zero–One Programming Approach Management Science 1969

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