multi-objective-optimization

Multi-Objective Optimization

You are an expert in multi-objective combinatorial optimization. This skill covers the full a-posteriori workflow — define Pareto optimality, generate the nondominated front exactly (weighted sum, epsilon-constraint with Gurobi) or approximately (NSGA-II, from scratch and via pymoo), measure approximation quality (hypervolume, IGD/IGD+), and support the final single-solution decision. Use the protocols below to pick the right method for the objective count, problem class, and budget, and to report results that survive peer review.

Initial Assessment

Establish these facts before writing any model or algorithm:

• How many objectives M, and are they genuinely conflicting? Sample feasible solutions and check pairwise objective correlation. Two strongly positively correlated objectives collapse to (nearly) one; optimizing both separately wastes the entire multi-objective apparatus.
• What does the decision maker actually need? One solution under known priorities (a-priori articulation), the whole trade-off curve to choose from afterwards (a-posteriori), or an interactive loop? This single question selects most of the method.
• Is the model an explicit MILP or a black-box evaluation? Epsilon-constraint needs a solvable scalarized model; if each scalarized MILP solves in seconds-to-minutes, an exact bi-objective front is usually affordable. Black-box or very large models push you to evolutionary methods.
• Are the objective functions integer-valued? Integer objectives let the epsilon-constraint sweep step by exactly 1 and terminate with the provably complete front. Continuous objectives need a grid density decision and yield a representation, not the full front.
• Estimate the nondominated set size. Bi-objective integer programs can have very many nondominated points (growing exponentially in the worst case — see Ehrgott (2005), Multicriteria Optimization). The cost of an exact sweep is one MILP per front point; budget accordingly.
• Objective scales and units. Cost in euros vs CO2 in tons differ by orders of magnitude. Every distance-based mechanism (crowding, hypervolume, IGD) silently breaks without normalization. Fix ideal/nadir estimates and record them.
• Hard constraints vs objectives. A "constraint" with a negotiable bound is often better treated as an objective (and vice versa). Epsilon-constraint makes this conversion explicit; confirm with the stakeholder which quantities are negotiable.
• Solver availability and license. Gurobi for the exact scalarization loops here; for license-free settings the same loops run on HiGHS/SCIP with longer runtimes.
• Evaluation budget for evolutionary methods. Population size N and generations G give N×G evaluations. The front cannot hold more points than the population; size N at 2-5× the front cardinality you intend to report.
• Comparison protocol. If two or more algorithms (or parameter settings) will be compared, fix now: instances, seeds per algorithm (10-30), identical normalization bounds, one shared hypervolume reference point, and a reference front (exact if available, else pooled best-known).
• Reproducibility. Every stochastic component takes an explicit seed (np.random.default_rng(seed)); every exact solve logs status, gap, and runtime per epsilon grid point.
• Decision-support endgame. Plan how the front turns into a decision: knee points, pseudo-weights, or a stakeholder workshop. A 200-point front without a selection protocol is not a deliverable.