Introduction to Integer Programming in Production Planning
Integer Programming
Integer Programming
•
Programming = Planning in this context
•
Origins go back to military logistics in WWII
(1940s).
•
In a survey of Fortune 500 firms, 85% of those
responding said that they had used linear or
integer programming.
•
Why is it so popular?
–
Many different real-life situations can be modeled
as integer programs (IPs).
–
There are efficient algorithms to solve IPs.
Standard form of integer program (IP)
maximize
c
1
x
1
+c
2
x
2
+…+c
n
x
n
(objective function)
subject to
a
11
x
1
+a
12
x
2
+…+a
1n
x
n
b
1
(functional constraints)
a
21
x
1
+a
22
x
2
+…+a
2n
x
n
b
2
….
a
m1
x
1
+a
m2
x
2
+…+a
mn
x
n
b
m
x
1
,
x
2
,
…
,
x
n
Z
+
(
s
e
t
c
o
n
s
t
r
a
i
n
t
s
)
Note
: Can also have
equality
or
≥
constraint
in non-standard form.
Standard form of integer program (IP)
•
In vector form:
m
a
x
i
m
i
z
e
c
x
(
o
b
j
e
c
t
i
v
e
f
u
n
c
t
i
o
n
)
s
u
b
j
e
c
t
t
o
A
x
b
(
f
u
n
c
t
i
o
n
a
l
c
o
n
s
t
r
a
i
n
t
s
)
x
(
s
e
t
c
o
n
s
t
r
a
i
n
t
s
)
I
n
p
u
t
f
o
r
I
P
:
1
n
v
e
c
t
o
r
c
,
m
n
m
a
t
r
i
c
e
A
,
m
1
v
e
c
t
o
r
b
.
O
u
t
p
u
t
o
f
I
P
:
n
1
i
n
t
e
g
e
r
v
e
c
t
o
r
x
.
•
Note
: More often, we will consider
mixed integer programs (MIP),
that is, some variables are integer,
the others are continuous.
Example of Integer Program
(Production Planning-Furniture Manufacturer)
•
Technological data:
Production of 1 table requires
5
ft pine,
2
ft oak,
3
hrs labor
1 chair requires
1
ft pine,
3
ft oak,
2
hrs labor
1 desk requires
9
ft pine,
4
ft oak,
5
hrs labor
•
Capacities for 1 week:
1500
ft pine,
1000
ft oak,
20
employees (each works
40
hrs).
•
Market data:
•
G
o
a
l
:
F
i
n
d
a
p
r
o
d
u
c
t
i
o
n
s
c
h
e
d
u
l
e
f
o
r
1
w
e
e
k
that will maximize the profit.
Production Planning-Furniture Manufacturer:
modeling the problem as integer program
The goal can be achieved
by making appropriate decisions.
First define decision variables:
Let
x
t
be the number of tables to be produced;
x
c
be the number of chairs to be produced;
x
d
be the number of desks to be produced.
(Always define decision variables properly!)
Production Planning-Furniture Manufacturer:
modeling the problem as integer program
Objective
is to maximize profit:
max 12x
t
+ 5x
c
+ 15x
d
Functional Constraints
capacity constraints:
pine: 5x
t
+ 1x
c
+ 9x
d
1500
oak: 2x
t
+ 3x
c
+ 4x
d
1000
labor:
3x
t
+ 2x
c
+ 5x
d
800
market demand constraints:
tables:
x
t
≥ 40
chairs:
x
c
≥ 130
desks:
x
d
≥ 30
Set Constraints
x
t
,
x
c
,
x
d
Z
+
Solutions to integer programs
•
A
solution
is an assignment of values to variables.
•
A solution can hence be thought of
as an
n
-dimensional vector.
•
A
feasible solution
is an assignment of values to
variables such that all the constraints are satisfied.
•
The
objective function value
of a solution is obtained
by evaluating the objective function at the given point.
•
An
optimal solution
(assuming maximization) is one
whose objective function value is greater than or equal
to that of all other feasible solutions.
Topics in this class about
Integer Programming
•
Modeling real-life situations as integer
programs
•
Applications of integer programming
•
Solution methods (algorithms) for integer
programs
•
(optional) Using software (called AMPL) to
solve integer programs
Next time
:
IP modeling techniques
Integer programming, a technique rooted in military logistics during WWII, is widely used in various industries due to its ability to model real-life situations efficiently. By formulating problems in a standard form and utilizing algorithms, integer programs can optimize decision-making processes. An example in production planning for a furniture manufacturer demonstrates how integer programming can maximize profit through strategic decision variables and constraints.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Integer Programming Programming = Planning in this context Origins go back to military logistics in WWII (1940s). In a survey of Fortune 500 firms, 85% of those responding said that they had used linear or integer programming. Why is it so popular? Many different real-life situations can be modeled as integer programs (IPs). There are efficient algorithms to solve IPs.
Standard form of integer program (IP) maximize c1x1+c2x2+ +cnxn subject to a11x1+a12x2+ +a1nxn b1 a21x1+a22x2+ +a2nxn b2 . am1x1+am2x2+ +amnxn bm x1, x2, , xn Z+ (objective function) (functional constraints) (set constraints) Note: Can also have equality or constraint in non-standard form.
Standard form of integer program (IP) In vector form: maximize cx (objective function) subject to Ax b (functional constraints) x (set constraints) + Z n Input for IP: 1 n vector c, m n matrice A, m 1 vector b. Output of IP: n 1 integer vector x . Note: More often, we will consider mixed integer programs (MIP), that is, some variables are integer, the others are continuous.
Example of Integer Program (Production Planning-Furniture Manufacturer) Technological data: Production of 1 table requires 5 ft pine, 2 ft oak, 3 hrs labor 1 chair requires 1 ft pine, 3 ft oak, 2 hrs labor 1 desk requires 9 ft pine, 4 ft oak, 5 hrs labor Capacities for 1 week: 1500 ft pine, 1000 ft oak, 20 employees (each works 40 hrs). Market data: profit table $12/unit chair $5/unit desk $15/unit demand 40 130 30 Goal: Find a production schedule for 1 week that will maximize the profit.
Production Planning-Furniture Manufacturer: modeling the problem as integer program The goal can be achieved by making appropriate decisions. First define decision variables: Let xtbe the number of tables to be produced; xcbe the number of chairs to be produced; xdbe the number of desks to be produced. (Always define decision variables properly!)
Production Planning-Furniture Manufacturer: modeling the problem as integer program Objective is to maximize profit: max 12xt + 5xc+ 15xd Functional Constraints capacity constraints: pine: 5xt + 1xc+ 9xd 1500 oak: 2xt + 3xc+ 4xd 1000 labor: 3xt + 2xc+ 5xd 800 market demand constraints: tables: xt 40 chairs: xc 130 desks: xd 30 Set Constraints xt , xc, xd Z+
Solutions to integer programs A solution is an assignment of values to variables. A solution can hence be thought of as an n-dimensional vector. A feasible solution is an assignment of values to variables such that all the constraints are satisfied. The objective function value of a solution is obtained by evaluating the objective function at the given point. An optimal solution (assuming maximization) is one whose objective function value is greater than or equal to that of all other feasible solutions.
Topics in this class about Integer Programming Modeling real-life situations as integer programs Applications of integer programming Solution methods (algorithms) for integer programs (optional) Using software (called AMPL) to solve integer programs
Next time: IP modeling techniques
