OR basics

Question 1

______ are given, known values that define the problem (don’t change).

Answer 1

Parameters

Question 2

______ are unknowns we need to decide/choose (can change).

Answer 2

Variables

Question 3

Example: Distance from A to B = 50km is a ______. Whether to use route A-B is a ______.

Answer 3

Parameter; variable

Question 4

In a shipping problem: Truck capacity = 10 tons is a ______. Amount to ship on route X = ______.

Answer 4

Parameter; variable

Question 5

An OR solution has TWO parts: ______ and ______.

Answer 5

Decision variables’ values; objective function value

Question 6

A ______ solution satisfies ALL constraints (legal/possible).

Answer 6

Feasible

Question 7

An ______ solution violates at least one constraint (impossible).

Answer 7

Infeasible

Question 8

An ______ solution is a FEASIBLE solution with the BEST objective function value

Answer 8

Optimal

Question 9

There can be multiple ______ solutions but only one best ______ value.

Answer 9

Optimal; objective function

Question 10

______ solution uses mathematical formulas/equations (exact, closed-form).

Answer 10

Analytical

Question 11

______ solution uses step-by-step procedures/algorithms (for complex problems).

Answer 11

Algorithmic

Question 12

Most real OR problems require ______ solutions because they’re too complex for analytical methods.

Answer 12

Algorithmic

Question 13

______ is human-readable algorithm description (not specific programming language).

Answer 13

Pseudocode

Question 14

Algorithmic complexity measures how ______ grows as problem size increases.

Answer 14

Computation time/work

Question 15

O(n) means ______ time, O(n²) means ______ time, O(2ⁿ) means ______ time.

Answer 15

Linear; quadratic; exponential

Question 16

______ problems have exponential time complexity - solving becomes impossible for large n.

Answer 16

NP-hard/NP-complete

Question 17

Example of hard problem: ______ with many cities.

Answer 17

Traveling Salesman Problem

Question 18

______ methods guarantee finding optimal solution (but can be slow).

Answer 18

Exact

Question 19

Examples of exact methods: ______ and ______, ______ Programming.

Answer 19

Branch and Bound; Dynamic; Integer

Question 20

______ methods find good solutions quickly (no optimality guarantee).

Answer 20

Heuristic

Question 21

______ are high-level strategies guiding search (Genetic Algorithms, Simulated Annealing)

Answer 21

Metaheuristics

Question 22

Which is faster but less reliable: exact or heuristic methods?

Answer 22

Heuristic methods (faster, but no guarantee of optimality).

Question 23

Greedy algorithm: Always choose ______ optimal choice at each step.

Answer 23

Locally (best immediate option)

Question 24

Greedy algorithms ______ reconsider previous choices.

Answer 24

Never

Question 25

Pro of greedy: ______. Con: ______.

Answer 25

Very fast and simple; doesn't always give optimal solution

Question 26

Example: Making change with coins - greedy takes largest coin first. Does this always give fewest coins?

Answer 26

Not always! Depends on coin system.

Question 27

Postoptimality analysis answers "______" questions after finding optimal solution.

Answer 27

"What if"

Question 28

Postoptimality analysis: Also called ______ analysis.

Answer 28

Sensitivity

Question 29

Why important? Real-world data has ______ and ______.

Answer 29

Uncertainty; changes

Question 30

Example question: "What if material costs increase 15%?" or "What if we add another delivery point?"

Answer 30

Correct - these are postoptimality questions.

Question 31

OR Problem-Solving Process: Step 1: ______ the problem (what to optimize, constraints).

Answer 31

Define

Question 32

OR Problem-Solving Process: Step 2: Build ______ (mathematical model with parameters, variables, objective).

Answer 32

Model

Question 33

OR Problem-Solving Process: Step 3: Choose ______ (exact, heuristic, metaheuristic).

Answer 33

Method

Question 34

OR Problem-Solving Process: Step 4: Implement ______ (pseudocode → actual code).

Answer 34

Algorithm

Question 35

OR Problem-Solving Process: Step 5: Find ______ (decision values + objective value).

Answer 35

Solution

Question 36

OR Problem-Solving Process: Step 6: ______ analysis ("what if" questions).

Answer 36

Postoptimality

Question 37

OR Problem-Solving Process: Step 7: ______ in reality.

Answer 37

Implement

Question 38

T/F: Parameters are what we decide, variables are given.

Answer 38

False! Opposite: Parameters = given, Variables = decide.

Question 39

T/F: A solution violating one constraint is infeasible.

Answer 39

True (infeasible = breaks at least one constraint).

Question 40

T/F: There can be only one optimal solution to any OR problem.

Answer 40

False! Multiple solutions can give same optimal value.

Question 41

T/F: Heuristic methods always find optimal solutions.

Answer 41

False! Heuristics find good solutions quickly, no guarantee of optimality.

Question 42

T/F: Postoptimality analysis is done BEFORE finding optimal solution.

Answer 42

False! It's done AFTER ("post") finding optimal solution.

Question 43

Designing fiber optic cable network connecting 20 cities: Type of problem? Graph type?

Answer 43

Network design problem. Undirected connected weighted graph.

Question 44

Maximizing data through internet backbone from server to users: Problem? Graph type?

Answer 44

Maximum flow problem. Directed weighted graph (capacities = bandwidth).

Question 45

UPS planning delivery routes with time windows: Problem? Solution method likely?

Answer 45

Vehicle routing problem. Likely heuristic/metaheuristic (too complex for exact).

Question 46

Construction manager scheduling tasks with dependencies: Problem? What finds critical path?

Answer 46

Project scheduling/Critical path method. Longest path algorithm.

Question 47

O(2ⁿ) complexity means problem is ______ for large n, often requiring ______ methods.

Answer 47

Hard/Intractable; heuristic/metaheuristic

Question 48

After finding optimal solution, ______ analysis tests solution robustness to changes.

Answer 48

After finding optimal solution, ______ analysis tests solution robustness to changes.