How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and independent of the objective function. This is due to the reason that I believe the tightness based on objective value is not informative enough and any change to the objective function might dramatically change the tightness. I believe there should be a different measure that is not affected by the change in the objective function. I am interested in both theoretical and computational answers. This is more of like a question out of curiosity.
If (for small dimensions) it is feasible to enumerate the vertices of the polyhedron of the relaxation, as well as the actual feasible set, one could try to find a vertex with the highest distance to the feasible set.
I guess this is equivalent to finding the "worst" objective function and could probably be posed as a bilevel problem with LP subproblem.
Let us say that we have two MILP formulations $A$ and $B$ on the same variables, each with the corresponding LP relaxations defining polyhedra $P_A$ and $P_B$, respectively. We say that $A$ is stronger than $B$ if every point of $P_A$ is also contained in $P_B$ whereas some points of $P_B$ are not contained in $P_A$.
For example, you may prove the first direction by showing that the constraints of $A$ imply the constraints of $B$ by Farkas lemma, and then prove the second direction by finding a point that is separated by some constraint of $A$ and not separated by any constraint of $B$.
In the case that the formulations are on different variables but we can find a mapping between how MILP solutions are represented in A and B, then we can still check if each solution in $P_A$ maps to a solution in $P_B$ and vice-versa.
Another way of looking at this is to construct randomized-rounding algorithms from both relaxations, and select the relaxation which yields a randomized rounding algorithm with the best approximation guarantee.
For instance, in max-cut we can construct an LP relaxation which provides a $0.5$ approximation ratio, or an SDP relaxation which provides a $0.878$ approximation ratio, so the SDP relaxation is a better option (provided you can solve it).
Admittedly, constructing randomized rounding methods might be more effort than its worth, but quite a bit of work has already been done in this area, so you can often get the relevant approximation ratios via a literature search.
N.b. randomized rounding algorithms are typically agnostic to the objective function used, so i'm going to claim that this counts as not using an objective function ;)
Assuming you have two closed polytopes, we can compare the volumes of the two polytopes as Rob Pratt mentioned. Unfortunately this is NP-hard as we need to identify all the vertices.
A more tractable (heuristic) metric would be to measure the distance between every constraint and its relaxation (e.g. at the midpoints or some arbitrary vertex) and get a point-system based measure of tightness. This is of course a heuristic, but it can give you some measure of what's happening and how your overall tightness improves over time. This is much more tractable than calculating the volumes as it has linear complexity with respect to the number of your constraints.