OMIS 327 Exam 2

Integer programming (IP) model -

 one where one or more of the decision variables has to take on an integer value in the final solution

3 types of integer programming problems 

1. Pure integer programming - all variables have integer values 

2. Mixed integer programming - some but not all of the variables have integer values 

3. Zero-one integer programming - special cases in which all of the decision variables must have integer solution values of 0 or 1

An integer solution..

Can never be better than the LP solution and is usually a lesser value.

Binary variables (aka 0-1 variable)

 decision variable that must be equal to 0 or 1

• Corresponds to yes/ no or taken or not taken activity 

• 1 = activity is undertaken

• 0 = activity not undertaken

Integer solution

not just rounded number of the non integer solution 

Fix charge problem

charge is incurred if an activity is undertaken at any positive level

• Independent of the level of the activity and is known as a fixed charge (or fixed cost)

  • A fixed charge is incurred if an activity is undertaken at any positive level 

  • No fixed charge is incurred i the activity is not undertaken at all

  • Use 0-1 variables

In an integer problem you cannot

round the non-integer solution to an integer

Node

 indicated by a circle, generally represents a geographical location

Arc

indicated by an arrow, generally represents a route for getting a product from one node to another

Flows

decision variables, denoted by x_ij, they represent the amounts shipped on the various arcs

Assignment models

 used to determine the most efficient assignment of people or equipment to particular tasks 

• Objective is to minimize total cost or total task time

• need to = supply of workers (vertical) and = demand for workers (horizontal)

Why we distinguish between network models from other LP models -

 structure of these models allows them to be represented graphically in a way that is intuitive to users. This graphical representation can then be used as an aid in the spreadsheet model development. 

Transportation problem

deals with distribution of goods from several points of supply (origins or sources) to a number of points of demand (destinations) 

• need to be < supply to minimize costs (vertical) and equal to demand (horizontal)

Linear program for transportation problem includes: 

• Minimize transportation cost (objective) 

• Not exceed supply (constraint)

• Meet demand (constraint)

X_ij

number of units shipped from source i to destination j 

Ex: where:

• i = 1,2,3 (1= des moines, 2 = evansville, 3= fort lauderdale) 

• j = 1,2,3( 1= albuquerque, 2 = boston, 3 = cleveland 

Ex: X₂₃ represents the amount shipped from evansville to cleveland (x 2 -3 not 23)

Examples of supply and demand constraints for the following variables 

• i = 1,2,3 (1= des moines, 2 = evansville, 3= fort lauderdale) 

• j = 1,2,3( 1= albuquerque, 2 = boston, 3 = cleveland

Transshipment point

 physical location in between source(s) and destination(s)

• A location where goods simply pass through

• node with new outflow (or net inflow) equal to 0

• start point flow - end point flow

Inflow

arc pointed into a node

Outflow

 an arrow pointed out of a node

Net inflow

for any node is defined as total inflow minus total outflow for that node (i.e. total inflow - total outflow)

Net inflow equation

total inflow - total outflow

Net outflow equation

 total outflow - total inflow

Origin

node with positive net outflow

sumif(startpoint only)

Destination

node with positive net inflow

sumif(end point only)

Framework for network design decisions 

• Maximize the overall profitability of the supply chain network while providing customers with the appropriate responsiveness

• Many trade offs during network design

• Network design models used: 

  • To decide on locations and capacities 

  • To assign current demand to facilities and identify transportation lanes

Shortest route problem

find the shortest distance from one location to another

Can be modeled as

• linear programming problem with 0-1 variables

• Special type of transshipment problem 

• Using specialized algorithm

How to use X_ij variable 

• X_ij = 1, then choose

• X_ij = 0, then cannot select

How to find total distance

 multiplying the binary decision for each route (flow) with its distance, then adding up all the distances across all the routes

• ∑(Flow * distance)

Ex: 100X₁₂ + 200x₁₃ + 50X₂₃  etc

Rules for shortest route constraints

• Origin location (node 1) = total outflow should = 1

• All intermediate nodes = total outflow should = 0 

  • Calculated by total inflow - total outflow OR total outflow - total inflow 

• Destination location (last node) = total outflow should = 1

Minimal spanning tree problem

 connect all points of a network together while minimizing the total distance of the connections.

• Linear programming can be used but is complex 

• Minimal spanning tree technique is easy

A spanning tree

for an n-node network is a set of n-1 arcs that connects every node to every other node

Steps for the minimal spanning tree technique 

1. Select any node in the network

2. Connect this node to the nearest node that minimizes the total distance

3. Considering all of the nodes that are now connected, find and connect the nearest node that is not connected. If there is a tie for the nearest node, select one arbitrarily. A tie suggests there may be more than one optimal solution. 

4. Repeat the third step until all nodes are connected.

How many distances to add up =

n-1 

• So if you have 5 nodes, you are gonna have 4 distances to add up (between 2 houses 1 road)

How to solve minimizing spanning tree method - 

• Start by picking the min distance for each

  • Going chronologically for each node 

• Once you start to branch out to ones that are too far away, you can look at which ones you have already “unlocked”/ accessed via a connecting branch

  • You can use these to connect to the node instead

• Start looking at the node you need to get to, look at what branches are leading to it and if you’ve unlocked the starting nodes for them 

• If you have unlocked the node then you pick the shortest one 

• Keep going in chronological order until you have reached all nodes and have n-1 branches done. (so say 7 nodes and 6 branches)

transshipment problem

optimization model that determines the lowest-cost routing of goods from origins through transshipment points to final destinations

minimal-spanning tree

All the nodes must be connected in this technique

The objective of a transportation problem

to minimize the total transportation (shipping) cost from sources to destinations.

non integer solution: (1)

integer solution: (2)

1. ex: 3.75, 2.49

2. 3,4,5,

integer = whole number

non-integer = not whole number

In the minimal-spanning tree technique, if there is a tie for the nearest node, that suggests

there may be more than one optimal solution.

[Binary Variable Scenario]: Limiting the number of alternatives selected

involves limiting the number of projects or items that are selected from a group

ex: Quemo chemical required to select no more than 2 projects

• constraint = X₁ + X₂ + X₃ < 2

• Saying all of the projects (value of 1 or 0) must be < 2

[Binary Variable Scenario]: Dependent selections

the selection of one project depends on the selection of another

• ex: Quemo’s catalytic converter could only be purchased if the software was purchased

  • constraint → X₁ < X₂ or X₁ - X₂ < 0

• If we wished for the catalytic converter and software
  projects to either both be selected or both not be
  selected, the constraint would be
  - X1 = X2 or X1 − X2 = 0

Linear program for assignment example

X_ij = 1 if person i is assigned to project j 0 otherwise

where i = 1,2,3 (1 = Adams, 2 = brown, 3 = cooper)

j = 1,2,3 (1 = project 1, 2 = project 2, 3 = project 3

solving an employee scheduling thing

define the decision variables as the number of employees starting work on each day of the week

• by knowing the values of these decision variables, the other output variables can be calculated