For my bachelor's thesis, I have the following problem: given a simple, undirected graph (V, E), assign a layout (meaning indices 0 to |V| - 1) to the vertices so that the difference in span length between the longest and the shortest edge is minimized.
It was suggested to me to use an integer linear program (ILP) for this optimization; being new to the topic, I have a formulation of linear equations that make sure every vertex is assigned exactly one index (I leave these out here), but have run into the problem below.
The variables that are to be solved for are $$v_i\in V$$
The constraints I wanted to use are those below; the idea is to cap all differences of span lengths between two arbitrary edges by the same variable and minimize that variable.
$v_{left}(e)$ is one end vertex of the edge $e$ and $v_{right}(e)$ is the other.
The constraints:
$$ \forall e \in E: v_{left}(e) - v_{right}(e) \le l(e) $$ $$ \forall e \in E: v_{right}(e) - v_{left}(e) \le l(e) $$ $$ \forall e, e'\in E:l(e) - l(e') \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:l(e') - l(e) \le \Delta_{e, e'} $$
These constraints could be reformulated as $$ \forall e, e'\in E:(v_{left}(e) - v_{right}(e)) - (v_{left}(e') - v_{right}(e')) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{left}(e') - v_{right}(e')) - (v_{left}(e) - v_{right}(e)) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{right}(e) - v_{left}(e)) - (v_{right}(e') - v_{left}(e')) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{right}(e') - v_{left}(e')) - (v_{right}(e) - v_{left}(e)) \le \Delta_{e, e'} $$
$$ \forall e, e'\in E:(v_{left}(e) - v_{right}(e)) - (v_{right}(e') - v_{left}(e')) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{left}(e') - v_{right}(e')) - (v_{right}(e) - v_{left}(e)) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{right}(e) - v_{left}(e)) - (v_{left}(e') - v_{right}(e')) \le \Delta_{e, e'} $$ $$ \forall e, e'\in E:(v_{right}(e') - v_{left}(e')) - (v_{left}(e) - v_{right}(e)) \le \Delta_{e, e'} $$ The minimization that then needs to be solved is $$minimize: \Delta_{e,e'}$$
All solving programs for ILPs which I came across, such as GLPK or lp_solve, only allow the objective function to solve for a linear combination of the solution variables; $\Delta_{e,e'}$ is not a solution variable but as far as I can make out needs to be a constant bounding the constraints.
One simple approach now is to check the feasability of the program iteratively for different values of $\Delta_{e,e'}$, starting with a a value I know is smaller than $\Delta_{e,e'}$ and ultimately find the smallest possible values by nested intervals. However, if possible I would like to avoid this since it means that for one graph, I may have to compute up to (I think) $\log_2 |V|$ iterations of the ILP instead of just one. Is there a way to reformulate my constraints in a way so the ILP can directly minimize $\Delta_{e,e'}$ without a need for iterative calls using nested intervals?
Side notes: For concrete LP-solving implementations I need to use Java; currently I'm writing the problem with GLPK for Java which is a Java wrapper for the GNU linear programming kit, but am considering switching to lp_solve.
If this is of relevance, I will gladly add the rest of my constraints that assign indices to vertices; I only left them out because the post was getting long anyway and they might have complicated my question unnecessarily.
