Discrete Optimization

Discrete Optimization
Outline
• What is discrete optimization?
• Problem formulation for linear programs
• Approximate solution techniques
• Exaction solution techniques
• Dynamic programming
• Ant-Colony optimization
2
Discrete Optimization
• Solving problems with variables that are discrete instead of continuous
• Examples?
• The set of possible discrete values can be finite or infinite
3
Integer Programs
• A linear program with integral constraints
• A mixed integer program contains both continuous and integral

constraints
• Can be solved exactly with the simplex algorithm under strict
conditions on A, b, and c
4
Rounding
• A common approach is to relax the discrete value constraint, solve the
problem in the continuous domain, then round the continuous result to
the nearest discrete value
• Known as solving the "relaxed" LP
5
Rounding
Rounding to infeasible point Rounding to suboptimal point
• If A is integral, the error of a rounded solution can be bounded

6
Cutting Planes
• The cutting plane method solves the relaxed LP, adds linear
constraints, then repeats until the solution is exact
• Solves mixed integer programs exactly
• The linear constraints are chosen such that all discrete points are still
feasible, but the relaxed solution is not
7
Cutting Planes
• Recall that we can partition a vertex as
• Using the method of Gomory's cut, we can add an

additional inequality constraint for each nonintegral dimension
with
• This "cuts out" the relaxed solution
8
Branch and Bound
• Algorithm for efficiently searching the very large set of solution
possibilities
• “Branching” is dividing the domain into sections
• “Bounding” is keeping track of the best solution so far and rejecting
regions that cannot improve upon it
• In the worst case, the algorithm has to search all possibilities but in
practice it works very well. Combined with cutting planes, this
approach forms the basis of many commercial MIP solvers.
9
Branching
10
Bounding
11
Bounding
LP-1
LP-2 LP-3
Infeasible
LP-4 LP-5
12
Dynamic Programming
• Applied to problems with optimal substructure and overlapping
subproblems
• Optimal substructure means an optimal solution can be
constructed from optimal solutions to its subproblems
• Overlapping subproblems means solving each subproblem
separately requires repeating certain operations
• Dynamic programming begins with desired problem and recurses
down to smaller and smaller subproblems, retrieving the value of
previously solved problems as necessary
13
Dynamic Programming
• Example – Optimal path
• Others?
14
Example 1: Padovan Sequence
15
16
17
Example 2: Knapsack Problem
• Trying to pack some number of items into a backpack

• Limited space in the backpack
• Each item has a specified value and size
• What is the best subset of items to include?
18
19
• Consider the ith item. You can either use it or not.
• If you use it, then the value of your knapsack will be
• If you don't use it then the value of your knapsack will be
20
21
22
Ant Colony Optimization
• A stochastic method for optimizing paths through graphs
• Named after ant behavior of leaving pheromone trails
• If a wandering ant successfully arrives at the destination, their
pheromone gets added to the path they took
• Successful paths are reinforced, while unpopular trails fade over time
• When expressed mathematically, ant colony optimization has been
used to find near-optimal solutions to hard problems such as the
traveling salesman problem
23
• Edge attractiveness
• Probability of edge transition
• Ants deposit pheromones after finding a successful path. The amount

of pheromone deposited depends on value of path found
24
25
Summary
• Discrete optimization problems require that the design variables
be chosen from discrete sets.
• Relaxation, in which the continuous version of the discrete
problem is solved, is by itself an unreliable technique for finding
an optimal discrete solution but is central to more sophisticated
algorithms.
• Many combinatorial optimization problems can be framed as an
integer program, which is a linear program with integer
constraints.
26
Summary
• Both the cutting plane and branch and bound methods can be used to
solve integer programs efficiently and exactly. The branch and
bound method is quite general and can be applied to a wide variety
of discrete optimization problems.
• Dynamic programming is a powerful technique that exploits optimal
overlapping substructure in some problems.
• Ant colony optimization is a nature-inspired algorithm that can be
used for optimizing paths in graphs.
27

Discrete Optimization

Uploaded by

Copyright:

Available Formats

Discrete Optimization

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Optimization

Uploaded by

Copyright:

Available Formats

Discrete Optimization

• The set of possible discrete values can be finite or infinite

• A mixed integer program contains both continuous and integral

• If A is integral, the error of a rounded solution can be bounded

• Using the method of Gomory's cut, we can add an

• This "cuts out" the relaxed solution

• Trying to pack some number of items into a backpack

• If you don't use it then the value of your knapsack will be

• Probability of edge transition

• Ants deposit pheromones after finding a successful path. The amount

You might also like