An optimization formulation states which decisions can change, what a good outcome means, and which rules every acceptable solution must satisfy. A clear formulation lets another researcher check whether the mathematical problem matches the operational problem.
Write the formulation before selecting an algorithm. The algorithm depends on the structure of the variables, objective, constraints, data, and uncertainty.
flowchart LR C[Operational context] --> I[Instance and inputs] I --> D[Decision variables] D --> O[Objective] D --> R[Constraints] O --> V[Problem variant] R --> V V --> U[Uncertainty] U --> M[Method and evaluation]
Problem class and problem instance
A problem class defines a family of related problems. The capacitated vehicle routing problem, for example, asks how a fleet should serve customers without exceeding vehicle capacity. A problem instance supplies all data for one case in that family (Deutsche Nationalbibliothek, n.d.).
One vehicle-routing instance may contain 100 customer locations, their demands, a depot, 12 vehicles, a capacity of 80 units, and a travel-time matrix. Changing the customer locations produces a new instance while the problem class stays the same.
State both levels in the thesis:
- Define the general problem class and its assumptions.
- Describe how each experimental instance is created or obtained.
- Identify which instance characteristics may affect difficulty.
- Record any preprocessing that changes the original data.
Readers need the distinction because a method can perform well on one set of instances and poorly on another.
Inputs, parameters, and decisions
Inputs describe the case you receive. Parameters are fixed values used in the model. Decision variables describe the choices the model makes.
For a vehicle-routing problem, customer demand and vehicle capacity are inputs. A binary variable \(x_{ij}\) may state whether a vehicle travels directly from location \(i\) to location \(j\). The solver changes \(x_{ij}\) while the demand and capacity stay fixed.
Use a notation table that separates these categories. For each item, give the symbol, units, source, domain, and interpretation. Include time units and reference periods. A parameter called “cost” remains ambiguous until the reader knows whether it means euros per kilometer, euros per route, or a dimensionless penalty.
Do not treat an operational choice as fixed data. If a planner can choose the number of temporary workers, that quantity belongs among the decision variables unless the research scope explicitly fixes it.
Objective function
The objective function assigns a value to every feasible solution and defines which direction is better (Wikipedia contributors, n.d.). A model may minimize cost, distance, lateness, emissions, or risk. It may maximize service, throughput, profit, or coverage.
For a routing problem, a simple distance objective is
\[ \min \sum_{i \in N}\sum_{j \in N} d_{ij}x_{ij}, \]
where \(d_{ij}\) is the distance from \(i\) to \(j\). The equation is useful only when total distance matches the decision that stakeholders care about.
Many projects have several objectives. A distribution network may need low cost, high service, and lower emissions. State how the model handles the trade-off. Common choices include a weighted objective, a lexicographic order, an epsilon-constraint formulation, or a Pareto analysis.
Document each weight and penalty. Explain its units, source, and effect on the solution. Test whether reasonable changes alter the conclusion.
Constraints
Constraints define the feasible solutions. They can express physical limits, business rules, logical relationships, service requirements, and accounting identities (IBM, n.d.).
A vehicle-routing formulation commonly requires that:
- every required customer is served;
- each route starts and ends at the correct depot;
- the load on a route stays within vehicle capacity;
- arrival and service times respect time windows.
Name each constraint group and explain its operational meaning before giving the equations. A reader should understand the rule without first decoding the notation.
Separate hard constraints from soft constraints. A hard constraint must always hold. A soft constraint may be violated at a stated penalty. If a company rule has exceptions in practice, a soft formulation may describe the operation more accurately.
Test the constraints on very small instances. Construct one feasible case, one case that should be infeasible, and cases that isolate each important rule. These tests catch missing links, incorrect indices, and unintended solutions before the full experiment begins.
Variants
A variant changes the definition of a base problem through an objective, constraint, decision, or information structure. Vehicle-routing variants may add capacities, time windows, pickups and deliveries, several depots, electric vehicles, or uncertain requests (ScienceDirect Topics, n.d.).
Give the variant a precise name only when your formulation matches the accepted definition. If the company problem combines several features, list them explicitly. Then state which established formulation is closest and which elements you changed.
A new constraint can change computational difficulty and make published results incomparable. Explain those consequences when you adapt a benchmark or method.
Randomness and information
Randomness can enter through the operation or the solution method. Travel time, demand, cancellations, and new requests may be uncertain. A heuristic may also use random construction, mutation, sampling, or tie-breaking.
Define when each uncertain quantity becomes known. A model that sees tomorrow’s requests before making today’s decisions has more information than an online planner. The comparison becomes unfair if the company baseline had less information.
For operational uncertainty, record:
- the probability distribution or scenario-generation procedure;
- the data used to estimate it;
- the decision stages and information available at each stage;
- the outcome measures used across scenarios.
For algorithmic randomness, report several independent runs, the seeds, and the distribution of results. A single best run does not describe typical performance.
A compact worked example
Suppose a warehouse must assign 60 customer orders to picking batches before 2 daily departures.
| Formulation element | Warehouse batching example |
|---|---|
| Instance | Orders released on one day, item locations, picker capacity, and departure deadlines |
| Inputs | Order lines, walking times, cart capacity, and release times |
| Decisions | Which orders share a batch and when each batch is released |
| Objective | Minimize expected picking time and late orders |
| Constraints | Capacity, order integrity, release time, and departure deadline rules |
| Variant | Online batching with 2 delivery deadlines |
| Uncertainty | Future order arrivals and picking-time variation |
The example makes the modeling boundary visible. Congestion, picker breaks, and equipment failures remain outside the model unless the research question needs them.
Formulation check
Before implementation, confirm that you can answer the following questions:
- Which operational decision does each decision variable represent?
- Does the objective measure the outcome named in the research question?
- Can each constraint be traced to a physical rule, policy, or assumption?
- Which information is available when each decision is made?
- Which small tests show that the formulation behaves as intended?
- Which claims remain valid when important parameters change?
Continue with Choosing optimization methods after the formulation is stable. Use Benchmarking optimization methods to design the comparison and final evaluation.