Integer Programming (Chapter 5)

Integer Programming

Chapter Overview

• Range of Topics Covered:

  • Linear programming

  • Graphical analysis

  • Computer solutions

  • Sensitivity analysis

  • Examples: integer values, transportation, diets, investment, blends, etc.

Introduction to Integer Programming

• Focus of Chapter:

  • Transition from general linear programming to specific cases involving integer constraints.

  • Reference to prior marketing example to outline constraints and solutions.

• Key insights from marketing example:

  • Unconstrained problem results: fractions (e.g., 1 or 1/3) were found.

  • Rounding leads to:

  • Rounding up resulted in non-feasible solutions despite a higher objective function value.

  • Rounding down yielded a feasible but non-optimal solution.

Types of Integer Programming Models

• Classification of Models:

  • Total Integer Model:

  • All decision variables must be integers.

  • Mixed Integer Model:

  • Some decision variables must be integers while others can be real numbers.

  • 0-1 (Binary) Integer Model:

  • All variables can only take values of 0 or 1.

Example of Total Integer Model: Machine Shop

1. Machine Information:

   • Machine Types:

     • Press:

     • Floor Space: 15 sqft

     • Purchase Price: $8000

     • Profit: $100/day

     • Lathe:

     • Floor Space: 30 sqft

     • Purchase Price: $4000

     • Profit: $150/day

2. Objective:

   • To determine the number of presses and lathes to maximize daily profit given:

     • Budget: $40,000

     • Floor space: 200 sqft

3. Formulation Steps:

   • Decision Variables:

     • Let $x_1$ = number of presses purchased

     • Let $x_2$ = number of lathes purchased

   • Objective Function:

     • Maximize Profit: Z = 100x1 + 150x2

   • Constraints:

     • Budget constraint: 8000x1 + 4000x2 \leq 40000

     • Space constraint: 15x1 + 30x2 \leq 200

     • Non-negativity: x1, x2 \geq 0

4. Results of Linear Programming Solution:

   • Maximum Daily Profit: $1055.56

   • Purchasing Recommendation (LP Solution):

     • Presses: 2.22

     • Lathes: 5.56

5. Rounding the LP Solution:

   • Rounded Solution:

     • Presses: 2

     • Lathes: 5

     • Profit Calculation: Z = 100(2) + 150(5) = 950

Feasibility of Solutions

• Feasibility Investigation:

  • LP Feasible Points: Infinity ($ ext{∞}$)

  • IP Feasible Points: 29

• Comparison of Feasibility:

  • More feasible solutions in LP leads to misleading thoughts about complexity.

  • Only corner points of the feasible region in LP are necessary to determine optimal solution.

Solving Integer Programs

• Process of Transitioning to Integer Programs:

  • Optimal solution found while mandating integer solutions.

  • Conversion from LP to IP involves stricter variable conditions.

Solver Parameters for IP

• Objective Setup:

  • Maximize objective function under certain conditions.

• Variable Cells Modification:

  • Adjustable range for variables (e.g., C4:D4).

• Constraints Setup:

  • Integer conditions: both variable cells must result in integer solutions.

  • Other conditions as per resource constraints (e.g., E5).

Mixed Integer Model Example

1. Investment Problem Overview:

   • Alice has $250,000 to invest across three options: condos, land, municipal bonds.

   • Objective: Maximize returns in one year.

2. Decision Variables Defined:

   • x_1 - condos purchased (integer)

   • x_2 - acres of land purchased (real)

   • x_3 - municipal bonds purchased (integer)

3. Profits and Constraints:

   • Maximize Profit: 9000x1 + 1500x2 + 1000x_3

   • Budget Limit: 50000x1 + 12000x2 + 8000x_3 \leq 250000

   • Availability Constraints: x1 \leq 4, \ x2 \leq 15, \ x_3 \leq 20

0-1 Integer Model Example

1. Investment Decision Structure:

   • Four investment options available with a total fund of $14,000.

2. Decision Variables Formulation:

   • Define binary variable for each investment option (0 or 1).

3. Objective Function:

   • max return: 16x1 + 22x2 + 12x3 + 8x4

4. Constraints to Note:

   • Cash Limit: 5x1 + 7x2 + 3x3 + 4x4 \leq 14000

   • Each investment variable must be binary: x_i \in {0, 1}

Logical Constraints in Binary Models

• Logical Forms to Handle Restrictions:

  • At most two investments constraint:

  • x1 + x2 + x3 + x4 \leq 2

  • If-Then Constraints:

  • Two forms available (direct modeling of logical implications).

Set Covering Example

1. Context and Objective:

   • Goal: Construct minimum hubs such that every city has access to a hub within 300 miles.

2. Decision Variables:

   • x_i (1 if hub in city $i$, 0 otherwise).

3. Objective Function:

   • Minimize number of hubs opened: Z = x1 + x2 + x3 + … + x{12}

4. Covering Constraints for Cities:

   • Specific coverage conditions laid out for each city in proximity to hubs, ensuring operationality.

Summary

• Integer programming crucial for specific decision-making scenarios where the solution must adhere to whole number requirements.

• Differences in models (total integer, mixed integer, and 0-1) highlight the flexibility needed for various decision scenarios.