Understanding Discrete Optimization in Mathematical Modeling

Discrete Optimization is a field of applied mathematics that uses techniques from combinatorics, graph theory, linear programming, and algorithms to solve optimization problems over discrete structures. This involves creating mathematical models, defining objective functions, decision variables, and constraints to find optimal solutions. Examples include the Traveling Salesman Problem and Job Scheduling. Mathematical models in discrete optimization aim to minimize or maximize a function subject to certain constraints involving decision variables. Different types of optimization models exist, such as stochastic, deterministic, integer, continuous, linear, and nonlinear models. These models help in tackling real-world problems where decisions need to be made regarding discrete elements. By understanding the principles of discrete optimization, one can employ these techniques to address complex problems efficiently and effectively.

• Discrete Optimization
• Mathematical Modeling
• Optimization Models
• Decision Variables
• Mathematical Relationships

heloise Follow

Uploaded on Aug 02, 2024 | 0 Views

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.

Presentation Transcript

1. Math4630/5630 Discrete Modeling and Optimization

2. A schematic view of modeling/optimization process assumptions, abstraction,data, simplifications Real-world problem Mathematical model makes sense? change the model, assumptions? optimization algorithm Solution to real-world problem Solution to model interpretation

3. What is a model? Model: A schematic description of a system, theory, or phenomenon that accounts for its known or inferred properties and maybe used for further study of its characteristics. Mathematical models are abstract models describe the mathematical relationships In this class, mathematical models dealing among elements in a system with discrete optimization

4. Mathematical models in Optimization The general form of an optimization model: min or max f(x1, ,xn) subject to gi(x1, ,xn) 0(functional constraints) x1, ,xn S x1, ,xn are called decision variables In words, the goal is to find x1, ,xn that satisfy the constraints; achieve min (max) objective function value. (objective function) (set constraints)

5. Types of Optimization Models Stochastic (probabilistic information on data) Deterministic (data are certain) Discrete, Integer (S = Zn) Continuous (S = Rn) Linear Nonlinear (f and g are linear) (f and g are nonlinear)

6. What is Discrete Optimization? Discrete Optimization is a field of applied mathematics, combining techniques from combinatorics and graph theory, linear programming, theory of algorithms, to solve optimization problems over discrete structures.

7. Examples of Discrete Optimization Models: Traveling Salesman Problem (TSP) There are n cities. The salesman starts his tour from City 1, visits each of the cities exactly once, and returns to City 1. For each pair of cities i,j there is a cost cij associated with traveling from City i to City j . Goal: Find a minimum-cost tour.

8. Examples of Discrete Optimization Models: Job Scheduling There are 4 jobs that should be processed on the same machine. (Can t be processed simultaneously). Job k has processing time pk . Here is an example of a possible schedule: Job 3 Job 1 Job 4 Job 2 2 6 14 time 0 9 Goal: Find a schedule which minimizes the average completion time of the jobs.

9. Examples of Discrete Optimization Models: Shortest Path Problem In a network, we have distances on arcs ; source node s and sink node t . 3 a d 4 1 1 1 4 7 2 c s t 2 2 1 2 5 b e Goal: Find a shortest path from the source to the sink.

10. Problems that can be modeled and solved by discrete optimization techniques Scheduling Problems (production, airline, etc.) Network Design Problems Facility Location Problems Inventory management Transportation Problems

11. Problems that can be modeled and solved by discrete optimization techniques Minimum spanning tree problem Shortest path problem Maximum flow problem Min-cost flow problem Assignment Problem

12. Solution Methods for Discrete Optimization Problems Integer Programming Network Algorithms Dynamic Programming Approximation Algorithms