# A lexicographic objective function

I am trying to solve a multi-objective vehicle routing problem, I want to implement a lexicographic objective function, I have already defined a function for each objective. if someone has an idea of how can implement the lexicographic function. (PS. the code is written in python).

• Are you using Gurobi/CPLEX? Sep 29 at 20:00
• yes I have the result of the CPLEX, but I want to compare it with a heuristic I have implemented Sep 29 at 20:06
• To clarify: you are asking how to implement the objective function in your heuristic, rather than how to implement it using CPLEX, correct? Does you heuristic require a single number as objective value, or is it sufficient to provide a function that lets the heuristic compare two solutions and see which is preferable? Sep 29 at 21:08
• For the first one correct, for the second yes the heuristic requires a single value but it must have the same representation of the lexicographic function of CPLEX. I need to compare the value of the solution given by the CPLEX and the one given by the heuristic. Sep 29 at 21:41

## 1 Answer

Let $$f(x)=(f_1(x),f_2(x),\dots,f_n(x))$$ be a lexicographic objective function, where $$f_1(x)$$ is more important than $$f_2(x)$$ which in turn is more important than $$f_3(x)$$, etc. I'll assume you are solving a minimization problem. In a mathematical programming solver, such an objective function could be easily implemented as follows. First find the solution $$x$$, subject to $$x\in X$$ which scores best on objective $$f_1$$ (here $$X$$ is the set of feasible solutions). Next, find the solution $$x'$$ that scores best on objective f_2, subject to $$x'\in X$$ and $$f_1(x')\leq f_1(x)$$. Continue this iterative procedure for every objective function, in descending order of the importance of each objective function.

To implement a heuristic with a lexicographic objective function, there exist different solutions.

• Assign a weight $$M_i$$ to each objective function $$i=1,2,\dots,n$$, with $$M_1\gg M_2 \gg \dots \gg M_n$$.You can than solve $$f(x)=M_1f_1(x)+M_2f_2(x)+\dots+M_nf_n(x)$$. In other words, you simply combine all objective functions into a single weighted objective function.

An example in the context of a vehicle routing problem: $$f_1=$$ the total number of vehicles needed, $$f_2=$$ total driving distance of the vehicles. You could minimize $$M_1f_1(x)+f_2(x)$$, where $$M_1$$ is an upper bound on the total driving distance (e.g. the sum of the 2 longest edges out of each customer). Alternatively, if you don't want to mimic an exact lexicographic function, you could simply set $$M_i=2^{n-i}$$ or $$M_i=10^{n-i}$$. Note that this kind of objective function has a major disadvantage: many common heuristics, including for instance Simulated Annealing, perform a lot better if the objective function is smooth, i.e. minor changes in the solution result in minor changes in the objective. With this multi-objective approach, a minor change in the solution might incur a big change in the objective function due to the different weights.

• Another approach is to implement the Lexicographic property directly into your heuristic: first search for a solution $$x$$ which scores best on $$f_1$$. Next, search for the solution $$x'$$ which scores best on $$f_2$$, while only accepting moves to solutions that have the same score on $$f_1$$ as $$x$$.

It is likely that this approach will get you stuck in a local optima quickly.

References to other approaches can be found in this slide deck.