Choose an optimization method after the formulation is stable. The variables, constraints, uncertainty, instance size, and required guarantees determine which methods are credible candidates.
Start with Formulating an optimization problem if those elements are still changing.
Describe the problem structure
Record the properties that affect method choice:
- Variables: continuous, integer, binary, or mixed.
- Objective and constraints: linear, nonlinear, convex, or nonconvex.
- Information: deterministic, stochastic, scenario-based, or online.
- Scale: variables, constraints, sparsity, instance size, and solve frequency.
- Evaluation: exact values, noisy simulation output, or expensive experiments.
Convex models often require more effort in formulation than in solver choice. Once the model is expressed as a convex optimization problem, established methods can solve it reliably under their stated assumptions (Boyd & Vandenberghe, 2004). Mixed-integer and nonconvex problems usually require a more explicit trade-off between guarantees, runtime, and scale.
Decide which guarantee you need
Exact methods can provide an optimal solution or a bound that quantifies the remaining gap. Their runtime may grow quickly with instance size. Approximate methods can handle larger or more complex cases, although their solutions need careful empirical evaluation.
Use an exact method when the model is tractable and the decision requires a certificate of optimality. Use an approximate method when a timely, high-quality solution is more useful than a proof. Hybrid approaches are also common. An exact model can validate small cases while a heuristic handles realistic ones.
Report solver bounds, gaps, time limits, and termination conditions whenever they are available.
Match the method to the available information
Gradient-based methods are efficient when the objective and constraints are smooth and reliable derivatives are available. Derivative-free methods are relevant when the evaluation comes from a simulation, contains noise, or has no usable derivative.
For nonlinear optimization, state the differentiability assumptions, initialization, tolerances, and convergence criteria. Local methods can return different solutions from different starting points (Boyd & Vandenberghe, 2004).
Dynamic and online problems may require a policy rather than one fixed solution.
Policy or decision rule
A policy maps the observed state to an action. A dynamic routing policy may decide whether to accept a new request, where to insert it, or whether a vehicle should wait or reposition.
Define the state, available actions, and decision time. Then state which future information the policy can use. A policy evaluated with information unavailable in practice has an unfair advantage.
Simple decision rules remain useful. A nearest-neighbor rule, dispatch rule, or company planning procedure can expose errors and provide a reference for more complex methods.
Baseline
A baseline is the method or performance level used for comparison. Choose a baseline that represents a credible alternative to your method. Depending on the thesis, that may be:
- the company’s current procedure;
- a simple constructive heuristic;
- a standard solver formulation;
- a published method for the same problem class.
Include a simple baseline even when a stronger published method is available. The simple comparison shows whether the extra complexity produces a meaningful gain.
SOTA method
SOTA refers to the strongest published or publicly available methods under a comparable protocol. The label depends on the instance set, time limit, hardware, objective, constraints, and publication date.
Name the exact method and evidence. Avoid calling an approach SOTA only because it is recent or uses a fashionable technique. A fair comparison may require the authors’ code, reported parameter settings, and the original benchmark data.
Best-known solution
A best-known solution (BKS) is the strongest reported objective value for one instance. The value may be optimal, although that status requires a proof or a matching bound.
Report whether the reference value is proven optimal or simply the best result found so far. Verify that the problem definition matches your implementation before calculating a gap.
Choose among heuristics
Start with the representation and move operators. They define which solutions the algorithm can construct and how it can move between them. A named metaheuristic cannot compensate for a representation that excludes useful solutions or neighborhoods that rarely improve them.
Select the control mechanism based on a specific need:
- Simulated annealing permits controlled worsening moves.
- Tabu search uses memory to limit cycling and guide intensification.
- Variable neighborhood search moves among neighborhoods of different sizes.
- Iterated local search repeatedly perturbs and improves a solution.
Many newer methods change the terminology while retaining familiar search mechanics. Justify the mechanics and supporting evidence, not the source metaphor (Sørensen, 2013).
Compare a short list
When several methods remain plausible, compare 2 to 4 candidates using the same representation, instance set, budget, and stopping rule. Use training instances for configuration and reserve separate instances for final testing.
Racing and configuration tools such as irace can allocate computation across candidates and parameter settings (López-Ibáñez, Dubois-Lacoste, Pérez Cáceres, Birattari, & Stützle, 2016). Freeze the selected configuration before evaluating the test set.
Explain the choice in the thesis
The methods chapter should let a reader reconstruct the decision:
- Describe the problem structure and computational requirements.
- Identify the realistic alternatives and the evidence supporting them.
- Explain why the selected method fits the model, data, and available time.
- State the baseline, evaluation protocol, and success criteria.
Continue with Benchmarking optimization methods to design the experiments. See Method versus methodology for the distinction between the chosen procedure and the reasoning behind it.