Sachverhalt:
A.
A._, 1985 geborener Staatsangehöriger von Somalia, reiste am 2. Mai 1995 zusammen mit seiner Mutter in die Schweiz ein. Das damalige Bundesamt für Flüchtlinge (BFF; heute: Staatssekretariat für Migration SEM) verfügte am 29. September 1995 die Wegweisung der Familie aus der Schweiz, lehnte das Asylgesuch ab und ordnete die vorläufige Aufnahme an.
Am 3. Juni 2009 hob das Bundesamt für Migration (heute SEM) die vorläufige Aufnahme von A._ auf und wies ihn aus der Schweiz weg. Auf eine hiergegen erhobene Beschwerde trat das Bundesverwaltungsgericht am 28. Juni 2009 nicht ein. Mit Urteil des Obergerichts des Kantons Bern vom 25. März 2011 wurde A._ wegen versuchter Tötung, mehrfach versuchter schwerer Körperverletzung und weiterer Delikte namentlich im Betäubungsmittelbereich zu einer Freiheitsstrafe von sechs Jahren verurteilt. Die Abteilung Straf- und Massnahmenvollzug im Amt für Freiheitsentzug lehnte die bedingte Entlassung am 10. Juli 2013 ab. A._ verbüsste seine Strafe bis zum ordentlichen Strafende am 12. September 2015.
B.
Mit Verfügung vom 14. September 2015 ordnete das Migrationsamt des Kantons Solothurn die Durchsetzungshaft per Strafende für einen Monat an. Das Haftgericht genehmigte mit Entscheid vom 16. September 2015 die angeordnete Durchsetzungshaft bis zum 11. Oktober 2015. Am 13. Oktober 2015 genehmige das Haftgericht die vom Migrationsamt beantragte Haftverlängerung bis zum 10. Dezember 2015. Die gegen die Haftbestätigungsentscheide beim Verwaltungsgericht des Kantons Solothurn erhobenen Beschwerden wurden vereinigt und am 16. November 2015 abgewiesen.
C.
Mit Beschwerde vom 29. Dezember 2015 beantragt A._ dem Bundesgericht, den Entscheid vom 16. November 2015 aufzuheben; er sei umgehend aus der Durchsetzungshaft zu entlassen. Der Beschwerdeführer verlangt eine Genugtuung für die seit dem 12. September 2015 ausgestandene Überhaft in der Höhe von mindestens Fr. 100.-- pro Tag. Er ersucht um unentgeltliche Rechtspflege und Verbeiständung.
Das Migrationsamt und das Verwaltungsgericht des Kantons Solothurn beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Haftgericht verzichtet auf eine Vernehmlassung. Das Staatssekretariat führt in seiner Stellungnahme aus, eine Rückkehr nach Somalia sei nur bei freiwilliger Ausreise möglich. Der Beschwerdeführer hält in einer weiteren Eingabe vom 21. Januar 2016 an seinen Anträgen fest.
Erwägungen:
1.
Gegen letztinstanzliche kantonale richterliche Entscheide betreffend die Zwangsmassnahmen im Ausländerrecht steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, soweit der Betroffene am vorinstanzlichen Verfahren teilgenommen hat, durch den angefochtenen Entscheid besonders berührt ist und an der Beurteilung seiner Eingabe ein aktuelles praktisches Interesse hat (Art. 86 Abs. 1 und 2, Art. 89 Abs. 1 BGG). Der Beschwerdeführer, der sich gestützt auf den hier angefochtenen Entscheid und einen mittlerweile ergangenen Haftverlängerungsentscheid vorerst bis zum 9. Februar 2016 in Haft befindet, hat ein Interesse an der Beurteilung der Beschwerde (BGE 139 I 206 E. 1 S. 208 ff.; Urteil 2C_1096/2015 vom 22. Dezember 2015 E.3). Ein Ausschlussgrund ist nicht ersichtlich (Art. 83 BGG). Auf die frist- und formgerecht eingereichte Beschwerde ist einzutreten.
2.
2.1. Hat eine ausländische Person ihre Pflicht zur Ausreise aus der Schweiz innerhalb der ihr angesetzten Frist nicht erfüllt und kann die rechtskräftige Weg- oder Ausweisung aufgrund ihres persönlichen Verhaltens nicht vollzogen werden, so darf sie in Durchsetzungshaft genommen werden, um der Ausreisepflicht Nachachtung zu verschaffen, sofern die Anordnung der Ausschaffungshaft nicht zulässig ist oder keine andere, mildere Massnahme zum Ziel führt (Art. 78 Abs. 1 AuG). Die Haft ist erstmals für einen Monat möglich; sie kann hernach mit der Zustimmung der zuständigen kantonalen gerichtlichen Behörde (vgl. Art. 78 Abs. 2 AuG) jeweils um zwei Monate verlängert werden, sofern die ausländische Person weiterhin nicht bereit ist, ihr Verhalten zu ändern und auszureisen. Die Haft wird gemäss Art. 78 Abs. 6 AuG beendet, wenn eine selbstständige und pflichtgemässe Ausreise nicht möglich ist, obwohl die betroffene Person den behördlich vorgegebenen Mitwirkungspflichten nachgekommen ist (lit. a), oder die Schweiz weisungsgemäss verlassen (lit. b), die Ausschaffungshaft angeordnet (lit. c) oder einem Haftentlassungsgesuch entsprochen wird (lit. d).
2.2. Zweck der Durchsetzungshaft ist es, die ausreisepflichtige Person in jenen Fällen zu einer Verhaltensänderung zu bewegen, in denen nach Ablauf der Ausreisefrist der Vollzug der rechtskräftig gegen sie angeordneten Weg- oder Ausweisung - trotz entsprechender behördlicher Bemühungen - ohne ihre Kooperation nicht (mehr) möglich erscheint (Art. 78 AuG). Der damit verbundene Freiheitsentzug stützt sich auf Art. 5 Ziff. 1 lit. f EMRK (Haft zur Sicherung eines schwebenden Ausweisungsverfahrens) und dient in diesem Rahmen der Erzwingung einer durch das Gesetz vorgeschriebenen Verpflichtung (Art. 5 Ziff. 1 lit. b EMRK). Die Durchsetzungshaft bildet das letzte Mittel, wenn und soweit keine andere Massnahme (mehr) zum Ziel führt, eine illegal anwesende ausländische Person auch gegen ihren Willen in ihre Heimat verbringen zu können. Sie darf - zusammen mit der bereits verbüssten Ausschaffungs- bzw. Vorbereitungshaft - maximal 18 Monate dauern (Art. 78 Abs. 2 i.V.m. Art. 79 AuG), muss aber in jedem Fall verhältnismässig sein. Innerhalb dieser Höchstdauer ist jeweils aufgrund der Umstände im Einzelfall zu prüfen, ob die ausländerrechtliche Festhaltung insgesamt (noch) geeignet bzw. erforderlich erscheint und nicht gegen das Übermassverbot, d.h. das sachgerechte und zumutbare Verhältnis von Mittel und Zweck, verstösst (vgl. BGE 140 II 409 E. 2.1 S. 411; 135 II 105 E. 2.2.1 S. 107; 134 II 201 E. 2 S. 204 ff.; 134 I 92 E. 2.3 S. 96 ff.; Urteile 2C_1182/2014 vom 20. Januar 2015 E. 3.3.1; 2C_639/2011 vom 16. September 2011 E. 3.1; 2C_624/2011 vom 12. September 2011 E. 2.1).
2.3. Bei dieser Beurteilung ist dem Verhalten des Betroffenen, den die Papierbeschaffung allenfalls erschwerenden objektiven Umständen (ehemalige Bürgerkriegsregion usw.) sowie dem Umfang der von den Behörden bereits getroffenen Abklärungen Rechnung zu tragen und zu berücksichtigen, wieweit der Ausländer es tatsächlich in der Hand hat, die Festhaltung zu beenden, indem er seiner Mitwirkungs- bzw. Ausreisepflicht nachkommt (BGE 134 I 92 E. 2.3.2 S. 97). Von Bedeutung können zudem seine familiären Verhältnisse sein sowie der Umstand, dass er allenfalls wegen seines Alters oder Gesundheitszustands als besonders schutzbedürftig gelten muss (BGE 134 II 201 E. 2.2.3 S. 205). Das mutmassliche künftige Verhalten des Betroffenen ist jeweils aufgrund sämtlicher Umstände abzuschätzen. Dabei kommt dem Haftgericht wegen der Unmittelbarkeit der Kontakte mit dem Betroffenen ein gewisser Beurteilungsspielraum zu. Je länger die ausländerrechtlich motivierte Festhaltung dauert und je weniger die Ausschaffung absehbar erscheint, desto strengere Anforderungen sind an die fortbestehende Hängigkeit des Ausweisungsverfahrens im Sinne von Art. 5 Ziff. 1 lit. f EMRK zu stellen und desto kritischer ist die jeweilige Haftverlängerung zu hinterfragen (vgl. BGE 135 II 105 E. 2.2.2 S. 107 f.; 134 II 201 E. 2 S. 204 ff.; 134 I 92 E. 2.3 S. 96 ff.; Urteile 2C_1182/2014 vom 20. Januar 2015 E. 3.3.3; 2C 639/2011 vom 16. September 2011 E. 3.1; 2C_624/2011 vom 12. September 2011 E. 2.1).
3.
3.1. Im vorliegenden Fall ist unbestritten, dass die gesetzlichen Haftvoraussetzungen von Art. 78 AuG grundsätzlich erfüllt sind und die maximale Haftdauer von 18 Monaten noch nicht erreicht ist. Der Beschwerdeführer macht indessen geltend, die Vorinstanz missachte den Verhältnismässigkeitsgrundsatz; sie habe darauf verzichtet, für seinen Fall eine Einzelfallprüfung vorzunehmen und sich mit den konkreten Umständen zu befassen.
3.2. Entgegen der Vorbringen liegt keine Verletzung von Art. 78 AuG und des Verhältnismässigkeitsgrundsatzes vor:
3.2.1. Der Beschwerdeführer macht geltend, eine freiwillige Ausreise sei ihm infolge Bürgerkriegs in seinem Herkunftsland nicht zumutbar. Er beruft sich in allgemeiner Weise auf die EMRK, äussert sich jedoch nicht weiter zur Unzumutbarkeit und der Situation in seinem Herkunftsland. Das Bundesamt legt in seiner Stellungnahme dar, eine freiwillige Ausreise nach Somalia sei möglich; zu einer ähnlichen Einschätzung kommt das Bundesverwaltungsgericht in einem Urteil von 2013 (BVGE 2013/27). Die Vorinstanz stellt ihrerseits fest, das Migrationsamt sei um einen Termin des Beschwerdeführers bei der somalischen Botschaft bemüht, und die somalische Botschaft sei "grundsätzlich bereit", ausreisepflichtige somalische Staatsangehörige zur freiwilligen Rückkehr zu bewegen. Die Vorinstanz durfte vor diesem Hintergrund davon ausgehen, der Beschwerdeführer könne seine Festhaltung verkürzen, indem er mit den Behörden kooperiere und freiwillig in sein Herkunftsland ausreise. Soweit es um die "Möglichkeit" der Ausreise geht (Art. 78 Abs. 6 lit. a AuG; vgl. hiervor E. 2.1), sind die Voraussetzungen der Durchsetzungshaft erfüllt.
3.2.2. Der Beschwerdeführer macht unter Bezugnahme auf sein bisheriges Verhalten geltend, er sei ohnehin nicht zu einer freiwilligen Rückkehr zu bewegen; eine fortgesetzte Haftdauer werde an seiner Einstellung nichts ändern.
Mit der Durchsetzungshaft soll nach Art. 78 Abs. 1 AuG der Ausreisepflicht Nachachtung verschafft werden. Typische Zielsetzung der Durchsetzungshaft ist demnach, durch eine Verhaltensänderung die Ausreisebereitschaft zu erlangen (vgl. hiervor E. 2.2). Insofern geht es bei der Überprüfung der Zulässigkeit der Durchsetzungshaft mit Blick auf den Haftzweck vor allem um die Frage, ob vernünftigerweise noch damit gerechnet werden kann, den Beschwerdeführer umstimmen zu können. Der Beschwerdeführer bringt zwar vor, sein gesamtes bisheriges Verhalten lasse nicht darauf schliessen, dass er auf diese Weise in seine Heimat zurückkehren werde. Die Vorinstanz stellt denn auch fest, dass sich der Beschwerdeführer bisher nicht darum bemüht habe, Reisepapiere für seine Rückkehr nach Somalia zu beantragen, obwohl dies prinzipiell möglich gewesen sei. Sie schliesst zum gegebenen Zeitpunkt indessen nicht aus, dass sich die Haltung des Beschwerdeführers mit der weiteren Haft noch ändern könnte. Dass die Vorinstanz den Haftzweck trotz der andauernden mangelhaften Kooperation nach rund zwei Monaten (heute dauert die Haft etwas mehr als vier Monate), somit in einer angesichts der maximal zulässigen Haftdauer von 18 Monaten frühen Phase der Durchsetzungshaft, als noch zu erreichen wertet, verletzt kein Bundesrecht (vgl. hiervor E. 2.3; vgl. Urteil 2C_630/2015 vom 7. August 2015 E. 2.2). Soweit der Beschwerdeführer seinen Standpunkt sodann mit einer fehlenden Fluchtgefahr unterlegen möchte, verkennt er den Zweck der Durchsetzungshaft, die ihn zu einer freiwilligen Ausreise bewegen soll.
3.3. Der Beschwerdeführer macht weiter geltend, er sei aus der Haft zu entlassen, um sich nunmehr in die Gesellschaft integrieren zu können. Er bringt vor, er fühle sich in der Schweiz heimisch und sei bereits seit 1995 im Land anwesend. Er wolle sich nunmehr um das von ihm anerkannte Kind kümmern. Sein in der Schweiz anwesenheitsberechtigter Bruder sei bereit, ihn bei sich aufzunehmen und auch finanziell zu unterstützen. In seinem Heimatland verfüge er über keine persönlichen Kontakte.
Das Verfahren vor dem Haftgericht dient nicht der Überprüfung des Wegweisungsentscheids oder von anderen zur Ausreise verpflichtenden Verfügungen; deren Rechtmässigkeit bildet nicht Gegenstand des Verfahrens (vgl. die Urteile 2C_218/2013 vom 26. März 2013 E. 3.2.2; 2C_168/2013 vom 7. März 2013 E. 1.3.1; 2C_749/2012 vom 28. August 2012 E. 2.1). Hinweise, dass der verfügte Wegweisungsentscheid geradezu willkürlich oder nichtig erscheint, ergeben sich vorliegend nicht (vgl. BGE 130 II 56 E. 2 S. 58; 128 II 193 E. 2.2.2 S. 198). Die Rügen zur Integration in die hiesige Gesellschaft und zu fehlenden Kontakten in seinem Herkunftsland sind demnach nicht einschlägig. Auch die Bereitschaft des Bruders, für den Beschwerdeführer aufzukommen, kann nicht hinreichend sicherstellen, dass das mit der Durchsetzungshaft bezweckte gesetzeskonforme Verhalten erreicht werden könnte. Es ergeben sich vorliegend weder Vorbringen noch Hinweise, dass der Beschwerdeführer nach dem langen Strafvollzug aus einer intakten Beziehung zu seinem Kind gerissen würde, und insbesondere ist nicht ersichtlich, inwiefern diese primär die Bewilligungsfrage betreffende familiäre Beziehung den besonderen Haftzweck infrage stellen sollte. Wie die Vorinstanz zurecht ausführt, ergeben sich sodann keine Hinweise, dass es sich beim Beschwerdeführer um eine besonders schutzbedürftige Person im Sinne der Rechtsprechung handle (vgl. hiervor E. 2.3). Aus den angerufenen persönlichen Umständen ergibt sich keine Rechtsverletzung durch die Vorinstanz.
4.
Nach dem Gesagten ist die Beschwerde abzuweisen. Die Anordnung und Verlängerung der Durchsetzungshaft war verhältnismässig. Ein Genugtuungsanspruch besteht aufgrund der rechtmässig angeordneten Durchsetzungshaft nicht.
5.
Der Beschwerdeführer ersucht um unentgeltliche Rechtspflege und Verbeiständung. Die Voraussetzungen nach Art. 64 BGG sind jedoch nicht erfüllt, da die Beschwerde aussichtslos ist. Umständehalber ist auf die Erhebung von Kosten zu verzichten (Art. 66 Abs. 1 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3.
Es werden keine Kosten erhoben.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 27. Januar 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Seiler
Die Gerichtsschreiberin: Hänni