LP dependent on the ordering of the data

Question

This is a rather simple question. Can a solution to a linear programming problem be dependent on the order in which the data is read/presented/stored?

I know, that the time it takes to solve the problem can depend heavily on the ordering of the data, and if there a multiple optimal solutions to an LP, the ordering of the data can result in the algorithm finding another optimal solution.

But, can the solution itself and the corresponding optimal objective function value change depending on the ordering of the data? Does there exist models which are "data sensitive" in this respect?

Answer 1

I know it's a bit of a stretch, but in some sense the answer is yes. I apologize in advance for the self-promotion as the following is based on a paper I have co-authored. Also I apologize for the rather lengthy reply.

---

The Capacitated Vehicle Routing Problem (CVRP) can be defined as follows . Let $G = (V, E)$ be an undirected graph with node set $V = \{0, . . . , n\}$ and edge set $E$. Node 0 represents a depot, whereas each of the nodes in $V_c = {1, . . . , n}$ represents a customer. The symmetric cost of travel between nodes $i$ and $j$ is denoted by $c_{ij}$. A number $K$ of identical vehicles, each of capacity $Q > 0$, is available. Each customer $i \in V_c$, has an integer demand $q_i$ ($q_0=0$). Each customer must be served by a single vehicle and and the vehicles' capacities must be respected. The task is to find a set of vehicle routes of minimum cost, where each vehicle used leaves from and returns to the depot. In the paper, we propose a formulation of the CVRP based on decomposing each route into two paths leaving the depot and meeting up in the customer having the largest index on the route. To do so, we introduce the following sets of variables:

• For each $(i,j)\in A$, $x_{ij} = 1$ if a vehicle travels along arc $(i,j)$, otherwise $x_{ij} = 0$.
• For each $(i,j)\in \in A$, if a vehicle travels along arc $(i,j)$, then $f_{ij}$ denotes the total quantity delivered on the path when the vehicle leaves vertex $i$, otherwise $f_{ij} = 0$.
• For each $i\in V_c\setminus\{n\}$, the variable $u_i$ denotes the largest customer index visited on the path from the depot to and including customer $i$. $u_n=n$.
• For each $i\in V_c$, the variable $p_i$ denotes whether or not node $i$ is the customer with the largest index on a route. $p_n=1$.
• For each $i\in V_c$, if $p_i = 1$, then $t_i$ represents the total demand on the route which services node $i$, otherwise $t_i = 0$.

In the paper we propose the following formulation of CVRP \begin{align} \min & \sum_{(i,j) \in A} c_{ij} x_{ij} \label{eq:our_obj} & & & \\ \text{s.t.:} & x(\delta^+(i)) + p_i = 1 & & \forall i \in V_c & \\ & x(\delta^-(i)) - p_i = 1 & & \forall i \in V_c & \\ & t_i + f(\delta^+(i)) = f(\delta^-(i)) + q_i & & \forall i \in V_c & \\ & q_i x_{ij} \leq f_{ij} \leq (Q-q_j) x_{ij} & & \forall (i,j) \in A_c & \\ & q_i p_i \leq t_i \leq Q p_i & & \forall i \in V_c & \\ & x(\delta^+(0)) = 2K & & & \\ & \sum_{i \in V_c} p_i = K & & & \\ & i \leq u_i \leq i p_i + (n-1) (1-p_i) & & \forall i \in V_c \setminus \{n\} & \\ & u_i-u_j +(n-j-1)x_{ij} + (n-\max\{i,j\}-1) x_{ji} \leq n-j-1 & & \forall i,j \in V_c \setminus \{n\}, \ i \not= j & \\ &\sum_{i \in S_j} p_i \geq \bigl \lceil \sum_{i \in S_j} q_i / Q \bigr \rceil &&\forall j=1,\ldots,n&\\ & x_{ij} \in \{0,1\} & & \forall (i,j) \in A_c & \\ & x_{0j} \in \{0,1,2\} & & \forall j \in V_c & \\ & p_{i} \in \{0,1\} & & \forall i \in V_c & \end{align} For a detailed description of the constraint sets, please see the paper.

Now, when we did the research, the goal was to get rid of the symmetry that comes from the fact that for the symmetric CVRP, it does not matter in which direction you traverse a route. As a by-product of this, we noticed, that the LP relaxation of this formulation was very dependent on the ordering of the customers. To illustrate this, consider the following small example with 6 customers:

The number of vehicles is set to $K=2$, the vehicle capacity to $Q=47$, and the $c_{ij}$'s are the rounded Euclidean distances between the coordinates. If one solves the LP-relaxation of the above program, the optimal objective function value is $z^*=54.786$. If, on the other hand, one sorts the customers according to non-increasing distance to the depot, the optimal objective function value of the LP relaxation is $z^*=49.987$. Obviously, the optimal solution value of the IP is independent of the ordering and is in this case equal to 61. We noticed that sorting the customers in non-decreasing distance to the depot worked well in general, however we were not able to come up with a provable optimal ordering in general.

Answer 2

In theory no. In practice this can happen, because everything is done in floating point arithmetic. (See also this post https://www.gurobi.com/documentation/9.0/refman/tolerances_and_ill_conditi.html)

If this happens i would look at the optimality certificates of the solutions. They might mention a large violation, even though the solver has terminated with this solution.

Answer 3

I have faced a similar issue. The above answer is up to the point but in addition to it, read the answer by Prof. Marco (link). The paper cited by him (pdf) helped me a lot in understanding the performance variability phenomenon. While solving MIPs, various algorithmic choices are influenced by the ordering of the variables, constraints in the input MIP model, leading to alternate optimal solutions. These solutions could have the same or different objective values depending upon the tolerance limit of floating-point arithmetics set by you but definitely the corresponding variables would be different. Not fixing the ordering of variables will also lead to variations in performance when the same code is run again on the same or a different machine.