Sachverhalt:
A.
Der Staatsangehörige von Nordmazedonien A.A._ (geboren 1983) heiratete am 12. September 2002 in Nordmazedonien die in der Schweiz niedergelassene B.A._ (geboren 1984), ebenfalls Staatsangehörige von Nordmazedonien. Im Rahmen des Familiennachzugs reiste er am 26. Januar 2003 in die Schweiz ein, wo ihm der Kanton Bern zunächst eine Aufenthaltsbewilligung erteilte. Seit dem 21. November 2007 ist A.A._ im Besitz einer Niederlassungsbewilligung, die letztmals von der Migrationsbehörde des Kantons Bern im Jahr 2013 bis am 30. November 2018 verlängert wurde. Der Ehe entstammen die in der Schweiz geborenen drei Söhne C.A._ (geboren 2003), D.A._ (geboren 2005) und E.A._ (geboren 2015). Während C.A._ und D.A._ ebenfalls im Besitz von Niederlassungsbewilligungen des Kantons Bern mit einer gültigen Kontrollfrist bis am 30. November 2018 sind, wurde E.A._ im Kanton Bern bisher keine Niederlassungsbewilligung erteilt. Per 1. September 2015 verlegte A.A._ mit seiner Familie den Wohnsitz von U._ (BE) nach V._ (SO) und ersuchte am 13. Oktober 2015 um Bewilligung des Kantonswechsel.
B.
A.A._ wurde während seines Aufenthalts in der Schweiz innert 13 Jahren (2005-2018) rund 30-mal strafrechtlich verurteilt. Insgesamt wurden gegen ihn Geldstrafen in der Höhe von 30 Tagessätzen zwischen Fr. 60.-- und 90.-- sowie Bussen ausgesprochen, welche zusammen Fr. 6'740.-- ausmachten. Das Regionalgericht Berner Jura-Seeland verurteilte A.A._ im November 2018 wegen versuchten Betrugs etc. zu einer Freiheitsstrafe von 20 Monaten, bedingt aufgeschoben beieiner Probezeit von zwei Jahren und einer Verbindungsbusse in der Höhe von Fr. 2'000.--. Gegen dieses Urteil wurde Berufung erhoben. Im Register des Betreibungsamtes Seeland vom 10. Dezember 2018 ist A.A._ mit fünf Betreibungen (davon vier mit Rechtsvorschlag) in der Höhe von Fr. 100'163.25 sowie 12 Verlustscheinen im Umfang von Fr. 24'430.60 verzeichnet. Im Register des Betreibungsamtes W._ vom 11. Juli 2019 liegen gegen A.A._ vier Verlustscheine in der Höhe von Fr. 14'250.75 vor. Gemäss den Sozialen Diensten der Stadt U._ erhielten der Beschwerdeführer und seine Familie bis am 28. Oktober 2015 Fr. 32'896.15 sozialrechtliche Unterstützung. Am neuen Wohnsitz hat er bis anhin keine Sozialhilfe bezogen.
C.
Mit Verfügung vom 13. März 2019 wies das Departement des Innern des Kantons Solothurn, vertreten durch das Migrationsamt (MISA), das Gesuch von A.A._ um Kantonswechsel ab und wies ihn mit Frist bis 31. Mai 2019 aus dem Kanton Solothurn weg. Das Gesuch um Kantonswechsel von B.A._ wurde bewilligt und ihr, sowie den drei Söhnen, eine Niederlassungsbewilligung im Kanton Solothurn erteilt. Die dagegen erhobene Beschwerde wurde vom Verwaltungsgericht des Kantons Solothurn mit Urteil vom 14. Januar 2020 teilweise gutgeheissen. Das Verwaltungsgericht stellte fest, dass das Departement des Innern in Bezug auf das Gesuch um Kantonswechsel vom 13. Oktober 2015 das Rechtsverzögerungsverbot verletzt hat. Im Übrigen wies es die Beschwerde ab.
D.
A.A._ gelangt mit subsidiärer Verfassungsbeschwerde vom 14. Februar 2020 an das Bundesgericht. Er beantragt, das Urteil des Verwaltungsgerichts sei, abgesehen von der Feststellung der Verletz ung des Rechtsverzögerungsverbots, aufzuheben, und sein Kantonswechselgesuch gutzuheissen. Eventualiter sei die Sache an die Vorinstanz beziehungsweise an den Beschwerdegegner mit der Anweisung, das Kantonswechselgesuch des Beschwerdeführers gutzuheissen, zurückzuweisen.
Das Departement des Innern des Kantons Solothurn und das Verwaltungsgericht des Kantons Solothurn beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Staatssekretariat für Migration (SEM) liess sich nicht vernehmen.
Mit Verfügung vom 18. Februar 2020 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.

Erwägungen:
1.
1.1. Gegen Entscheide über den Kantonswechsel ist gemäss <ref-law> die Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgeschlossen (vgl. Urteile 2D_16/2015 vom 29. Oktober 2015 E. 1.1.; 2D_37/2014 vom 9. Februar 2015 E. 1.1; 2D_19/2014 vom 2. Oktober 2014 E. 1.1). Der Beschwerdeführer erhebt daher zu Recht subsidiäre Verfassungsbeschwerde (<ref-law>).
1.2. Die Erhebung einer subsidiären Verfassungsbeschwerde erfordert ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids (<ref-law>; vgl. <ref-ruling> ff.). <ref-law> (SR 142.20; bis 31. Dezember 2018 und soweit im Folgenden die altrechtliche Fassung massgeblich ist: AuG) statuiert einen Anspruch von in der Schweiz niedergelassenen Personen auf einen Kantonswechsel, wenn keine Widerrufsgründe nach <ref-law> vorliegen. Ein rechtlich geschütztes Interesse des Beschwerdeführers an der Änderung des kantonalen Entscheids liegt damit vor.
Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde (Art. 117 und 100 Abs. 1 BGG; <ref-law>) gegen den kantonal letztin stanzlichen Entscheid des Verwaltungsgerichts (Art. 114 und 86 Abs. 1 lit. d und Abs. 2 BGG) ist einzutreten.
Da der Beschwerde aufschiebende Wirkung zuerkannt wurde, ist es dem Beschwerdeführer während des Verfahrens vor Bundesgericht weiterhin gestattet, sich im Kanton Solothurn aufzuhalten und niederzulassen. Die diesbezüglich beantragte vorsorgliche Massnahme ist gegenstandslos.
1.3. Mit subsidiärer Verfassungsbeschwerde kann nur die Verletzung von verfassungsmässigen Rechten gerügt werden (<ref-law>). Der Beschwerdeführer muss angeben, welches verfassungsmässige Recht verletzt wurde, und substanziiert darlegen, worin die Verletzung besteht; appellatorische Kritik und blosse Ausführungen zur eigenen Sichtweise genügen nicht (vgl. <ref-ruling> E. 1.3 S. 60; <ref-ruling> E. 3 S. 352; <ref-ruling> E. 1.4.2 S. 254).
1.4. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann davon nur abweichen, wenn die Sachverhaltsfeststellung unter Verletzung eines verfassungsmässigen Rechts zustande kam (Art. 118 Abs. 2 und <ref-law>), was die Beschwerdeführerin präzise geltend zu machen hat (Art. 117 i.V.m. <ref-law>; <ref-ruling> E. 3.2 S. 445).
1.5. Der Beschwerdeführer behauptet, dass seine Schulden nach Rückzahlungen mittlerweile nur noch Fr. 14'000.-- betragen würden. Er belegt aber nicht weiter, dass der Sachverhalt in dieser Hinsicht willkürlich festgestellt worden wäre. Soweit diese Rückzahlungen nach dem vorinstanzlichen Urteil erfolgt sind, würde es sich dabei zudem um unzulässige Noven handeln, welche im bundesgerichtlichen Verfahren in jedem Fall unberücksichtigt bleiben (vgl. <ref-ruling> E. 3.1.2 S. 123; 133 IV E. 2.1 S. 343 f.; je mit Hinweisen).
2.
Der Beschwerdeführer rügt vorab eine Verletzung von <ref-law>.
2.1. Jede Person hat in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf Beurteilung innert angemessener Frist (<ref-law>; <ref-ruling> E. 2.2 S. 177 f.). Wie die Vorinstanz in Ziff. 1 des Dispositivs ihres Entscheides vom 14. Januar 2020 festgestellt hat, hat das Departement des Innern in Bezug auf das Gesuch um Kantonswechsel des Beschwerdeführers vom 13. Oktober 2015 das Rechtsverzögerungsverbot verletzt. Der Beschwerdeführer ist jedoch der Auffassung, dass mit der Feststellung der Rechtsverzögerung die erlittenen Nachteile nicht beseitigt und sein verfassungsmässiges Recht verletzt worden sei. Die Vorinstanz habe sich auf die drei Monate vor Erlass der erstinstanzlichen Verfügung eingetretenen Bestimmungen des AIG abgestellt, obschon bei Einreichung des Gesuches um Kantonswechsel am 13. Oktober 2015 noch über drei Jahre lang das AuG massgebend gewesen sei, welches für den Beschwerdeführer günstiger gewesen sei. So wäre zum Beispiel ein Widerruf gestützt auf Art. 63 Abs. 1 lit. a i.V.m. <ref-law> (falsche Angaben wesentlicher Tatsachen) unter dem AuG nicht möglich gewesen, da Art. 63 Abs. 2 AuG vorgesehen habe, dass ein Widerruf von Niederlassungsbewilligungen von Ausländern, die sich seit mehr als 15 Jahren ununterbrochen und ordnungsgemässs in der Schweiz aufhalten, nur aus Gründen von Art. 63 Abs. 1 lit. b und Art. 62 Abs. 1 lit. b AuG widerrufen werden könne.
2.2. Gemäss bundesgerichtlicher Rechtsprechung ist die Rechtmässigkeit von Verwaltungsakten mangels einer anderslautenden übergangsrechtlichen Regelung grundsätzlich nach der Rechtslage im Zeitpunkt ihres Ergehens zu beurteilen (vgl. <ref-ruling> E. 11.1 S. 259; <ref-ruling> E. 7c S. 315 f.; <ref-ruling> E. 2a S. 434; Urteil 2C_1134/2018 vom 11. Juni 2019 E. 2.1). Massgebend ist im Grundsatz folglich das zum Zeitpunkt der erstmaligen verwaltungsrechtlichen Beurteilung in Kraft stehende Recht. Tritt während des erstinstanzlichen Verfahrens eine Rechtsänderung ein, ist diese grundsätzlich zu berücksichtigen, auch wenn sich dies ungünstig auf den Betroffenen auswirkt (TSCHANNEN/ZIMMERLI/MÜLLER, Allgemeines Verwaltungsrecht, 4. Aufl. 2014, § 24 Rz. 20). Es geht jedoch nach rechtsstaatlichen Erwägungen nicht an, einen Privaten die Nachteile einer neuen Ordnung tragen zu lassen, wenn die von der Behörde zu verantwortende ungebührlich lange Verfahrensdauer zur Folge hatte, dass das neue Recht noch vor dem Entscheid in Kraft treten konnte. Würde in einem solchen Fall die Anwendung des neuen Rechts zu einer Benachteiligung des Privaten und zu einem Vorteil des Kantons führen, muss dies zur Folge haben, dass das alte Recht anzuwenden ist (<ref-ruling> E. 3a S. 337).
2.3. Dementsprechend wären auf das Gesuch des Beschwerdeführers die alten Bestimmungen des AuG zur Anwendung gelangt. Im vorliegenden Fall ergibt sich dies auch bereits aus der Übergangsbestimmung von <ref-law>, wonach auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, mangels besonderer Übergangsbestimmungen das bisherige Recht anwendbar bleibt (Urteile 2C_496/2019 vom 13. November 2019 E. 4; 2C_184/2018 vom 16. August 2018 E. 2.1; 2C_167/2018 vom 9. August 2018 E. 2.). Überdies ist Art. 80 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) anzuwenden, obwohl <ref-law> in der neuen Fassung vom 15. August 2018 (in Kraft seit 1. Januar 2019 [vgl. AS 2018 3173 ff., S. 3180 und S. 3187]) inhaltlich mit <ref-law> übereinstimmt.
2.4. Ob die Voraussetzungen für den Widerruf der Niederlassungsbewilligung aufgrund der falschen Angabe wesentlicher Tatsachen wie vom Beschwerdeführer vorgebracht aufgrund von Art. 63 Abs. 2 AuG nicht erfüllt sind, kann jedoch vorerst offenbleiben. Die Vorinstanz stützte sich nämlich primär auf den Widerrufsgrund der Gefährdung der öffentlichen Ordnung und Sicherheit gemäss <ref-law>, welcher inhaltlich mit der Regelung des AuG übereinstimmt. Erweist sich die Argumentation der Vorinstanz zur Verweigerung des Kantonswechsels in dieser Hinsicht als verfassungskonform, erwächst dem Beschwerdeführer kein Nachteil aus der auf der festgestellten Rechtsverzögerung resultierenden Anwendung neuen statt alten Rechts.
3.
Der Beschwerdeführer beanstandet, die Vorinstanz sei hinsichtlich des Widerrufsgrunds nach <ref-law> in Verletzung des Willkürverbots (<ref-law>) zum Schluss gelangt, dass ein solcher bestehe.
3.1. Willkür liegt nach der Rechtsprechung nicht schon dann vor, wenn eine andere Lösung ebenfalls vertretbar erscheint oder sogar vorzuziehen wäre. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.2.2 S. 318 f. mit Hinweisen). Dies ist insbesondere dann der Fall, wenn die Vorinstanz offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (<ref-ruling> E. 2.1 S. 9; Urteil 2C_630/2014 vom 24. Oktober 2014 E. 3.2). Dabei genügt es nicht, wenn sich nur die Begründung des angefochtenen Entscheides als unhaltbar erweist. Eine Aufhebung rechtfertigt sich nur dann, wenn der Entscheid auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 2.2.2 S. 318 f. mit Hinweisen; Urteil 2D_16/2015 vom 25. Oktober 2015 E. 3.1).
3.2. Gemäss Art. 37 Abs. 3 AuG haben Personen mit Niederlassungsbewilligung Anspruch auf einen Kantonswechsel, wenn keine Widerrufsgründe nach Art. 63 AuG vorliegen. Die Bewilligung kann im neuen Kanton nicht allein mit der Begründung verweigert werden, dass der Gesuchssteller im bisherigen Bewilligungskanton verbleiben könne. Vielmehr muss ein Widerrufsgrund gegeben sein, der eine Wegweisung aus der Schweiz rechtfertigen würde. Vom neuen Kanton ist deshalb zu prüfen, ob ein Widerrufsgrund gegeben ist und eine Wegweisung aus der Schweiz verhältnismässig wäre (Urteile 2D_16/2015 vom 25. Oktober 2015 E. 3.2; 2D_19/2014 vom 2. Oktober 2014 E. 3.2). Es handelt sich dabei um eine hypothetische Frage.
3.3. Die Niederlassungsbewilligung kann nach Art. 63 Abs. 1 lit. b AuG widerrufen werden, wenn der Ausländer in schwerwiegender Weise gegen die öffentliche Sicherheit und Ordnung in der Schweiz oder im Ausland verstossen hat oder diese gefährdet oder die innere oder die äussere Sicherheit gefährdet. Dieser Widerrufsgrund gilt auch, wenn sich der Betroffene - wie hier - mehr als 15 Jahre ununterbrochen und ordnungsgemäss in der Schweiz aufgehalten hat (Art. 63 Abs. 2 AuG; <ref-ruling> E. 2.1 S. 19). Der Widerruf muss verhältnismässig sein (Art. 96 Abs. 1 AuG), was sich bei Ausländern, die sich auf Art. 8 EMRK berufen können, auch aus dessen Ziff. 2 ergibt (<ref-ruling> E. 2.2 S. 147 f.).
3.4. Im Rahmen von Art. 63 Abs. 1 lit. b AuG muss, anders als beim Widerrufsgrund von Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b AuG, nicht eine Verurteilung zu einer längerfristigen Freiheitsstrafe (d.h. zu einer Strafe von mindestens einem Jahr, <ref-ruling> E. 2.1 S. 299; <ref-ruling> E. 4.2 und E. 4.5 S. 379 ff.) vorliegen. Ein schwerwiegender Verstoss gegen die öffentliche Sicherheit und Ordnung besteht in erster Linie, wenn die ausländische Person durch ihre Handlungen besonders hochwertige Rechtsgüter wie namentlich die körperliche, psychische und sexuelle Integrität eines Menschen verletzt oder gefährdet hat. Indes können auch vergleichsweise weniger gravierende Pflichtverletzungen als "schwerwiegend" im Sinne von Art. 63 Abs. 1 lit. b AuG bezeichnet werden: So ist ein Widerruf der Niederlassungsbewilligung namentlich auch dann möglich, wenn sich eine ausländische Person von strafrechtlichen Massnahmen bzw. ausländerrechtlichen Verwarnungen nicht beeindrucken lässt und damit zeigt, dass sie auch zukünftig weder gewillt noch fähig ist, sich an die Rechtsordnung zu halten (<ref-ruling> E. 2.1 S. 19, 137 II 297 E. 3.3 S. 303; Urteil 2C_881/2012 vom 16. Januar 2013 E. 4.3.1). Somit kann auch eine Summierung von Verstössen, die für sich genommen für einen Widerruf nicht ausreichen würden, einen Bewilligungsentzug rechtfertigen, wobei nicht die Schwere der verhängten Strafen, sondern die Vielzahl der Delikte entscheidend ist (Urteil 2C_160/2013 vom 15. November 2013 E. 2.1.1). Auch das Nichterfüllen von öffentlich-rechtlichen oder privatrechtlichen Verpflichtungen kann gegebenenfalls einen schwerwiegenden Verstoss gegen die öffentliche Sicherheit und Ordnung darstellen, wenn die Verschuldung mutwillig erfolgt ist (<ref-law>; Urteil 2C_699/2014 vom 1. Dezember 2014 E. 3.2; Urteil 2C_160/2013 vom 15. November 2013 E. 2.1.1).
3.5. Der Widerruf der Bewilligung rechtfertigt sich nur, wenn die jeweils im Einzelfall vorzunehmende Interessenabwägung die entsprechende Massnahme als verhältnismässig erscheinen lässt (vgl. Art. 96 Abs. 1 AuG). Die Notwendigkeit einer Verhältnismässigkeitsprüfung ergibt sich auch aus Art. 8 Ziff. 2 EMRK: Danach ist ein Eingriff in das von Art. 8 Ziff. 1 EMRK geschützte Familienleben dann statthaft, wenn er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung oder zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesundheit und Moral sowie der Rechte und Freiheiten anderer notwendig erscheint. Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die primär betroffene Person sowie deren familiäre Situation zu berücksichtigen. Zudem sind die Dauer der ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (Geburt und Alter allfälliger Kinder; Kenntnis der Tatsache, dass die Beziehung wegen der Straftat unter Umständen nicht in der Schweiz gelebt werden kann). Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimat folgen (<ref-ruling> E. 2.2.2 S. 20 f., 139 I 31 E. 2.3.3 S. 34 ff.; 135 II 477 E. 4.3 S. 381 f.).
4.
Während im erstinstanzlichen Entscheid auch die finanzielle Situation des Beschwerdeführers zur Begründung des Widerrufsgrundes nach Art. 63 Abs. 1 lit. b AuG herbeigezogen wurde, beschränkte sich die Vorinstanz alleine auf die strafrechtlichen Massnahmen. Ebenfalls nicht in die Beurteilung floss das Urteil des Regionalgerichtes Berner Jura-Seeland vom November 2018 ein, da gegen dieses Urteil Berufung erhoben wurde und es noch nicht rechtskräftig ist.
4.1. Die Vorinstanz führte aus, dass der Beschwerdeführer in 13 Jahren (2005-2018) rund 30-Mal strafrechtlich belangt worden sei. Zwar habe es sich dabei auch um blosse Bagatelldelikte wie Überschreiten der Parkzeit, Einstellen falscher Ankunfstzeit, Falschparken usw. gehandelt, aber nicht ausschliesslich. Der Beschwerdeführer sei wiederholt wegen Telefonierens ohne Freisprechanlage sowie wiederholtem Nichtabgeben entzogener Fahrzeugausweise und Kontrollschilder trotz behördlicher Aufforderung belangt worden. Im Weiteren verurteilte ihn das Gerichtspräsidium Baden am 17. Januar 2012 zu einer Busse von Fr. 300.-- weil er auf der Autostrasse trotz doppelter Sicherheitslinie wendete und seine Fahrt Richtung Autobahneinfahrt fortsetzte. Am 11. März 2017 verurteilte die Staatsanwaltschaft des Kantons Basel-Landschaft den Beschwerdeführer zu einer Busse von Fr. 400.-- weil er wegen ungenügenden Abstands eine Auffahrkollision mit dem vor ihm verkehrsbedingt bis zum Stillstand abgebremsten Personenwagen verursacht hatte. Mit Strafbefehl der Staatsanwaltschaft Solothurn vom 12. April 2018 wurde der Beschwerdeführer unter anderem zu einer Busse von Fr. 300.-- verurteilt, weil er während der Fahrt sein Mobiltelefon auf Höhe des Lenkrades in der Hand gehalten und bedient hatte, mit Blick auf das Display, was einen Schwenker innerhalb der Fahrspur zur Folge hatte. Gestützt auf diese Verurteilungen gelangte die Vorinstanz zum Schluss, dass das Verhalten des Beschwerdeführers eine Gefahr für die anderen Verkehrsteilnehmer bilde. Gegen den Beschwerdeführer wurden Geldstrafen in der Höhe von 30 Tagessätzen zwischen Fr. 60.-- und 90.-- sowie Bussen ausgesprochen, welche zusammen insgesamt Fr. 6'740.-- ausmachten. Aus dem über Jahre hinweg unveränderten Verhalten könne geschlossen werden, dass der Beschwerdeführer offenbar nicht gewillt oder fähig ist, sein Verhalten anzupassen und die hiesige Rechtsordnung vollumfänglich zu respektieren.
4.2. Der Beschwerdeführer erblickt in der Schlussfolgerung der Vorinstanz eine willkürliche Anwendung von Art. 63 Abs. 1 lit. b i.V.m. <ref-law>. Entgegen der Annahme der Vorinstanz stelle sein Verhalten keine schwerwiegende Gefahr für die öffentliche Ordnung und Sicherheit dar. Vielmehr habe die Vorinstanz jede Busse, selbst solche in der Höhe von Fr. 20.--, aufgelistet. Seit seiner Anwesenheit in der Schweiz habe er in gut 15 Jahren insgesamt 27 Bussen und drei kleine Geldstrafen mit Tagessätzen zwischen fünf und 15 Tagen erwirkt. Das ergebe pro Jahr zwei Bussen im Strassenverkehr, wovon die überwiegende Mehrheit nicht mehr als Fr. 40.-- betragen und Bagatellen betreffen würden. Zudem habe er sämtliche Bussen und Geldstrafen stets bezahlt. Darüber hinaus handle es sich bei einer Vielzahl der Bussen um solche, die seit dem Inkrafttreten des Ordnungsbussengesetzes in jenem Verfahren erledigt würden. Ordnungsbussen würden nie ins Strafregister eingetragen und es dürfe gemäss <ref-law> in keinem Fall ein Administrativverfahren stattfinden, wenn eine Übertretung im Ordnungsbussenverfahren erledigt werde. Solche Übertretung dürften dementsprechend auch nicht in einem ausländerrechtlichen Verfahren herangezogen werden, um eine ausländerrechtliche Massnahme zu rechtfertigen. Es sei zudem willkürlich ihm Bussen entgegenzuhalten, die nie im schweizerischen Strafregister eingetragen worden seien.
4.3. Vorab zählen auch Strafbefehle zu den strafrechtlichen Urteilen, welche die Polizei- und Gerichtsbehörden sowie die Strafuntersuchungsbehörden unaufgefordert den kantonalen Ausländerbehörden melden, wenn Ausländer davon betroffen sind (Art. 97 Abs. 3 AuG i.V.m. <ref-law>) und dürfen von diesen verwendet werden (Urteil 2C_886/2008 vom 4. Mai 2009 E. 5). Aber auch unter Berücksichtigung sämtlicher strafrechtlicher Verurteilungen fällt auf, dass die gegen den Beschwerdeführer ausgesprochenen Strafen im Vergleich mit der Rechtsprechung des Bundesgerichts (für eine exemplarische Übersicht vgl. Urteil 2C_39/2016 vom 31. August 2016 E. 2.3) eher tief ausgefallen sind. So verneinte das Bundesgericht in <ref-ruling> die Voraussetzungen von Art. 63 Abs. 1 lit. b AuG (im Zusammenhang mit Art. 51 Abs. 1 lit. b AuG) im Falle eines als Erwachsener in die Schweiz eingereisten Ausländers, der in einem Zeitraum von etwa zehn Jahren 16 Mal zu Freiheitsstrafen von insgesamt rund 33 Monaten wegen Vermögensdelikten sowie Widerhandlungen gegen aufenthaltsrechtliche Bestimmungen verurteilt worden war, wobei die Vermögensdelikte schon relativ weit zurücklagen und vergleichsweise tiefe Strafen nach sich gezogen hatten.
Hingegen bejahte das Bundesgericht den Widerrufsgrund im Falle eines ausländischen Staatsbürgers, der in einem Zeitraum von 16 Jahren 18 Mal zu Freiheitsstrafen von insgesamt 116 Tagen, Geldstrafen von 50 Tagessätzen zu Fr. 50.-- und 20 Tagessätzen zu Fr. 60.-- und verschiedenen Bussen bis Fr. 4'180.-- wegen Verkehrs- und Betreibungsdelikten, Veruntreuung und Vernachlässigung von Unterstützungspflichten verurteilt worden war (Urteil 2C_699/2014 vom 1. Dezember 2014). Gegen den Betreffenden lagen Verlustscheine in der Höhe von fast Fr. 300'000.-- vor. Das Bundesgericht betrachtete den Fall als Grenzf all (E. 4.3).
Verneint wurde hingegen der Widerruf im Falle eines seit seinem achten Lebensjahr in der Schweiz lebenden Ausländers, welcher zwar als Minder jähriger verschiedene Gewaltdelikte begangen hatte, jedoch als Erwachsener nur zwei Mal zu Geldstrafen wegen SVG-Delikten und Vergehen gegen das Waffengesetz verurteilt worden war. Da der Betroffene nie ausländerrechtlich verwarnt worden war, erwies sich der Widerruf der Niederlassung als unverhältnismässig (Urteil 2C_446/2014 vom 5. März 2015).
4.4. Der Beschwerdeführer hat bei seinen Delikten keine hochwertigen Rechtsgüter verletzt und auch das Fehlverhalten im Strassenverkehr begründete keine extreme Gefahr für die anderen Verkehrsteilnehmer wie bei massiven Überschreitungen der zulässigen Höchstgeschwindigkeit, ohne damit die Verstösse verharmlosen zu wollen. Es ist nicht von der Hand zu weisen, dass die Bedienung eines Mobiltelefons während der Fahrt sehr gefährlich sein kann. Die bereits rechtskräftig beurteilten Vergehen des Beschwerdeführer treten jedoch mehr durch ihre Regelmässigkeit als durch eine Gefährdung anderer Personen hervor.
Hinsichtlich der finanziellen Situation des Beschwerdeführers fällt auf, dass gegen ihn zwar Verlustscheine in Umfang von fast Fr. 40'000.-- bestehen, eine mutwillige Verschuldung als Voraussetzung eines schweren Verstosses gegen die öffentliche Ordnung und Sicherheit (E. 3.4 in fine) wurde ihm von der Vorinstanz jedoch nicht nachgewiesen. Eine solche ist ohnehin nicht leichthin anzunehmen und die Höhe der Verlustscheine befindet sich im Vergleich zu früheren Fällen deutlich unter den dort genannten Beträgen (vgl. Urteile 2C_928/2019 vom 26. Februar 2020 E. 3; 2C_62/2019 vom 14. Februar 2020 E. 3.1.2). Eine vorgängige Verwarnung wegen seiner Schulden ist dem Beschwerdeführer gegenüber ebenfalls nicht ausgesprochen worden, nur seine Ehefrau wurde im Rahmen des Kantonswechsel ermahnt. Die Vorinstanz liess die finanzielle Situation des Beschwerdeführers, wie eingangs erwähnt offen (E. 4). Das Verwaltungsgericht verwendete die finanzielle Situation im Gegensatz zum Departement des Innern explizit nicht zur Begründung der Verweigerung des Kantonswechsels.
4.5. Im Vergleich mit der bestehenden bundesgerichtlichen Rechtsprechung reichten ähnlich gelagerte Konstellationen nicht aus, um eine Niederlassungsbewilligung zu widerrufen und in Anbetracht der gesamten Umstände ist es zweifelhaft, ob ein Widerrufsgrund vorliegt. Das Bundesgericht weicht vom Entscheid der kantonalen Instanz jedoch nur ab, wenn dieser offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 2.2.2 S. 318 f. mit Hinweisen). Dies ist insbesondere dann der Fall, wenn die Vorinstanz offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (<ref-ruling> E. 2.1 S. 9; Urteil 2D_16/2015 vom 29. Oktober 2015 E. 3.1). Diese Voraussetzungen sind vorliegend nicht erfüllt. Zwar hätte der Entscheid hinsichtlich des Bestehens eines Widerrufsgrunds durchaus - oder gar eher - anders ausfallen können und die Erwägungen der Vorinstanz, wonach der Beschwerdeführer in schwerwiegender Weise die öffentliche Ordnung und Sicherheit in der Schweiz gefährdet, begnügten sich mit schematischen Wiederholungen der Rechtsprechung ohne die Umstände des Einzelfalls miteinzubeziehen. Dennoch ist die Erkenntnis der Vorinstanz nicht geradezu abwegig und sie hat nicht in willkürlicher Weise den Widerrufsgrund von Art. 63 Abs. 1 lit. b AuG als erfüllt erachtet.
5.
Der Beschwerdeführer bringt ebenfalls vor, ein Entzug seiner Niederlassungsbewilligung wäre auch aufgrund einer offensichtlichen Unverhältnismässigkeit willkürlich.
5.1. Der Widerruf der Niederlassungsbewilligung soll nur verfügt werden, wenn er nach den gesamten Umständen angemessen und verhältnismässig erscheint (<ref-ruling> E. 2.2.2 S. 20). Bei der entsprechenden Interessenabwägung sind insbesondere die Schwere des Fehlverhaltens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile zu berücksichtigen (vgl. E. 3.5).
Gemäss Art. 96 Abs. 2 AuG können Ausländer unter Androhung einer Massnahme verwarnt werden, wenn diese begründet, aber nach den Umständen nicht angemessen ist. Eine Verwarnung muss einem Bewilligungswiderruf nicht zwingend vorangehen. Rechtsprechungsgemäss kann eine einzelne Verurteilung wegen einer besonders schweren Straftat den Widerruf der Niederlassung rechtfertigen, ohne dass zuvoreine Verwarnung ausgesprochen wird. Die bundesgerichtliche Praxis ten diert jedoch dahin, bei einem langfristigen Aufenthalt und wenn es nicht um schwere Delinquenz geht, eher zu verlangen, dass der Ausländer vorab verwarnt wird (Urteile 2C_446/2014 vom 5. März 2015 E. 4.1; 2C_283/2011 vom 30. Juli 2011 E. 2.3 mit Hinweisen).
5.2. Die Vorinstanz hat erwogen, dass sich der Beschwerdeführer seit rund 17 Jahren in der Schweiz aufhält, die prägenden Kinder- und Jugendjahre habe er jedoch in seinem Heimatland verbracht, in welchem er bis kurz vor seinem 20. Geburtstag lebte. Seine Gattin stammt ebenfalls aus Nordmazedonien und sowohl der Beschwerdeführer als auch seine Ehefrau sind mit der Sprache, den Verhältnissen und Gebräuchen in ihrer Heimat bestens vertraut. Die drei Kinder des Beschwerdeführers sind zwar in der Schweiz geboren, dürften jedoch durch ihre Eltern hinreichend mit der Sprache und Gepflogenheiten vertraut sein und verfügen über die Staatsangehörigkeit Nordmazedoniens. Gemäss verbindlicher Sachverhaltsfeststellung durch die Vorinstanz besteht beruflich keine gelungene Integration, da der Beschwerdeführer wiederholt arbeitslos war. Seine beruflichen Möglichkeiten in Nordmazedonien seien beschränkter als in der Schweiz, jedoch lasse der Umstand, dass die wirtschaftlichen Verhältnisse in der Schweiz besser seien eine Ausreise nicht als unzumutbar erscheinen. Insgesamt stünden seiner sozialen und wirtschaftlichen Wiedereingliederung in seinem Heimatland keine unüberwindbaren Hindernisse entgegen. Eine Rückkehr sei dem Beschwerdeführer trotz seines langen Aufenthalts in der Schweiz zumutbar, nachdem er über Jahre hinweg nicht im Stande gewesen sei, sich an die hiesige Rechtsordnung zu halten. Trotz wiederholter strafrechtlicher Sanktionen habe er sich in keiner Weise darum gekümmert, weitere Gesetzesverstösse zu vermeiden.
5.3. Der Beschwerdeführer erachtet die Interessenabwägung der Vorinstanz als willkürlich. Sie habe seine lange Anwesenheit ungenügend berücksichtigt, der Entzug der Niederlassungsbewilligung wäre nur unter strengen Anforderungen möglich. Im Weiteren sei das Kindswohl gemäss Übereinkommen vom 20. November 1989 über die Rechte der Kinder (UN-Kinderrechtskonvention, KRK, SR 0.107) nicht gewürdigt worden, welches stark beeinträchtigt wäre, wenn er die Schweiz verlassen müsste. Hinzu komme, dass das Interesse an einer Wegweisung vorliegend aufgrund der doch eher geringfügigen Delikte seine gewichtigen privaten Interessen nicht überwiegen. Er habe regelmässig gearbeitet, seine Ehefrau sei im Arbeitsmarkt integriert und seine drei Kinder seien in der Schweiz aufgewachsen. Sein ganzes Erwachsenenleben habe er in der Schweiz verbracht und es sei absolut unverhältnismässig aufgrund von Bussen darauf zu schliessen, dass er eine solche Gefahr für die öffentliche Ordnung und Sicherheit darstelle, die eine aufenthaltsbeendende Massnahme rechtfertigen würde. Es wäre viel angemessener und verhältnismässiger gewesen gegen ihn eine Verwarnung auszusprechen. Die Verhältnismässigkeitsprüfung der Vorinstanz sei folglich unvollständig, lasse wichtige Aspekte aus und gewichte die auf dem Spiel stehenden Interessen vollkommen falsch.
5.4. Dem Beschwerdeführer ist zuzustimmen. Mangels schwerer Delinquenz und mutwilliger Schuldenwirtschaft ist es bereits zweifelhaft, ob der Widerrufsgrund gemäss Art. 63 Abs. 1 lit. b AuG überhaupt erfüllt ist (vgl. E 4.5 vorne). Dementsprechend hätte die Vorinstanz zumindest die Möglichkeit einer Verwarnung als milderes Mittel anstelle des Widerrufs prüfen müssen, um den offensichtlich gewichtigen Interessen des Beschwerdeführers an einem Verbleib - er hält sich seit über 15 Jahren ordnungsgemäss mit seiner Familie in der Schweiz auf - gerecht zu werden. Den Aspekt der fehlenden vorgängigen ausländerrechtlichen Verwarnung des Beschwerdeführers hat sie dabei gänzlich unbeachtet gelassen. Unter diesen Umständen erweist sich die Verhältnismässigkeitsprüfung als eindeutig unvollständig und das Ergebnis, wonach eine Wegweisung aus der Schweiz gestützt auf Art. 63 Abs. 1 lit. b AuG gerechtfertigt wäre, ist offensichtlich unhaltbar und verletzt <ref-law>.
6.
Wie bereits erwähnt (vgl. E. 2.4 oben), ging die Vorinstanz davon aus, dass in Ergänzung zum Widerrufsgrund von Art. 63 Abs. 1 lit. b AuG auch derjenige der falschen Angabe wesentlicher Tatsachen erfüllt sei. Der Beschwerdeführer ist der Ansicht, dieser Widerrufsgrund sei aufgrund der festgestellten Rechtsverzögerung und des deshalb anwendbaren alten, für ihn günstigeren, Rechts ohnehin nicht massgebend. Gemäss Art. 63 Abs. 2 AuG könne ihm die Niederlassungsbewilligung nicht entzogen werden, da er sich bereits seit mehr als 15 Jahren unu nterbrochen und ordnungsgemäss in der Schweiz aufhalte.
Ungeachtet davon, ob sich die Vorinstanz aufgrund der festgestellten Rechtsverzögerung vorliegend überhaupt noch auf den Widerrufsgrund der falschen Angaben wesentlicher Tatsache berufen konnte, sind dessen Voraussetzungen ohnehin nicht erfüllt. Das Verschweigen einer Tatsache ist nur dann relevant, wenn diese für den Widerruf der Bewilligung geeignet sein könnte (vgl. <ref-ruling> E. 4.1 S. 5). Solches ist, wie soeben gesehen, nicht der Fall. Die verschwiegenen strafrechtlichen Verurteilungen des Beschwerdeführers reichen nicht aus, um einen Entzug der Niederlassungsbewilligung zu rechtfertigen.
Dasselbe gilt auch hinsichtlich des Vorwurfs der Vorinstanz an den Beschwerdeführer, er habe wahrheitswidrige Angaben zu seiner Wohnsituation gemacht. Anstatt in ein Eigenheim zu ziehen, lebe er jetzt in einer Mietwohnung. Es ist jedoch nicht ersichtlich, aus welchen Gründen diese Tatsache für den Bewilligungsentscheid von Bedeutung sein sollte, und eine diesbezüglich falsche Angabe von Tatsachen kann nicht die Verweigerung der Bewilligung zur Folge haben.
7.
Das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 14. Januar 2020 ist somit aufzuheben und das Departement des Innern des Kantons Solothurn anzuweisen, d as Kantonswechselgesuch des Beschwerdeführers gutzuheissen.
Die Sache ist der Vorinstanz zur Neuverlegung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens zurückzuweisen (Art. 67BGG). Diesem Verfahrensausgang entsprechend sind keine Gerichtskosten zu erheben (<ref-law>). Der Kanton Solothurn hat dem Beschwerdeführer eine Parteientschädigung für das bundesgerichtliche Verfahren auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die subsidiäre Verfassungsbeschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 14. Januar 2020 wird aufgehoben.
2.
Das Departement des Innern des Kantons Solothurn wird angewiesen, dem Beschwerdeführer den Kantonswechsel zu bewilligen.
3.
Die Sache wird zur Neuverlegung der Kosten- und Entschädigungsfolgen des vorinstanzlichen Verfahrens an das Verwaltungsgericht des Kantons Solothurn zurückgewiesen.
4.
Es werden keine Gerichtskosten erhoben.
5.
Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
6.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 9. Juli 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Mösching