- Chapter 4: Discrete Optimization
- Lecture 4.1: Introduction to Discrete Optimization
- Lecture 4.2: Branch and Bound Exercize
One often encounters problems in which design variables must be selected from among a set of discrete values. Examples of discrete variables include catalog or standard sizes (I beams, motors, springs, fasteners, pipes, etc.), materials, and variables which are naturally integers such as people, gear teeth, number of shells in a heat exchanger and number of distillation trays in a distillation column. Many engineering problems are discrete in nature.
At first glance it might seem solving a discrete variable problem would be easier than a continuous problem. After all, for a variable within a given range, a set of discrete values within the range is finite whereas the number of continuous values is infinite. When searching for an optimum, it seems it would be easier to search from a finite set rather than from an infinite set.
This is not the case, however. Solving discrete problems is harder than continuous problems. This is because of the combinatorial explosion that occurs in all but the smallest problems. For example if we have two variables which can each take 10 values, we have 10*10 = 100 possibilities. If we have 10 variables that can each take 10 values, we have 10^10 possibilities. Even with the fastest computer, it would take a long time to evaluate all of these.
comments powered by Disqus