Understanding Discrete Optimization in Graph Theory
Explore the relationship between counting techniques, graph theory, and discrete optimization, with examples illustrating the transition from counting problems to optimization problems. Learn about applying optimization in scheduling and making graph models, as well as the role of graphs in discrete network optimization. Discover the ingredients of common physical networks and the importance of designing algorithms to solve discrete optimization problems effectively.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
The relationship between counting techniques/graph theory and discrete optimization Adding a goal (objective function) to a counting situation or a graph model makes it a discrete optimization problem. 2
Example: making the scheduling model an optimization problem There are 4 jobs that should be processed on the same machine. (Can t be processed simultaneously). Here is an example of a possible schedule: Job 3 Job 1 Job 4 Job 2 Original (counting) question: What is the number of all possible schedules? New (optimization) question: Find a schedule that minimizes the average completion time of the four jobs. 3
Example: making a graph model an optimization problem There are n cities. The salesman starts his tour from City 1, visits each of the cities exactly once, and returns to City 1. Original (counting) question : How many different tours are possible? New (optimization) question : Find a minimum- cost tour. 4
Graphs and discrete optimization Adding a goal (objective function) about the amount of some entity in a network makes the network model a discrete (network) optimization problem. Goal: Build a network satisfying certain requirements with minimal cost Move some entity (electricity, a consumer product, people, information) from one point to another in underlying network as efficiently as possible: Provide good service to the network users Use the network facilities efficiently 5
Ingredients of some common physical networks Application Physical analog of nodes Cities, intersections, facilities Phones, computers Physical analog of arcs Highways, airline routes Flow Transportation systems Vehicles, passengers Communication systems Cables, fiber optic links Voice messages, data Water, gas, oil Hydraulic systems Pumping stations, reservoirs Pipelines 6
How to solve discrete optimization problems? Design algorithms! The word algorithm refers to a step-by-step method for performing some action. Some examples of algorithms in everyday life: Food preparation recipes Driving directions Directions for assembling equipment Instructions for filling out income tax forms We will study algorithms for solving discrete optimization problems 7
Solution Process for discrete optimization problems Optimiz. models Abstraction, simplifications Design algorithms Solution to the model Real life situation The role of Discrete Mathematics : Show that the algorithm is correct Show that the algorithm is efficient Do careful mathematical analysis to design better algorithms 8
