Sachverhalt:
A.
A._, geboren 1981, meldete sich im April 2013 bei der Invalidenversicherung zum Leistungsbezug an. Der behandelnde Psychiater, med. pract. B._, Facharzt für Psychiatrie und Psychotherapie, diagnostizierte am 9. Oktober 2013 eine paranoide Schizophrenie (ICD-10: F 20.0). Die Psychiatrie C._ konnte am 4. November 2013 die Diagnose hingegen nicht bestätigen und verwies auf den Bericht der Neurologischen Praxis, Spital D._, vom 30. Oktober 2013. Mit Verfügung vom 10. September 2014 wies die IV-Stelle des Kantons Solothurn das Leistungsgesuch ab, da keine medizinische Diagnose vorliege, welche eine länger andauernde Arbeitsunfähigkeit zu begründen vermöge.
B.
Das Versicherungsgericht des Kantons Solothurn wies die dagegen erhobene Beschwerde gestützt auf das Gerichtsgutachten der Frau Dr. med. E._, Fachärztin für Psychiatrie und Psychotherapie, vom 13. November 2015 am 17. Februar 2016 ab (Ziff. 1), auferlegte der IV-Stelle die Kosten des Gerichtsgutachtens (Ziff. 4) sowie A._ die Gerichtskosten (Ziff. 3) und verzichtete auf die Zusprechung einer Parteientschädigung (Ziff. 2).
C.
A._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Antrag, es sei der vorinstanzliche Entscheid bezüglich Ziff. 2 und 3 aufzuheben, der IV-Stelle die Kosten des kantonalen Verfahrens aufzuerlegen und ihm eine Parteientschädigung in der Höhe von mindestens Fr. 3'474.35 zu Lasten der IV-Stelle zuzusprechen. Eventualiter sei die Sache an die Vorinstanz zur Festlegung der Höhe der Parteientschädigung und Kostenverteilung zurückzuweisen. Zudem ersucht er um unentgeltliche Rechtspflege.

Erwägungen:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Pflicht zur Begründung der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1 S. 236 mit Hinweisen).
2.
Der Versicherte macht geltend, ihm stehe nach <ref-law> eine Parteientschädigung zu, da seine Beschwerde bezüglich des gerügten unvollständig erstellten Sachverhalts erfolgreich gewesen sei, was zumindest ein teilweises Obsiegen darstelle. Es könne sich hier nicht anders verhalten, als wenn die Vorinstanz die Sache an die IV-Stelle zu weiteren Abklärungen zurückweise, was als vollständiges Obsiegen mit entsprechenden Entschädigungsfolgen seitens der versicherten Person gewertet werde. Es sei nicht nachvollziehbar, weshalb sein Anspruch auf Entschädigung nur deshalb entfallen soll, weil vorliegend die Vorinstanz selbst die weiteren Abklärungen vorgenommen habe. Zumindest habe er Anspruch auf Ersatz seiner Aufwendungen bis zur Anordnung des Gerichtsgutachtens. Dies gelte sinngemäss auch für die kantonalen Gerichtskosten. Zudem rügt er eine Verletzung des rechtlichen Gehörs, da die Vorinstanz nicht begründet habe, weshalb ihm keine Parteientschädigung zustehe.
3.
Vorweg ist die formelle Rüge der Verletzung des rechtlichen Gehörs zu prüfen.
3.1. Das rechtliche Gehör nach <ref-law> verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Dabei ist es nicht erforderlich, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinne müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf die sich ihr Entscheid stützt (<ref-ruling> E. 2.2.1 S. 188, 229 E. 5.2 S. 236).
3.2. Die Vorinstanz stellt in E. 7 ihres Entscheids einleitend fest: "Bei diesem Verfahrensausgang besteht kein Anspruch auf eine Parteientschädigung." Diese Aussage ist in Zusammenhang mit dem vorangegangenen Satz, dem letzten von E. 6.2 zu sehen ("Demnach ist die Beschwerde abzuweisen."). Auch wenn es wünschbar gewesen wäre, dass die Vorinstanz wenigstens die massgebliche gesetzliche Grundlage (<ref-law>, welcher explizit ein Obsiegen der versicherten Person voraussetzt) angegeben hätte, ist aus dem Zusammenhang jedoch klar ersichtlich, dass sie dem Versicherten keine Parteientschädigung zusprach, weil seine Beschwerde abgewiesen wurde. Da es sich dabei um die übliche Rechtsfolge bei einem erfolglos eingereichten Rechtsmittel handelt, war keine einlässliche Begründung notwendig (vgl. <ref-ruling> E. 5 S. 503, wonach der Richter etwa bei der ermessensweisen Festsetzung der Höhe einer Parteientschädigung diese in der Regel nicht begründen muss, sofern er sich an den gesetzlich vorgegebenen Tarifrahmen hält). Im Verzicht auf eine ausführliche Begründung kann hier jedenfalls keine Verletzung des rechtlichen Gehörs erblickt werden.
4.
4.1. Gemäss <ref-law> hat das erstinstanzliche Gericht unter Mitwirkung der Parteien die für den Entscheid wesentlichen Tatsachen festzustellen und die notwendigen Beweise zu erheben. Nach dem Bundesgericht dürfen die erstinstanzlichen Gerichte sich ihrer Pflicht zur Abklärung des massgeblichen Sachverhalts nach <ref-law> nicht ohne Not durch Rückweisung an die IV-Stelle zur weiteren Abklärungen entziehen. Vielmehr hat es die Vorteile des gestrafften Verfahrens und des verminderten Risikos von multiplen Begutachtungen bei Anordnung eines Gerichtsgutachtens hervorgehoben und die bisherige Praxis, wonach es im Ermessen der erstinstanzlichen Gerichte lag, selbst ein Gutachten einzuholen oder die Sache zur weiteren Abklärung zurückzuweisen, geändert. Nunmehr stellt die Einholung eines Gerichtsgutachtens den Regelfall dar und die Rückweisung an die IV-Stelle bleibt beschränkt auf Fälle, in welchen eine bis anhin noch nicht abgeklärte Frage zu beantworten ist oder in denen es lediglich um Klarstellungen, Präzisierungen oder Ergänzungen von gutachterlichen Ausführungen geht (<ref-ruling> E. 4.4.1 S. 263 mit Hinweisen).
Abweichend von <ref-law> ist das kantonale Beschwerdeverfahren bei Streitigkeiten um die Bewilligung oder Verweigerung von IV-Leistungen kostenpflichtig; der Kostenrahmen beträgt Fr. 200.- bis Fr. 1'000.- (<ref-law>). Dabei richtet sich die Aufteilung der Gerichtskosten bei bloss teilweisem Obsiegen nach kantonalem Verfahrensrecht (Urteil 8C_568/2010 vom 3. Dezember 2012 E. 4.2).
Nach <ref-law> hat die versicherte Person Anspruch auf Ersatz der Parteikosten, wenn sie obsiegt. Nach der Rechtsprechung wird dies nach einer materiellen Betrachtungsweise unter Zugrundelegung der gestellten Anträge beurteilt und es kann erst dann von einem Obsiegen gesprochen werden, wenn das Gericht den Entscheid zugunsten der beschwerdeführenden Person abgeändert hat resp. wenn sich deren Position durch den Entscheid verbessert hat (Ueli Kieser, ATSG-Kommentar, 3. Aufl. 2015, N. 205 zu <ref-law> mit Verweis auf <ref-ruling> E. 6.2 S. 235). Wird eine Sache zur weiteren Abklärung an die IV-Stelle zurückgewiesen, stellt dies ein vollständiges Obsiegen dar (<ref-ruling> E. 6.1 S. 235).
4.2. Entgegen der Ansicht des Versicherten kann seine Situation nicht mit jener einer Person verglichen werden, deren Fall durch das kantonale Gericht an die IV-Stelle zu weiteren Abklärungen zurückgewiesen wurde. Denn die Vorinstanz war nicht frei, ob sie selber ein Gutachten in Auftrag geben oder aber die Sache an die IV-Stelle zu weiteren Abklärungen zurückweisen wolle. Vielmehr war sie nach der geltenden Rechtsprechung (E. 4.1) gehalten, ein Gerichtsgutachten einzuholen.
Bei einem Vergleich der Rechtsstellung des Versicherten bei Erlass der Verfügung der IV-Stelle mit jener bei Vorliegen des vorinstanzlichen Entscheids ist festzustellen, dass sich diese nicht verbessert hatte. Insofern ist nicht zu beanstanden, dass die Vorinstanz von einem vollständigen Unterliegen des Beschwerdeführers ausging, da er seine Rechtsstellung nicht verbessern konnte. Daran ändert auch der Umstand nichts, dass seinem Verfahrensantrag auf Einholung eines weiteren Gutachtens entsprochen wurde. Denn nach der Rechtsprechung könnte er nur dann eine Entschädigung für die Notwendigkeit der Einleitung des kantonalen Verfahrens geltend machen, wenn er lediglich den (vorinstanzlich nunmehr bestätigten) Fehler der IV-Stelle gerügt hätte; da er aber die Verfügung der IV-Stelle über den ungenügend erstellten Sachverhalt hinaus in weiteren Punkten angefochten hat, sind ihm insgesamt keine unnötigen Kosten aus dem Fehlverhalten der IV-Stelle erwachsen, welche diese gemäss dem allgemeinen Grundsatz, wonach der Verursacher unnötige Kosten zu übernehmen hat, ihm zu erstatten hätte (vgl. SVR 2010 IV Nr. 51 S. 157 E. 3.3, 9C_363/2009). Unbehelflich ist auch der Verweis auf das Urteil 9C_99/2010 vom 6. Dezember 2010, da dieses nicht einschlägig ist; dort erfolgte eine Rückweisung an die IV-Stelle zur - von der Vorinstanz nicht vorgenommenen - Prüfung des Anspruchs auf berufliche Massnahmen.
Nach dem Gesagten ist nicht zu beanstanden, dass die Vorinstanz dem Versicherten die Gerichtskosten auferlegt und eine Parteientschädigung verweigert hat, da es an einem - wenigstens teilweisen - Obsiegen mangelt.
5.
Dem Verfahrensausgang entsprechend sind die Gerichtskosten vom Beschwerdeführer als unterliegender Partei zu tragen (<ref-law>). Ihm ist indessen die unentgeltliche Rechtspflege zu gewähren (<ref-law>), weil die Bedürftigkeit aktenkundig und die Beschwerde nicht als aussichtslos zu bezeichnen ist sowie die anwaltliche Vertretung geboten war. Es ist indessen auf <ref-law> hinzuweisen, wonach der Gerichtskasse Ersatz zu leisten sein wird, wenn dies später möglich sein sollte.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt und Advokatin Raffaella Biaggi wird als unentgeltliche Anwältin bestellt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Der Rechtsvertreterin des Beschwerdeführers wird aus der Bundesgerichtskasse eine Entschädigung von Fr. 2'800.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons Solothurn und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 14. Juni 2016
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Riedi Hunold