@techreport{TR-IC-PFG-26-24,
   number = {IC-PFG-26-24},
   author  =  {Pedro  Carvalho  Cintra and Gabriel Siqueira and Zanoni
                   Dias},
   title  =  {{Warm-Starting  Exact  Solvers for Minimum Common String
                   Partition Problems}},
   month = {July},
   year = {2026},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 27 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       The  Signed Minimum Common Intergenic String Partition (SMCISP)
       problem    is    used    in    approximation   algorithms   for  
       genome-rearrangement  distances and is NP-hard even over binary
       alphabets.  We  experimentally compare two exact approaches---a
       fixed-parameter   branching   algorithm   and   integer  linear 
       programming  (ILP)---and  study  whether  heuristic information
       improves them. We consider (i) time to certify optimality under
       explicit  safety  limits  and  (ii)  the best feasible solution
       available  after  a fixed solver budget. On small instances and
       on  the  $n  =  1000$ high-alphabet families ($K = 20$ and $K =
       36$),  the  cold  ILP  is  substantially  faster  than  the FPT
       algorithm  and  certifies optimality; the FPT also certifies on
       the small instances but frequently times out at $n = 1000$. The
       low-alphabet  $K = 4$ family is an important exception: the ILP
       formulation  becomes  very large, while the FPT algorithm finds
       better  feasible  solutions within the tested budget. Supplying
       only   a   valid  upper-bound  value  produces  no  practically 
       meaningful runtime gain in the tested configurations. Moreover,
       a  cost-only  FPT  seed  may  leave  no  materialized incumbent
       partition,  and  an  ILP  cutoff  may  leave the solver with no
       internal  incumbent,  although  the heuristic partition remains
       available  to  the  warm-start pipeline. Supplying the complete
       heuristic  partition as a MIP start to the CB model avoids this
       loss of information: on the tested $K = 4$ intergenic instance,
       the  incumbent  available  after the solver budget changes from
       $1234$  to  $864$  blocks,  while  the  reported optimality gap
       changes  from  about $50\%$ to $28\%$. The ILP does not improve
       upon  the  seeded partition within $300$~s; its contribution in
       this  experiment  is  to  provide a lower bound and certify the
       quality  of  the heuristic incumbent. Overall, the results show
       that  the  usefulness  of a warm start depends on both instance
       structure  and  the  information passed to the solver, and that
       the  FPT  and  ILP  approaches  are complementary on the tested
       benchmark.
  }
}