I think you have covered most of the important topics already in a high level description. You can perhaps consider the following, although I suspect they are specific cases of the items that you already list. I am assuming the perspective of someone with a very detailed technical understanding of the optimisation task, but who may not know how to tune algorithm parameter settings.
If possible, display the solution quality (a number) along with the proposed solution, especially when it comes to multi-objective problems where you can have multiple valid solutions. This could be "time" or "cost" or a combination of both (or any other objective criteria). Showing the quality in a quantitative way, allows a person to (for example) decide if 1% saving in cost is worth 5% loss in time (compared to another solution that maybe saves 0.5% in cost, but only requires 2% extra time). This becomes more important with an increase in objectives to be optimised.
Sometimes the optimisation task is interactive, such that multiple intermediate solutions are presented, and the user picks one solution which is then refined. This may happen many times. There should be a way to structurally compare the solutions (routes, layouts, etc.). This is highly specific to the problem domain, but will come in handy when qualitative criteria are used to tie-break quantitatively-similar solutions. I assume this is covered by your "multiple solutions" item.
Along the same vein, being able to save intermediate solutions and being able to re-start from those "snapshots", or comparing snapshots, may come in handy. Again, being able to compare solution structure, and solution quality is imperative. I assume this ties into your "approximate solution" item.
Parameter settings are usually problem dependant. Capturing and communicating the interactions between parameter settings are crucial, assuming you are able to model these interactions. Basically graphically/visually answering "What happens to y if I increase x?". This will allow the user to tune the algorithm settings before starting the optimisation process, seeing "predicted impact" on solution quality, or execution time etc. Also, if there is a stochastic component (random number generator) involved in the optimisation process, you may want to allow setting of the random seed to make it easier to replicate simulation results. I assume this falls under your "display trade-offs of manual changes promptly", and/or the "faster processing/higher accuracy" items.
Sometimes algorithms prematurely converge in local optima (get stuck on a poor solution), or they simply never improve the solution quality. I would guess being able to spot when this happens graphically, with a performance plot over time, would be very useful. In addition, being able to restart the simulation (if it has prematurely converged), or stop the simulation when it has found a "good enough" solution (saving unnecessary processing time), will be useful.
Being able to save/load optimisation tasks. If you schedule a simulation that will take three days, and after one day you get a notice that building maintenance crews have to perform emergency power tests, then you would preferably allow the user to interrupt the optimisation task, save it, and continue when conditions are more stable.
Those are the points I can think of that will highly improve the user experience off the top of my head.