Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings
Alexander Dobler Michael Jünger Paul J. Jünger Julian Meffert Petra Mutzel Martin Nöllenburg


Theoretical modelling of the exceptional GRB 221009A afterglow
    [
    September 9, 2024
==============================================================



§ ABSTRACT 
Storyline drawings are a popular visualization of interactions of a set of characters over time, e.g., to show participants of scenes in a book or movie. 
Characters are represented as x-monotone curves that converge vertically for interactions and diverge otherwise. 
Combinatorially, the task of computing storyline drawings reduces to finding a sequence of permutations of the character curves for the different time points, with the primary objective being crossing minimization of the induced character trajectories.
In this paper, we revisit exact integer linear programming (ILP) approaches for this -hard problem. 
By enriching previous formulations with additional problem-specific insights and new heuristics, we obtain exact solutions for an extended new benchmark set of larger and more complex instances than had been used before. 
Our experiments show that 

our enriched formulations lead to better performing algorithms when compared to state-of-the–art modelling techniques. 
In particular, our best algorithms are on average 2.6–3.2 times faster than the state-of-the-art and succeed in solving complex instances that could not be solved before within the given time limit. Further, we show in an ablation study that our enrichment components contribute considerably to the performance of the new ILP formulation. 









§ INTRODUCTION
 













Storyline drawings are a well-studied visualization style for complex event-based temporal interaction data and have been popularized by the xkcd comic “Movie Narrative Charts” in 2009 <cit.>.
They show a set of characters, e.g., from the plot of a movie or book, and how they interact or co-occur in a sequence of events over time, e.g., by participating in the same scene or conversation of the evolving story.
A storyline drawing is a two-dimensional diagram, where the x-axis represents time and the y-dimension is used for the vertical grouping of characters according to their interaction sequence. The exact temporal distance of interactions is usually not depicted, only their order.
Each character is represented as an x-monotone curve, and interactions are represented by vertically grouping the curves of the participating characters at the x-coordinate corresponding to the interaction time.
Characters that are not participating in an interaction at any specific point in time are vertically separated from each other.
<Ref> shows an example of a storyline drawing.
Due to their popularity and the intuitive data encoding, they are well suited for visual storytelling and have since been used as visual metaphors for representing a variety of different event-based data sets beyond the original book and movie plots <cit.>, e.g., for software projects <cit.>, newspaper articles <cit.>, political debates on social media <cit.>, visual summaries of meeting contents <cit.>, scientific collaborations <cit.>, sports commentary <cit.>, and gameplay data <cit.>.

There is one main degree of freedom when computing and optimizing storyline drawings: the (vertical) linear order and positioning of the characters at each discrete time steps. 
The only hard constraint is that all characters participating in the same interaction must be consecutive as a group.
This degree of freedom can thus be used to minimize the number of crossings between character curves, their wiggles (i.e. the amount of vertical movement of character lines in the visualization), and any excessive white space in the diagram, which are the three major objectives that have been identified for computing storyline drawings <cit.>.
While the number of crossings is determined purely combinatorially by the sequence of character permutations, wiggles and white space depend on the actual y-coordinates assigned to each character curve at each point in time.

In this paper, our interest is the combinatorial crossing minimization problem. 
It is the primary objective in practical storyline optimization pipelines <cit.>, where it forms the input to the subsequent steps of reducing wiggles and white space while maintaining the character order.
Additionally, crossing minimization is one of the most fundamental graph drawing problems <cit.> and it is well known that graph drawings with fewer crossings increase readability <cit.>. 
Unfortunately, crossing minimization in storyline drawings is an -hard problem <cit.> and hence practical approaches for storyline visualization usually resort to 
heuristics, even though they cannot guarantee optimal solutions.  

We consider the crossing minimization problem from the opposite side and revisit exact integer linear programming (ILP) approaches <cit.> for computing provably optimal solutions. Such approaches often lead to practical exact algorithms.
Our goal is to improve on the runtime performance of such exact methods by enriching the models with both new problem-specific insights and better heuristics. 
Faster exact algorithms for crossing minimization in storyline drawings are practically relevant for two reasons: firstly, solving moderately sized instances to optimality within a few seconds provides a strictly better alternative to commonly used suboptimal heuristics, and secondly, knowing optimal solutions for a large set of representative benchmark instances (even if their computations take several minutes or up to a few hours) is a prerequisite for any thorough experimental study on the performance of non-exact crossing minimization heuristics and for generating crossing-minimum stimuli in user experiments.




    Related Work.

Tanahashi and Ma <cit.> introduced storyline drawings as an information visualization problem, provided the first visual encoding model, and defined the above-mentioned optimization criteria (crossings, wiggles, white space). 
They suggested a genetic algorithm to compute storyline drawings. 
Ogawa and Ma <cit.> used a greedy algorithm to compute storylines to depict software evolution. Due to slow computation times of previous methods, Liu et al. <cit.> split the layout process into a pipeline of several subproblems ordered by importance, the first one being crossing minimization. 
They solved the character line ordering by an iterated application of a constrained barycenter algorithm, a classic heuristic for multi-layer crossing minimization <cit.>. 
Their results were obtained in less than a second and had fewer crossings than those computed by the genetic algorithm <cit.>, which took more than a day to compute on some of the same instances. 
Tanahashi et al. <cit.> enhanced previous methods to take into account streaming data and apply a simple sequential left-to-right sorting heuristic. 
Recent practical works on storyline drawings focus on other aspects, such as an interactive editor <cit.> or a mixed-initiative system including a reinforcement learning AI component <cit.>; both these systems apply a two-layer crossing minimization heuristic <cit.>.  

Several authors focused on the combinatorial crossing minimization problem and its complexity. 
Kostitsyna et al. <cit.> observed that the -hardness of the problem follows from a similar bipartite crossing minimization problem <cit.> and proved fixed-parameter tractability when the number of characters is bounded by a parameter k. 
Gronemann et al. <cit.> were the first to model the problem as a special type of tree-constrained multi-layer crossing minimization problem. They implemented an exact branch-and-cut approach that exploits the equivalence of the quadratic unconstrained 0/1-optimization problem with the maximum cut problem in a graph.
They managed to solve many instances with up to 20 characters and 50 interactions optimally within a few seconds.
Van Dijk et al. <cit.> proposed block-crossing minimization in storyline drawings, which counts grid-like blocks of crossings rather than individual crossings. 
They showed -hardness and proposed greedy heuristics, a fixed-parameter tractable algorithm, and an approximation algorithm. 
In a follow-up work, van Dijk et al. <cit.> implemented and experimentally evaluated an exact approach for the block crossing minimization problem using SAT solving.
A different variation of storylines was studied by Di Giacomo et al. <cit.>, who considered ubiquitous characters as x-monotone trees with multiple branches, enabling characters to participate in multiple simultaneous interactions; they solved the crossing minimization aspect using an adaptation of the previous SAT model <cit.>.
Dobler et al. <cit.> consider time interval storylines, where additionally to the order of characters, the order of time steps in so-called time-intervals can be permuted.

The problem is also similar to crossing minimization in layered graph drawing, which was introduced by Sugiyama et al. <cit.>. The problem is to draw a graph with its vertices on multiple parallel lines while minimizing crossings. A notable difference to storyline crossing minimization is that vertices can have arbitrary degree and that edges can span more than one layer. For a survey of algorithms and techniques in layered graph drawing, we refer to Healy and Nikolov <cit.>.











    Contributions.



The contributions of this paper are the following: 

    
  * We identify structural properties of storyline drawings and prove that there exist crossing-minimum drawings satisfying them, reducing the search space of feasible solutions.
    
  * We propose a new ILP formulation exploiting these structural insights in order to (i) significantly reduce the number of required constraints and (ii) apply symmetry breaking constraints to strengthen the ILP model. 
    
  * We introduce several new heuristics that support the exact solver, either as initial heuristics to improve branch-and-bound pruning or for deriving integral solutions from fractional ones during the incremental ILP solving process. 
    
  * We have compiled a new benchmark set of storyline instances, including those of earlier studies, as well as several challenging new ones.
    
    
    
  * We have conducted a detailed experimental evaluation of our new ILP model using the above benchmark set. We compare its ability to solve instances with state-of-the-art ILP models. Moreover, in an ablation study, we show that our further enhancements (e.g., adding symmetry breaking constraints and novel heuristics) contributes considerably to the performance of both the new and several state-of-the-art ILP formulations.
    
  * We show that our ILP models are able to solve previously unsolved instances from the literature and obtain a speedup of 2.6–3.2 compared to the state of the art.

Data sets, source code, evaluation, and a visualization software are available on https://doi.org/10.17605/OSF.IO/3BUA2.
































































    


§ PRELIMINARIES



    Permutations.

Given a set X={x_1,…,x_n}, a permutation π is a linear order of its elements, or equivalently, a bijective mapping from {1,2,…,|X|} to X. For x,x'∈ X we write x≺_πx' if x comes before x' in π.
For Y⊆ X, π[Y] is the permutation π restricted to Y, formally, for y,y'∈ Y,  y≺_π[Y]y' if and only if y≺_πy'. For two permutations π,ϕ of two sets X and Y with X∩ Y=∅, we denote by π⋆ϕ their concatenation. Given two permutations π,π' of the same set X, the inversions between π and π' is the number of pairs x,x'∈ X such that π^-1(x)<π^-1(x') and π'^-1(x)>π^-1(x').



    Problem input.


A storyline instance consists of a 4-tuple (T,𝒞,ℐ, A) where T={t_1,t_2,…,t_ℓ} is a set of totally ordered time steps (or layers), 𝒞={c_1,c_2,…,c_n} is a set of characters, and ℐ={I_1,I_2,…,I_m} is a set of interactions. Each interaction I∈ℐ has a corresponding time step (I) ∈ T and consists of a set of characters (I) ⊆𝒞. Further, A maps each character c∈𝒞 to a consecutive set of time steps, i.e., A(c)={t_i,t_i+1,…, t_j} for 1≤ i≤ j≤ℓ. We say that character c is active at the time steps in A(c), it starts at t_i and ends at t_j.
We define AC(t) for t∈ T as the set of all characters c∈𝒞 active at time t, i.e., 
AC(t)={c∈𝒞| t∈ A(c)}.
Clearly, for each interaction I∈ℐ, (I)⊆AC((I)) must hold.
Next, we define the set of all characters active in the time interval [t_i,t_j] (1≤ i≤ j≤ℓ) as AC(t_i,t_j)=AC(t_i)∩AC(t_i+1)∩…∩AC(t_j). 
For a time step t∈ T we define the set of interactions at t as ℐ(t)={I∈ℐ|(I)=t} and its corresponding set of characters as CI(t)=⋃_I∈ℐ(t)(I). Without loss of generality, for the interactions at time step t we assume that |ℐ(t)| 0 and that the sets of characters of the interactions ℐ(t) are pairwise disjoint. This is a reasonable assumption as characters usually participate in at most one interaction at any given time, e.g. in movies. Important notation is also illustrated in <ref>.



    Problem output.

Solutions to storyline instances (T,𝒞,ℐ, A) consist of a sequence of ℓ permutations S=(π_1,π_2,…,π_ℓ) such that π_i is a permutation of AC(t_i) for all i=1,…,ℓ satisfying the condition that the set of characters of each interaction I∈ℐ(t_i) 
appears consecutively.
We call S a storyline solution or drawing.


The number of crossings cr(π_i, π_i+1) between two consecutive permutations π_i and π_i+1 is defined as the number of inversions of the two permutations π_i[C] and π_i+1[C], where C=AC(t_i)∩AC(t_i+1). The number of crossings in a storyline solution is ∑_i=1^ℓ-1cr(π_i,π_i+1). The problem addressed in this paper is the following.

[Storyline Problem]
    Given a storyline instance (T,𝒞,ℐ,A), find a storyline drawing S with the minimum number of crossings.





§ STANDARD MODELS FOR THE STORYLINE PROBLEM
 

The most natural ILP formulation to solve <ref> has a quadratic objective function and is based on the linear ordering model, which uses binary variables in order to encode the linear ordering at each time step. The number of crossings between two subsequent time steps is then given by the number of inversions of the two permutations.

From now on, we assume that characters c_u,c_v,c_w are pairwise different, even if we write for example c_u,c_v∈ C for some set C of characters.



  §.§.§ Quadratic Model (QDR)

For each time step t_i,i=1,2,…,ℓ and each tuple of characters c_u,c_v∈AC(t_i) we introduce a binary ordering variable x_i,u,v which is equal to 1 if and only if c_u≺_π_ic_v.
The quadratic model QDR is given as follows:











    min     ∑_i=1^ℓ-1∑_c_u,c_v∈AC(t_i,t_i+1)x_i,u,vx_i+1,v,u      QDR
    
      x_i,u,v = 1- x_i,v,u       for all  i=1,…,ℓ; c_u,c_v∈AC(t_i)  with  u<v EQ
    
            x_i,u,v+x_i,v,w+x_i,w,u≤ 2        for all   i=1,…,ℓ; c_u,c_v,c_w∈AC(t_i) 
            LOP
    
       x_i,u,w=x_i,v,w       for all   i=1,…,ℓ; I∈ I(t_i); TREE
             c_u,c_v∈(I), u<v; c_w∈AC(t_i)∖(I)
    
       x_i,u,v∈{0,1}       for all  i=1,…,ℓ; c_u,c_v∈AC(t_i), BIN


 The character curves for c_u and c_v cross between the two layers t_i and t_i+1 if and only if
 one of the terms x_i,u,vx_i+1,v,u and x_i,v,ux_i+1,u,v equals 1.
The (<ref>) and (<ref>) constraints ensure transitivity of the set of characters AC(t_i) present at time step t_i and guarantee that they define a total order.


For all interactions I∈ I(t_i) 
the (<ref>) constraints ensure that characters from I appear consecutively at the respective time step t_i. 







  §.§.§ Linearized Model (LIN)

The standard linearisation of quadratic integer programs introduces additional variables y_i,u,v that substitute the quadratic terms x_i,u,vx_i+1,v,u for all t_i, i=1,2,…,ℓ-1 and each tuple of characters c_u,c_v∈AC(t_i,t_i+1) in the objective function. 
In order to link the new variables with the ordering variables, we introduce the following constraints:


    y_i,u,v≥ x_i,u,v-x_i+1,u,v     for all  i=1,…,ℓ; c_u,c_v∈AC(t_i,t_i+1) CR

Obviously, the variable y_i,u,v is forced to 1, if the character c_u is before c_v at time step t_i in the solution represented by the y-variables, and the order of both characters is reversed at time step t_i+1.

The linearised model (<ref>) is given as follows.


    min     ∑_i=1^ℓ-1∑_c_u,c_v∈AC(t_i,t_i+1)y_i,u,v      LIN
          y_i,u,v,x_i,u,v satisfy  (<ref>), (<ref>), (<ref>), (<ref>), and (<ref>)










  §.§.§ Max-Cut Model (CUT)


Gronemann et al. <cit.> have suggested a formulation based on the transformation of the problem into a quadratic unconstrained binary program with additional (TREE) constraints, which is then solved using a maximum cut approach. Here, we omit the detour via the quadratic binary program and directly provide the corresponding maximum cut formulation. 


Starting with a feasible storyline drawing Ŝ=(π̂_1,…,π̂_ℓ), we define the graph G_M=(V_M,E_M): 
The vertex set V_M is given by a vertex v^* and the union of the sets V_i (i=1,…,ℓ), where V_i has a vertex c_uv^i for each pair c_u,c_v∈AC(t_i) with c_u≺_π̂_ic_v.


We introduce an edge between the vertices c_uv^i and c_pq^i+1 if the corresponding characters coincide.
In the case that c_u=c_p and c_v=c_q, the (type-1) edge e=e_uv^i gets a weight of w_e=-1, and in the case that c_u=c_q and c_v=c_p, the (type-2) edge e=e_uv^i gets a weight of w_e=1.
We define the constant K as the number of edges of type (2). 



The intention is the following: 
An edge of type (1) results in a crossing if and only if it is in the cut, and an edge of type (2) results in a crossing if and only if it is not in the cut.
This construction allows for associating the maximum cut objective function values W to corresponding crossing numbers K-W. 
In particular, W=0 for the empty cut corresponds to the number of crossings K in Ŝ.
In order to guarantee that the characters of an interaction appear consecutively, we introduce type-3 edges with weight 0 from the additional vertex v^* to every vertex in V_i for all i=1,…,ℓ, and add the additional constraints (<ref>).

We introduce a binary variable z_e for every edge e∈ E_M in the graph, which is 1 if and only if the edge is contained in the computed cut.

The following model guarantees that every optimal solution corresponds to a constrained maximum cut in the graph G_M that provides the optimal solution to the storyline problem. 

The constraints (<ref>) capture the fact that any intersection of a cut and a cycle in a graph has even cardinality.
The correctness is provided in <cit.>, see also <cit.>.


    max     ∑_e∈ E_Mw_ez_e CUT
    ∑_e∈ Fz_e-∑_e∈ C∖ Fz_e≤| F| -1       , F⊆ C, | F | oddCYC
    
    
          
            0≤ z_(v^*,c_uv^i)+z_(v^*,c_vw^i)-z_(v^*,c_uw^i)≤ 1      for all   i=1,…,ℓ; c_uv^i,c_vw^i,c_uw^i∈ V_i
            LOPC
         with  c_u≺_π̂_ic_v≺_π̂_ic_w
     z_(v^*,c_uw^i)=z_(v^*,c_vw^i) if c_u,c_v≺_π̂_ic_w
    
           z_(v^*,c_wu^i)=z_(v^*,c_wv^i) if c_u,c_v≻_π̂_ic_w
                   for all   i=1,…,ℓ; I∈ I(t_i);
       c_u,c_v∈(I); c_w∈AC(t_i)∖(I)
       TRC
    
     z_e∈{0,1}     BIC




§ STRUCTURAL PROPERTIES OF STORYLINE SOLUTIONS

In this section, we identify structural properties of storyline solutions that will help us to optimize the models proposed in <ref>, and that guide the exact optimization process. 

For the results in this section, we introduce some definitions and observe some properties of the function .
Let π be a permutation of the set X, and ϕ be a permutation of the set Y⊆ X.
We define the permutation ψ=(π,ϕ) as the permutation of the set X such that

    ψ(i)=π(i)    if π(i)∈ X∖ Y
    ϕ(j)    if c=π(i)∈ Y with j=π[Y]^-1(c)

In particular, all elements in X∖ Y are ordered according to π, and all elements in Y switch their position so that they are ordered according to ϕ.
Notice that (π,ϕ)[Y]=ϕ.

    Let π=(c,e,b,d,f,a,g) and ϕ=(a,b,c). Then (π,ψ)=(a,e,b,d,f,c,g).

Consider three consecutive time steps t_i,t_i+1,t_i+2 (1≤ i≤ℓ-2), we observe a special type of triangle inequality.


    Let C⊆AC(t_i,t_i+2). For any feasible solution S we have
    
    (π_i[C],π_i+1[C])+(π_i+1[C],π_i+2[C])≥(π_i[C],π_i+2[C]).


Next, consider two permutations π_i,π_i+1 of a storyline solution such that C=AC(t_i)∩AC(t_i+1). 
Consider two sets X,Y⊆ C. We define (π_i,π_i+1,X,Y) as the amount of (c,c')∈ X× Y such that either c≺_π_ic' and c'≺_π_i+1c, or c'≺_π_ic and c≺_π_i+1c'. I.e., these are the crossings between time steps t_i and t_i+1 with one character in X and one character in Y. We set (π_i,π_i+1,X)=(π_i,π_i+1,X,X).


    It holds that (π_i,π_i+1,X)=(π_i[X],π_i+1[X]).


Let X,Y be sets such that X∪̇Y=C⊆AC(t_i,t_i+1). It holds that

    (π_i,π_i+1, C)=(π_i,π_i+1,X)+(π_i,π_i+1,Y)+(π_i,π_i+1,X,Y).



Now, we define two properties of storyline drawings. <ref> captures that the relative order of characters in an interaction can be propagated backwards.


    Let S=(π_1,π_2,…,π_ℓ) be a solution to a storyline instance (T,𝒞,ℐ, A). Let I∈ℐ, t_i=(I) and C=(I). Let 1< j(I)≤ i be the index of the earliest time step t_j(j) such that C⊆AC(t_j(I),t_i) and
    
    ∀ k∈{j(I)+1,…, i}:CI(t_k)∩ C=∅∃ I∈ℐ(t_k):C⊆(I).

    
     We say that S is I-consistent if
     
    ∀ k∈{j(I),j(I)+1,…,i}:π_k[C]=π_i[C].

     Further, we say that S is type-1-consistent if it
     is I-consistent for all I∈I.


<ref> defines the property that between suitable pairs of interactions with the same set of characters, these characters are kept together between the two time steps. Note that this is not implied by type-1 consistency.

    Let S=(π_1,π_2,…,π_ℓ) be a solution to a storyline instance (T,𝒞,ℐ, A). Consider two interactions I_1,I_2∈ℐ such that 
    
        
  * (I_1)=(I_2)=C,
        
  * i=(I_1)<(I_2)=j, and
        
  * ∀ k∈ℕ: i<k<j⇒[CI(t_k)∩ C=∅∃ I_3∈ℐ(t_k):C⊆(I_3)].
    
    We say that S is (I_1,I_2)-consistent if
    
    ∀ i<k<j:∃π^a,π^b:π_k=π^a⋆π_i[C]⋆π^b.

    Further, we say that S is type-2-consistent if it is (I_1,I_2)-consistent for all such pairs (I_1,I_2).


The following lemma shows that we can achieve type-1 consistency for storyline drawings without increasing the number of crossings. Essentially, if a storyline solution is not type-1 consistent for an interaction I, we can propagate the relative order of characters in that interaction forward from the time step t_j(I) from <ref>.
lemmatypeonelemma
    
    Let (T,𝒞,ℐ, A) be an instance with a solution S. We can construct from S a type-1-consistent solution S' such that (S')≤(S). If S is type-2-consistent, so is S'.


    Let S=(π_1,π_2,…,π_ℓ) be a solution such that there exists I∈ℐ such that S is not I-consistent.
    We choose such an interaction I that is as “late as possible”, i.e. I∈ℐ(t_i) with i maximal.
    We construct S'=(π_1',π_2',…,π_ℓ') such that
    
        
  * (S')≤(S), 
        
  * S' is I-consistent,
        
  * for each I'∈ℐ such that S is I'-consistent and (I')≥(I), S' is also I'-consistent.
    
    Let t_i=(I) and C=(I) and define j(I)<i as in <ref>.
    For all 1≤ k≤ℓ such that k≤ j(I) or k>i we set π_k'=π_k.
    For k∈{j(I)+1,j(I)+2,…,i} we set π_k'=(π_k,π_j(I)[C]).
    It is clear that the new solution S' is I-consistent and is still a solution to the storyline instance (characters involved in interactions are still consecutive in the respective time steps).
    
    We first argue that (S')≤(S).
    First, it is clear that (π'_k,π'_k+1)=(π_k,π_k+1) for k≤ j(I)-1 and k>i as the involved permutations did not change.
    It remains to show that 
    
    ∑_k=j(I)^i(π_k',π_k+1')≤∑_k=j(I)^i(π_k,π_k+1).

    We also have that 
    
    ∑_k=j(I)^i(π_k',π_k+1')=   ∑_k=j(I)^i(π_k',π_k+1',C)+
       ∑_k=j(I)^i(π_k',π_k+1',AC(t_k,t_k+1)∖ C)+
       ∑_k=j(I)^i(π_k',π_k+1',C,AC(t_k,t_k+1)∖ C),

    and 
    
    ∑_k=j(I)^i(π_k,π_k+1)=   ∑_k=j(I)^i(π_k,π_k+1,C)+
       ∑_k=j(I)^i(π_k,π_k+1,AC(t_k,t_k+1)∖ C)+
       ∑_k=j(I)^i(π_k,π_k+1,C,AC(t_k,t_k+1)∖ C).

    Thus it is enough to show that the inequality holds for the respective terms separately.
    
        
  * ∑_k=j(I)^i(π_k',π_k+1',C)≤∑_k=j(I)^i(π_k,π_k+1,C): We have
        
    ∑_k=j(I)^i(π_k,π_k+1,C)   =∑_k=j(I)^i(π_k[C],π_k+1[C])
       ≥∑_k=j(I)^i(π_k[C∩AC(t_i+1)],π_k+1[C∩AC(t_i+1)])
       ≥(π_j(I)[C∩AC(t_i+1)], π_i+1[C∩AC(t_i+1)])
       =(π'_i[C∩AC(t_i+1)], π_i+1'[C∩AC(t_i+1)])
       =∑_k=j(I)^i(π_k',π_k+1',C)

        The first inequality holds because C∩AC(t_i+1) is a subset of C. The second inequality holds because of <ref>. The last equality holds because the only crossings between characters from C from t_j(I) to t_i+1 appear between t_i and t_i+1 as the relative order of characters from C in S' is the same from j(I) to i.
        
        
  * ∑_k=j(I)^i(π_k',π_k+1',AC(t_k,t_k+1)∖ C)≤∑_k=j(I)^i(π_k,π_k+1,AC(t_k,t_k+1)∖ C): Let k∈{j(I), j(I)+1,…,i} and let C_a=AC(t_k,t_k+1)∖ C. We have that
        
    (π_k',π_k+1',AC(t_k,t_k+1)∖ C)   =(π_k'[C_a],π_k+1'[C_a])
       =(π_k[C_a],π_k+1[C_a])
       =(π_k,π_k+1,AC(t_k,t_k+1)∖ C).

        The key is that π_k[C_a]=π_k'[C_a] and π_k+1[C_a]=π_k+1'[C_a], as we did not change the relative order of non-interaction characters, that is, characters that are not in C.
        As the equality holds for each term, it also holds for the sum.
        
  * ∑_k=j(I)^i(π_k',π_k+1',C, AC(t_k,t_k+1)∖ C)≤∑_k=j(I)^i(π_k,π_k+1,C, AC(t_k,t_k+1)∖ C): We again argue for each k∈{j(I),j(I)+1,…,i} separately and consider two cases.
        
        If k=i then the relative order of character pairs (c,c')∈ C× (AC(t_k,t_k+1)∖ C) is the same for π_i and π_i' as C must be consecutive in t_i, and π[AC(t_k,t_k+1)∖ C] = π'[AC(t_k,t_k+1)∖ C]. The relative order is also the same in π_i+1' and π_i+1 as π_i+1'=π_i+1. Thus (π_k,π_k+1,C,AC(t_k,t_k+1))∖ C)=(π_k',π_k+1',C,AC(t_k,t_k+1)∖ C) holds.

        In the remaining case, we have that k∈{j(I),j(I)+1,…,i-1}. Consider a character c∈AC(t_k,t_k+1)∖ C. Let α be the amount of characters from C that are crossed by c between t_k and t_k+1 in S. We show that c crosses at most α characters from C between t_k and t_k+1 in S', which is enough to show the claim.
        Let abv_k be the amount of c'∈ C such that c'≺_π_kc. Define abv_k+1 by replacing k with k+1 in the definition. Equivalently define abv_k' and abv_k+1' by replacing π_k by π_k' and π_k+1 by π'_k+1, respectively.
        By the definition of  we have that abv_k=abv_k' and abv_k+1=abv_k+1'. By the pigeonhole principle, c must cross at least β=|abv_k-abv_k+1| characters from C between t_k and t_k+1 (for S and S'). Notice that β is the exact amount of crossings for S' and β≤α must hold as β is a lower bound. Thus c crosses less than or equal characters from C between t_k and t_k+1 in S' when compared to S.
    
    Putting these inequalities together, we get (S')≤(S). It is easy to see that we constructed S' such that it satisfies (2).

    It remains to show (3), i.e. that for each I'∈ℐ such that S is I'-consistent and (I')≥(I), S' is also I'-consistent. We show the claim by contradiction, so assume to the contrary that there exists some I' with (I')≥(I), S is I'-consistent, and S' is not. First, it is worth noting that we only change relative orders of character pairs involving at least one character from C. 
    We consider different cases.
    
        
  * (I')=(I): Then (I)∩(I')=∅. Hence, we did not change relative orders of character pairs from (I') and we obtain a contradiction.
        
  * (I')>(I)=t_i. We again consider two cases.
        
            
  * (I')⊆(I): It follows that j(I')<i and further j(I')≤ j(I). As we changed orders for character pairs from (I'), we have that S is already not I'-consistent, a contradiction.
            
  * (I')⊈(I): Then j(I')≥ i. But we only changed orders up to i, so S' is already not I'-consistent, a contradiction.
        
    
    Lastly, assume that S is type-2-consistent, we prove that S' is as well. We proceed by contradiction.
    Hence, let there be (I_1,I_2) as in <ref> such that S is (I_1,I_2)-consistent, but S' is not. It follows that the interval [t_j(I)+1,t_i] has non-empty intersection with [(I_1),(I_2)]. It further follows that (I_1)⊆ C. But if S was already (I_1,I_2)-consistent, we did not change relative orders nor positions of characters in (I_1) during the above process, a contradiction.
    
    The proof is concluded by applying the above procedure inductively.


A similar result with a related proof argument holds for type-2 consistency.
lemmatypetwolemma
    
    Let (T,𝒞,ℐ, A) be an instance with a solution S. We can construct from S a type-2-consistent solution S' such that (S')≤(S). If S is type-1-consistent, so is S'.


    Let S be a solution that is not type-2-consistent, i.e. there exist interactions I_1,I_2∈ℐ such that S is not (I_1,I_2)-consistent with i=(I_1),j=(I_2) and C=(I). Choose such a pair such that j-i is maximized.
    We construct S'=(π_1',π_2',…,π_ℓ') such that
    
        
  * (S')≤(S),
        
  * S' is (I_1,I_2)-consistent, and
        
  * for each I_1',I_2'∈ℐ such that S is (I_1',I_2')-consistent, S' is also (I_1',I_2')-consistent,
    
    as follows: For k∈{1,2,…,i}∪{j+1,j+2,…,ℓ} we set π_k'=π_k.
    Now we find a character from C that has the fewest crossings with characters not in C between t_i and t_j. Formally, we define c^*∈ C such that
    
    c^*=*argmin_c∈ C∑_k=i^j-1(π_k,π_k+1,{c},AC(t_k,t_k+1∖ C)).

    For each k∈{i+1,i+2,…,j} we do the following. Let π^a,π^b be such that π_k=π^a⋆ (c^*)⋆π^b, where (c^*) is the unit permutation of the set {c^*}. We set π'_k=π^a[AC(t_k)∖ C]⋆π_i[C]⋆π^b[AC(t_k)∖ C].
    Informally, we first remove C from π_k and then insert the permutation π_i[C] at the position of c^*.
    We first argue that (S')≤(S).
    First, it is clear that (π'_k,π'_k+1)=(π_k,π_k+1) for k≤ i-1 and k>j as the involved permutations did not change.
    It remains to show that 
    
    ∑_k=i^j(π_k',π_k+1')≤∑_k=i^j(π_k,π_k+1).

    We split up the crossings into types, as in the proof of <ref>; i.e. we consider crossings between pairs C× C,AC(t_k,t_k+1)× C, and AC(t_k,t_k+1)×AC(t_k,t_k+1), respectively.
    
        
  * ∑_k=i^j(π_k',π_k+1',C)≤∑_k=i^j(π_k,π_k+1,C): We have
        
    ∑_k=i^j(π_k,π_k+1,C)   =∑_k=i^j(π_k[C],π_k+1[C])
       ≥∑_k=i^j(π_k[C∩AC(t_j+1)],π_k+1[C∩AC(t_j+1)])
       ≥(π_i[C∩AC(t_j+1)], π_j+1[C∩AC(t_j+1)])
       =(π'_j[C∩AC(t_j+1)], π_j+1'[C∩AC(t_j+1)])
       =∑_k=i^j(π_k',π_k+1',C)

        The first inequality holds because C∩AC(t_i+1) is a subset of C. The second inequality holds because of <ref>. The last equality holds because the only crossings between characters from C from t_i to t_j+1 appear between t_j and t_j+1 as the relative order of characters from C in S' is the same from i to j.
        
  * ∑_k=i^j(π_k',π_k+1',AC(t_k,t_k+1)∖ C)≤∑_k=i^j(π_k,π_k+1,AC(t_k,t_k+1)∖ C): Let k∈{i,i+1,…, j} and let C_ac=AC(t_k,t_k+1)∖ C. We have that
        
    (π_k',π_k+1',AC(t_k,t_k+1)∖ C)   =(π_k'[C_ac],π_k+1'[C_ac])
       =(π_k[C_ac],π_k+1[C_ac])
       =(π_k,π_k+1,AC(t_k,t_k+1)∖ C).

        The key is that π_k[C_ac]=π_k'[C_ac] and π_k+1[C_ac]=π_k+1'[C_ac], as we did not change the relative order of non-interaction characters, that is, characters that are not in C.
        As the equality holds for each term, it also holds for the sum.
        
  * ∑_k=i^j(π_k',π_k+1',C, AC(t_k,t_k+1)∖ C)≤∑_k=i^j(π_k,π_k+1,C, AC(t_k,t_k+1)∖ C): This inequality holds by definition of c^*. Each character from C is involved in the same crossings between t_i and t_j.
        The crossings between t_j and t_j+1 are exactly the same, as relative orders of character pairs in C× (AC(t_k,t_k+1)∖ C) are the same in S and S' for k=j,j+1.
    

The following is a direct consequence.

    For each storyline instance (T,𝒞,ℐ, A) there exists a crossing-minimum solution S that is type-1-consistent and type-2-consistent.




<ref> is the main ingredient for a new ILP formulation given in <ref>.
It shows that we can in specific cases assume the order of characters C_a above and C_b below an interaction at time step t_i to be equal to the relative order at t_i-1. This is similar to type-1-consistency, where the relative order of characters in an interaction sometimes can be kept.
theorempropthm
    
    Let (T,𝒞,ℐ, A) be a storyline instance. There exists a crossing-minimum solution S=(π_1,π_2,…,π_ℓ) with the following property.
    For all t_i∈{t_2,t_3,…,t_ℓ} with |ℐ(t_i)|=1, where ℐ(t_i)={I}, the following holds.
    
        
  * ∃ C_a,C_b:π_i=π_i[C_a]⋆π_i[(I)]⋆π_i[C_b],
        
  * if C_a⊆AC(t_i-1,t_i), then π_i[C_a]=π_i-1[C_a],
        
  * if (I)⊆AC(t_i-1,t_i), then π_i[(I)]=π_i-1[(I)], and
        
  * if C_b⊆AC(t_i-1,t_i), then π_i[C_b]=π_i-1[C_b].
    


    Consider a crossing-minimum solution S^*=(π_1^*,π_2^*,…,π_ℓ^*). We construct a new storyline instance (T,𝒞,ℐ', A) where ℐ'=ℐ∪ℐ_S^*, with ℐ_S^* containing the following interactions.
    For each t_i∈{t_2,t_3,…,t_ℓ} with |ℐ(t_i)|=1 and ℐ={I}, let C_a,C_b∈AC(t_i) such that π_i^*=π_i[C_a]*π^*_i[(I)]⋆π^*_i[C_b].
    If C_a⊆AC(t_i-1,t_i), then add to ℐ_S^* the interaction I_a with (I_a)=C_a and (I_a)=t_i.
    If C_b⊆AC(t_i-1,t_i), then add to ℐ_S^* the interaction I_b with (I_b)=C_b and (I_b)=t_i.
    Note that S^* is still a crossing-minimum solution for the new instance. Hence, we apply <ref> to S^* for the new storyline instance. We obtain a new solution S that is crossing-minimum and type-1-consistent. Type-1-consistency for new interactions implies (2) and (4), type-1 consistence of the original interactions implies (3). Lastly, S is also a crossing-minimum solution of the original instance as (S)≤(S^*) by <ref>, and the statement follows.








§ REFINING THE ILP MODELS

We apply our structural insights from <ref> to the models (besides the (<ref>)-model) to obtain a new ILP formulation, including a reduction of the number of (LOP) constraints in <ref> via <ref> and the inclusion of additional symmetry breaking constraints in <ref> via <ref>.



 §.§ The Propagated Linear Ordering Model (PLO)




For our new formulation, we take the linearized model (<ref>) as basis, but remove some of the (<ref>)-constraints for time step t_i as we can make use of propagating the ordering at t_i-1 by <ref> as follows. 

If ℐ(t_i) for i>1 contains only one interaction I, and no characters outside the interaction start at t_i (i.e., AC(t_i)∖AC(t_i-1)⊆CI(t_i)), we only include a part of the (<ref>)-constraints for time step t_i using a representative character c_w∈(I): 

From the set of (<ref>)-constraints containing at least one character in AC(t_i)∖(I), we keep only those that contain exactly two characters in AC(t_i)∖(I) and the representative character c_w∈(I).

This is sufficient, because we can define the order of the active characters in t_i relative to the order of the characters in the interaction I based on <ref>. Hence, let c_w be a representative character from the set (I), and consider a pair of characters c_u,c_v∈AC(t_i)∖(I). 
By <ref>, if both c_u and c_v are above or below c_w, then their relative order can be fixed by their relative order at t_i-1. Otherwise, their relative order is already given by their relative order to c_w. That is, if, e.g., c_u is above c_w and c_v is below c_w, then we know that c_u is above c_v. To ensure the above, we add the following constraints in addition to the 
(<ref>)-constraints for c_u, c_v, and c_w at time step t_i.
    
    x_i,u,v   ≥ x_i-1,u,v+x_i,u,w+x_i,v,w-2PROP-R1
    
            x_i,u,v   ≥ x_i-1,u,v+x_i,w,u+x_i,w,v-2PROP-R2

    The two constraints ensure that c_u is above c_v if the requirements are met. By switching c_u and c_v, these constraints also ensure the case that c_u is below c_v. 
 
 
 
 
 

If additionally (I)⊆AC(t_i-1) we can apply <ref> (3) to further reduce the number of those (<ref>)-constraints, whose triples are taken from the set (I):


In this case, we do not add any of the (<ref>)-constraints for the characters in I, but instead for each pair c_u,c_v∈(I), we add the following constraint ensuring that the relative order of c_u and c_v is the same for t_i and t_i-1.
    
    x_i,u,v=x_i-1,u,vPROP-I


 If both reductions for (<ref>) apply, we get a quadratic rather than cubic number of constraints for t_i.
We call this formulation propagated linear order (PLO). Note that this idea of reducing the number of (<ref>)-constraints also works for any of the other standard ILP models. 


theoremplotransitivity
    Every optimal solution to the formulation (PLO) corresponds to a crossing minimum storyline drawing. 


    We only have to show that solutions to PLO satisfy transitivity constraints for the ordering variables, as we include the constraint set (<ref>) and (<ref>). Optimality follows from <ref>.
    We show this by induction on i – the time steps. For the base case of i=1 the variables x_1,u,v for c_u,c_v∈AC(t_1) satisfy transitivity, as we include all (<ref>) constraints for t_1.
    For the induction step, assume that transitivity is satisfied for all time steps t_i' with i'<i. We show that transitivity is satisfied for t_i. We perform a case distinction.
    
        
  * If |ℐ(t_i)|>1 or (AC(t_i)∖AC(t_i-1))⊈CI(t_i), transitivity is clearly satisfied, as we again include all (<ref>)-constraints for this time step. 
        
  * Otherwise, there is exactly one interaction I at time t_i. Consider now three distinct characters c_u,c_v,c_w∈AC(t_i). We show transitivity between this triple for t_i by considering memberships with respect to I.
        
            
  * If {c_u,c_v,c_w} contains at least one character from (I) but {c_u,c_u,c_w}⊈(I) then transitivity for these three characters is achieved because of the (<ref>)-constraints.
            
  * If {c_u,c_v,c_w}∩(I)=∅, then we know that {c_u,c_v,c_w}⊆AC(t_i-1). Thus, transitivity between this triple follows from (<ref>) and (<ref>) and because, by the induction hypothesis, the same triple satisfies transitivity for time step t_i-1.
            
  * If {c_u,c_v,c_w}⊆(I), we again have two cases. If (I)⊈AC(t_i-1), transitivity is clearly satisfied as we add all (<ref>)-constraints between triples in (I) for this time step. Otherwise, transitivity for this triple follows from the induction hypothesis and (<ref>).
    

    










































 §.§ Symmetry Breaking Constraints

We introduce the set (SBC) of symmetry breaking constraints that are based on <ref> and might improve the solving process of the models, as they constitute equalities:

    
  * We can assume that a crossing-minimum solution is type-1 consistent. Thus let I∈ℐ with t_i=(I) and let j(I) be defined as in <ref>.  For all pairs c_u,c_v∈(I) and all j(I)≤ k<i we can add the following constraint enforcing type-1 consistency:
    
    x_k,u,v=x_i,u,vSBC-1

    
  * We can assume that a crossing-minimum solution is type-2 consistent. Thus, let I_1,I_2∈ℐ be two distinct interactions satisfying the properties of <ref>. Let i=(I_1) and j=(I_2).
    For all i<k<j, all pairs c_u,c_v∈(I_1), and all c_w∈AC(t_k)∖(I_1) 
    we add the following constraint, enforcing type-2 consistency:
    
    x_k,u,w=x_k,v,wSBC-2

    
    






§ IMPLEMENTATION

In this section, we discuss relevant implementation details and new heuristic-based approaches to improve our algorithms.



 §.§ Initial Heuristic


Our initial heuristic follows a decomposition strategy. The original problem instance is first split into smaller subproblems, each comprising  many consecutive time steps, which are of such a size that it is possible to quickly compute a crossing minimal solution for this subproblem.
The initial heuristic solution S_h is computed by optimally solving these subsequent “slices” of the original problem instance and piecing together a global solution. This works as follows.
First, a crossing minimal solution S_1 = (π_1, …, π_ℓ̂) is computed for the first  many time steps of the original problem using the [section:newformulation]PLO ILP formulation. The first  many layers of S_1 are assigned to the initial heuristic solution S_h. In the next iteration, we compute an optimal solution for time steps ,…,+-1 while enforcing the ordering of layer ŝ by fixing the ordering variables accordingly. Again, we fix the first  many permutations of this solution as the permutations of the corresponding time steps in the heuristic solution S_h. This is continued until the heuristic solution is computed for all time steps t_1,t_2,…,t_ℓ.

We choose < in order to include as much information about the global problem into the sliced subproblem as possible (in the form of the time steps that are about to come), while achieving a good tradeoff between time needed to solve all subproblems and the number of crossings of S_h. Experimental evaluation showed that = 5,  = 30 yields a good tradeoff between runtime and solution quality.





 §.§ Rounding and Local Improvement Heuristics

We propose a rounding heuristic that exploits fractional LP-solutions. 
Furthermore, we try to improve these solutions as well as incumbent solutions found by the solver software by proposing three local improvement heuristics Rem-DC, Push-CR, and SL-Bary.



    Rounding Heuristic.
 We propose a strategy to round fractional solutions of the ordering variables x_i,u,v to valid integer solutions corresponding to a drawing of the storyline instance.  
In particular, we compute permutations π_i for t_i, going from i=1 to ℓ in this order, and convert them to integer solutions of ordering variables in the natural way. This works as follows. First, for each interaction I∈ℐ(t) we compute a permutation π_I of its characters (I). For this we compute for each c∈(I) the value (c) which is computed as A+B where A is the number of c'∈(I) such that x_i,c',c>0.5+ϵ and B is the number of c' such that |x_i,c,c'-0.5|≤ϵ, {c,c'}⊆AC(t_i-1), and c'≺_π_i-1 c[This is useful as setting all ordering variables to 0.5 is a valid solution to the LP relaxation of most considered models and thus ordering variables often assume this value]. Clearly, B is only positive if i>1. Then π_I is computed by sorting (I) by their -values. If the model contains symmetry breaking constraints, this sometimes leads to an infeasible ordering. In this case, we find an order π_I that also satisfies the symmetry breaking constraints imposed by π_i-1 (some pairs of characters must have the same relative order in π_i and π_i-1) as follows. We construct π_I iteratively by always selecting the character c∈(I) that has the smallest value (c) and, furthermore, there is no character c' which was not selected yet and needs to precede c according to π_i-1 and the symmetry constraints. This is implemented in quasi-linear time using a priority queue.



    Local Improvement Heuristics.


    
  Rem-DC (remove double crossings) This heuristic finds pairs of characters that cross twice, and both crossings can be removed without increasing the total number of crossings. Formally, this is possible for a drawing S and two characters c,c' if there exist 1≤ i<j≤ℓ with j-i>1 such that

    
  * c and c' cross between t_i and t_i+1, and t_j-1 and t_j, and
    
  * for all k∈ℕ with i<k<j, c and c' either belong to the same interaction in t_k, or they both are in no interaction for t_k.

Then for all k as above we can exchange c and c' in π_k. This removes the double-crossing between c and c' and further does not introduce new crossings.
    
  Push-CR This heuristic proceeds from i=2,…,ℓ in this order and tries to push crossings between π_i-1 and π_i forward by one time step: Let C be a maximal set of characters such that (1) all characters in C appear consecutively in π_i, (2) C⊆AC(t_i-1,t_i), and (3) all characters in C either appear in the same interaction in t_i or no character in C is part of an interaction. For each such set of characters C we replace in π_i, π_i[C] by π_i-1[C]. By similar arguments as in <ref> this never increases the number of crossings.
    
  Bary-SL Lastly, we describe a variant of the barycenter heuristic <cit.> for storylines that iteratively improves a storyline drawing by updating π_i for 1≤ i≤ℓ based on π_i-1 and π_i+1 or one of them if not both exist. It is only applied to π_i if |ℐ(t_i)|=1. Informally, we say that a pair of characters c,c' is comparable if c and c' have the same relative order in π_i-1 and π_i+1. We compute an ordering π_i such that most comparable pairs have the same relative order in π_i-1,π_i,π_i+1 as follows. We compute the directed auxiliary graph G_C whose vertex set is a subset S of AC(t_i) and which contains an arc from c to c' for each comparable pair c and c' such that c is before c' in π_i-1 and π_i+1. Then, an order of S is built by iteratively selecting the vertex from G_C with the fewest incoming arcs. We also ensure that characters c that are not part of I are above or below the characters in I depending on which option leads to fewer crossings between c and (I) with respect to the considered time steps t_i-1,t_i,t_i+1. The algorithm computing the order based on the graph G_C is then applied to the characters in the interaction yielding π_I, and those not in the interaction yielding π_C, respectively. The ordering π_C is inserted into the maximum position of π_I such that all characters before π_C “prefer” being above the interaction with regard to crossings with (I).
The new π_i is only accepted if it decreases the number of crossings.




Both Bary-SL and Push-CR are applied successively to layers 2,…,ℓ. This is repeated five times and applied to valid integer solutions found by the solver and the rounding heuristic described above. If enabled, the rounding heuristic is applied to every LP solution found by the solver. Rem-DC is applied five times to each pair of characters.







 §.§ Max-Cut Implementation Details

Since the original implementation of Gronemann et al. <cit.> is not available, we provide our own implementation that was optimized beyond their algorithm. 
After reading the input, we first find an initial starting solution by applying adapted barycenter techniques as described in <cit.>. 
We start the root relaxation with the objective function and the tree constraints (<ref>) as the only constraints, 
and start separating the odd cycle (<ref>) (as suggested by Charfreitag et al. <cit.>) and the (<ref>) constraints. 





The (<ref>) constraints are separated by complete enumeration.

Whenever a new LP solution is available, all nonbinding inequalities are eliminated, and we try to exploit the information in the (fractional) solution in order to obtain a better 
incumbent solution. 

The root phase ends when no violated inequalities are found. Then the branch-and-cut phase is started by changing the variable types from continuous in the interval [0,1] to binary. 
In the Gurobi “MIPSOL” callbacks at branch-and-cut nodes with an integer solution, we check if the integral solution is the characteristic vector of a storyline drawing. If so and if the number of crossings is lower than the one of the incumbent solution, the latter is updated, otherwise, the exact (<ref>) and (<ref>) separators are called to provide violated inequalities that are passed to Gurobi as lazy constraints.
In the Gurobi “MIPNODE” callbacks it is tried to exploit the fractional solution for a possible update of the incumbent solution.




 §.§ Implementation of the ILP Models

The models (<ref>), (<ref>), and (PLO) include many  symmetries regarding ordering variables and crossing variables. 
For each t_i∈ T and pair of characters c_u,c_v∈AC(t_i) we only keep the ordering variables x_i,u,v and crossing variables y_i,u,v with u<v. The constraints are adjusted with standard projections <cit.>. 




We take the linearized model (<ref>) as basis for our refined ILP model described in Section <ref>, because preliminary experiments showed no performance gain from refining (<ref>) instead. Further, the linearized model (<ref>) is competitive with the max-cut approach when implemented in Gurobi. Therefore, we decided on refining the linearized model that is simpler to implement and more accessible when compared with the max-cut approach.  
Furthermore, implementing any of the ILP models naively includes up to 𝒪(ℓ n^3) (<ref>)-constraints in the model. We have experimented with adding these constraints during a cutting-plane approach and also by including them into the Gurobi solver as lazy constraints, i.e., constraints that the solver can decide to include at later stages during the solving process. 
We decided to always add (<ref>) as lazy constraints, as this leads to the best performance.
Hence, we consider the following algorithms for our experimental evaluation.

    
  * : the max-cut formulation (as a baseline) implemented as described in <ref>
    
  * : the linearized model (<ref>) with (<ref>)-constraints included as lazy constraints
    
  * : the quadratic model (<ref>) with (<ref>)-constraints included as lazy constraints
    
  * : the PLO formulation with (<ref>)-constraints included as lazy constraints









The latter three algorithms are by default extended with the symmetry breaking constraints described in <ref> (), the initial heuristic from <ref> (), and the rounding and local improvement heuristics from <ref> (). This is not done for , as it should serve as a state-of-the-art baseline and allow comparison with Gronemann et al. <cit.>.




§ EXPERIMENTS AND EVALUATION


In our experimental evaluation, we are interested in the following research questions.

    
  Q1: Does the algorithm  based on our new ILP model dominate the state-of-the-art model ? Will we be able to solve hard instances that have not been solved to optimality before? How do the various algorithms compare to each other?
    
  Q2: What effect do the structural insights have when applied to the -formulation? 
    
  Q3: What is the effect of the newly introduced components , , and ?



In the following we describe our experimental setup, our benchmark instances, and the results of our study. We also provide our results and analysis on  https://doi.org/10.17605/OSF.IO/3BUA2.



 §.§ Setup

Systems employed for all experiments have AMD EPYC 7402, 2.80GHz 24-core CPUs and 1024GB of RAM, running Ubuntu 18.04.6 LTS; experiments were run using a single thread. 

 is implemented in  and compiled with , , and flag , all remaining code is written in , compiled with  and  in  mode. To solve the ILPs we used Gurobi 11.0.1. The time limit is 3600s (same as Gronemann et al. <cit.>) and the memory limit is 16GB for all experiments. We do not know the memory limit for Gronemann, however memory was certainly not our limiting factor.
The time for the initial heuristic is negligible (<1% of the overall runtime), so it is not counted towards the solving time.


To mitigate performance variability, we ran each instance-setting combination with five different seeds provided to Gurobi; data displayed below corresponds to the seed with the median runtime. With this, an instance counts as “solved in the time limit”, if the majority of the five runs does not time out. 
Source code for the new formulations is available on  https://doi.org/10.17605/OSF.IO/3BUA2.





 §.§ Test Data

The instances used in our computational study are taken from the literature <cit.>. However, we also present a new data set, including existing instances, in a specifically designed storyline data format, together with tools for transformation and visualization of the storyline layouts on  https://doi.org/10.17605/OSF.IO/3BUA2. We also provide data on best known crossing numbers. 

The existing instances from Gronemann et al. <cit.> consist of three book instances from the Stanford GraphBase database <cit.>, i.e., Anna Karenina (anna), Les Misérables (jean) and Adventures of Huckleberry Finn (huck), and the movie instances TheMatrix, Inception, and StarWars. The instances gdea10, gdea20 from Dobler et al. <cit.> consist of publication data from 10 (resp. 20) authors from the GD conference. The publication instances ubiq1, ubiq2 are from Di Giacomo et al. <cit.>. Furthermore, anna and jean are split up into slices of 1-4 consecutive chapters as was done by Gronemann et al. <cit.>[We could not replicate this process fully equivalently, as sometimes our optimal crossing numbers are different to those of Gronemann et al. <cit.>.].
The new instances consist of scenes from nine blockbuster movies, namely Avatar, Back to The Future, Barbie, Forrest Gump, Harry Potter 1, Jurassic Park, Oceans 11, Oppenheimer, and Titanic. 

In all 59 resulting instances, characters are active from their first interaction to their last interaction, and most instances have one interaction per time step.





 §.§ Evaluation






Several instances could be solved within 30s by all algorithms, others could not be solved within the time limit by any of the algorithms. 
The three instances TheMatrix, Inception, and StarWars used commonly in heuristic storyline visualization were all solved within 450ms.
We exclude all these instances and focus on the 23 challenging instances that remain. Out of these, the maximum number of characters is 88, and the maximum number of layers is 234. A table showing detailed statistics of test data and executions of each algorithm is given in <ref>.



    Answering  and .



Figure <ref> displays the number of instances solved over time for each algorithm. We observe that the algorithms differ in their ability to solve challenging instances:  solves the most, followed by  and , with  last. In fact,  solves one instance that cannot be solved by any other algorithm, and additionally solves six instances that could not be solved by Gronemann et al. <cit.> and three more than  within the same time limit. Hence, we answer the first part in  positively. For further illustration, the exact runtimes per instance are also shown in <ref>.

Answering , the structural insights as applied in  reduce the number of constraints by a factor of five on average, comparing  and . More so, they enhance Gurobi's capabilities of strengthening the LP relaxation, as the two instances not solved by  are solved by  in the root, while  starts branching early and times out.
 enters branching in all 23 instances,  in two,  in three,  in seven instances.  solves 21 out of 23 instances in the root, the remaining two with branching.

Furthermore, we computed the speedup factor of , , and , when compared with  on instances where both respective algorithms did not time out. 
This factor is the runtime of  divided by the runtime of, e.g., . The geometric means of these values are 2.6 for , 3.2 for , and 2.7 for . Hence, our new algorithms are 2.6–3.2 times faster than the state-of-the-art algorithm .















    Ablation study to answer .






We conduct an ablation study to discern the impact each of the methods proposed in <ref> has on the algorithms' performance. To this end, we enable all the proposed methods as the baseline configuration for , , and , namely ,   and . Then, each component is disabled one at a time to measure the component's impact on overall performance. 
In <ref> we present the speedup factors of the algorithms vs. their counterparts with the specific component disabled (see also <ref> for more details).


From this table, we conclude that  and the  are beneficial for all algorithms, while  has a small to no noticeable impact.
This is further supported by <ref>, which shows that disabling  or , results in all the formulations solving fewer instances (curves with no and no are below the baseline). Further, <ref> depicts the speedup factors per instance.
This is because  introduces equalities between two variables, and hence improve presolving capabilities and reduce the search space that solvers have to explore. The heuristics of  help the solver find optimal solutions early in the  process. This answers .




    Further observation.

By inspecting <ref> in more detail, we can make the following interesting observations.

    
  *  enters branching on every instance. This results in  solving very small instances faster than the other algorithms, however it struggles to solve larger instances.
    
  * The larger the instance, the fewer constraints  has compared to .
    
  * Most of the instances can be solved within the root of the branch-and-bound tree for most formulations.





 


    Large Instances.
 Finally, we demonstrate that our implementations are capable of solving even very large instances to proven optimality: 
Figure <ref>(a) shows the raw drawing of the data for Victor Hugo’s Les Misérables <cit.> as provided in the data file  of the Stanford GraphBase <cit.>. After roughly 7 hours of single thread computation, we obtained the proven crossing minimum layout shown in Figure <ref>(b).



§ CONCLUSION AND FUTURE WORK

As shown in our experimental study, our new methods and algorithms dominate the state-of-the-art algorithms and are able to solve large instances to optimality, while the newly introduced improvements are beneficial towards all considered formulations. We observe two directions for future work.

    
  * Our new components for improvement could be implemented into the max-cut formulation. However, initial experiments have shown that the simple linearized formulation (<ref>) performs comparably to the more complex max-cut formulation, hence we expect that this will result in a negligible or no improvement over our proposed formulations.
    
  * Out of our 59 instances (see  https://doi.org/10.17605/OSF.IO/3BUA2) we were able to solve 55 when increasing the time limit. The remaining four  unsolved instances should pose a challenge to engineer new exact methods for crossing minimization in storylines.







































§ DETAILED STATISTICS ON INSTANCES AND ALGORITHM EXECUTIONS.



|l|l|r|r|r|r|r|
Table of runtimes for the 23 instances. B&B = number of branch-and-bound nodes, Root LB = lower bound computed at the root node, number of constraints, overall runtime in seconds, and the crossing number or interval of best lower bound and upper bound if not solved within time limit. The value t.l. means time limit and |𝒞|, ℓ, and |ℐ| are the number of characters, layers, and interactions, respectively. 

Instance     Algorithm     B&B     Root LB      #constraints     Time[s]     crossings
Table of runtimes for the 23 instances (continued)
 
Instance     Algorithm     B&B     Root LB      #constraints     Time[s]     crossings
Avatar         1     229     238496     106.4     229 

|𝒞|=35         628     226     820944     284.2     229 

ℓ=54         3295     80          358.5     229 

|ℐ|=54         1     229          841.9     229 
Barbie         1     138     1125220     304.0     138 

|𝒞|=67         1     138     6393964     123.4     138 

ℓ=63         558     48          66.6     138 

|ℐ|=63         1     138          923.6     138 
HarryPotter1         1     236     520981     776.9     236 

|𝒞|=52         597     229     2361796     1123.5     236 

ℓ=54         11288     77          t.l.     [223,239] 

|ℐ|=54         1     236          1444.9     236 
Oceans11         1     275     1271525     536.9     275 

|𝒞|=60         578     271     7018542     1087.9     275 

ℓ=96         11908     82          t.l.     [244,284] 

|ℐ|=96         1     275          2106.1     275 
anna1-2         1     57     1370481     47.8     57 

|𝒞|=57         1     56     6926150     38.2     57 

ℓ=116         561     38          37.6     57 

|ℐ|=116         1     57          53.1     57 
anna1-3         1     108     4241743     1634.2     108 

|𝒞|=83         1     108     30520530     966.5     108 

ℓ=164         1792     52          t.l.     [104,113] 

|ℐ|=164         1     108          2857.8     108 
anna2-3         1     28     1793109     29.4     28 

|𝒞|=67         1     28     10538684     12.8     28 

ℓ=106         100     22          9.3     28 

|ℐ|=106         1     28          30.6     28 
anna2-4         9     76     3738699     701.4     76 

|𝒞|=80         1     76     25966988     472.7     76 

ℓ=155         562     47          136.3     76 

|ℐ|=155         2     76          1339.5     76 
anna3-5         1     107     4882063     1157.5     107 

|𝒞|=88         1     107     36830405     919.4     107 

ℓ=168         2570     59          1168.5     107 

|ℐ|=168         1     107          1404.2     107 
anna4-5         1     70     1568650     80.9     70 

|𝒞|=60         1     70     8222852     48.9     70 

ℓ=120         1642     37          124.8     70 

|ℐ|=120         1     70          112.1     70 
anna4-6         1     157     3228069     2087.8     157 

|𝒞|=71         119     157     19956977     1960.4     157 

ℓ=176         1090     77          2138.1     157 

|ℐ|=176         1     157          2890.4     157 
anna5-6         1     76     1821015     84.6     76 

|𝒞|=63         1     76     10021591     64.9     76 

ℓ=127         782     37          92.6     76 

|ℐ|=127         1     76          83.0     76 
anna6-7         1     78     1586302     155.5     78 

|𝒞|=60         1     78     8300109     73.9     78 

ℓ=118         917     33          110.2     78 

|ℐ|=118         1     78          232.6     78 
anna6-8         193     121     2266237     2700.7     121 

|𝒞|=65         556     118     13025530     2155.1     121 

ℓ=146         3193     52          2352.8     121 

|ℐ|=146         1     121          2280.4     121 
anna7         1     8     525061     0.6     9 

|𝒞|=47         1     8     2151380     0.6     9 

ℓ=62         3     6          0.4     9 

|ℐ|=62         824     8          39.2     9 
gdea20         1     41     108934     26.5     41 

|𝒞|=19         1     41     212494     11.3     41 

ℓ=100         171     19          8.6     41 

|ℐ|=100         1     41          92.2     41 
huck         1     41     2130471     5.7     42 

|𝒞|=74         1     41     13537255     3.3     42 

ℓ=107         140     30          4.5     42 

|ℐ|=107         9547     41          2148.8     42 
jean1-3         1     53     3616478     72.8     53 

|𝒞|=73         1     53     24790611     44.4     53 

ℓ=253         1070     36          108.9     53 

|ℐ|=253         1     53          123.5     53 
jean1-4         1     172     5643798     3306.5     172 

|𝒞|=79         1     172     42117296     2739.6     172 

ℓ=329         1792     75          t.l.     [149,183] 

|ℐ|=329         1     156          t.l.     [156,565] 
jean2-3         1     33     663871     30.7     33 

|𝒞|=41         1     33     2671943     11.0     33 

ℓ=158         181     24          7.5     33 

|ℐ|=158         1     33          56.3     33 
jean2-4         1     154     1358514     3150.6     154 

|𝒞|=47         210     154     6283384     t.l.     [154,159] 

ℓ=234         1587     68          t.l.     [138,156] 

|ℐ|=234         1     148          t.l.     [148,468] 
jean3-4         1     128     780027     1943.7     128 

|𝒞|=41         330     126     3209062     t.l.     [127,132] 

ℓ=175         1720     53          2157.5     128 

|ℐ|=175         1     127          t.l.     [127,170] 
jean4-5         1     96     521469     125.7     96 

|𝒞|=36         1     96     1939809     111.3     96 

ℓ=149         1476     50          171.2     96 

|ℐ|=149         1     96          238.0     96 





