Discrete Optimisation

DSC1007 Lecture 10 Introduction to Optimization

The

 Lego

 Game

 Revisited

•  We

 have

 seen

 fractional

 solutions

 for

 certain

 numbers

 of

 large

 and

  small

 bricks.

  •  What

 if

 we

 insist

 that

 the

 numbers

 of

 chairs

 and

 tables

 to

 produce

  must

 be

 whole

 numbers?

Scenario 1. Some decision variables have to be integers.

Transportation

 Problem

 Revisited

•  What

 if

 there

 is

 a

 requirement

 that

 each

 retail

 outlet

 can

 only

 be

  supplied

 by

 one

 plant?

  •  What

 if

 Outlet

 A

 and

 Outlet

 B

 cannot

 be

 supplied

 by

 the

 same

 plant?

Scenario 2. There is a need to make choice or consider some logical constraints.

Computer

 Production

 Problem

 Revisited

Scenario 3. There is a need to convert some nonlinear constraints into linear constraints.

Discrete

 Optimization

•  Discrete

 Optimization

 is

 an

 optimization

 problem

 in

 which

  some

 (or

 all)

 of

 the

 decision

 variables

 must

 be

 integer-­‐valued

  •  Examples:

–  Integer

 variables:

 Number

 of

 workers,

 cars,

 machines,

 etc.

  –  Binary

 variables:

 YES/NO

 decisions

  –  Mixed

 Integer

 Program

 (MIP):

 Some

 variables

 are

 integer-­‐valued

•  Why

 do

 we

 need

 discrete

 optimization?

–  A

 very

 powerful

 modeling

 method!

  –  CPLEX

 reports

 that

 >

 90%

 of

 their

 clients’

 problems

 are

 MIP’s

  –  Various

 applications:

 Sudoku

Discrete

 Optimization

•  Taxonomy

  –  Integer

 Optimization/Programming

 (IP):

 Linear

optimization

 with

 all...