I was wondering whether there are studies on problems that present solutions composed by a permutation of elements and some non-combinatorial part, such as a set of real values, where both parts have to be optimized. In that case, I would be interested in benchmarks and state-of-the-art algorithms to solve them. I started browsing through the literature, but I am not finding what I'm looking for. Thank you
You can find such problems in many applications related to scheduling or routing for example.
Consider the Earliness/Tardiness scheduling problem, you have to assign jobs and find their processing order on some resources/machines, which is a combinatorial aspect (permutation + assignment), but then even for a fixed assignment and sequence, you can still shift the tasks backward or forward in time, which yields a continuous optimization problem, sometimes called "timing problem", or optimal "departure time problem".
The same issue arises in combined vehicle routing and scheduling settings, in which you have to set up a sequence of deliveries to a subset of geographically scattered customers (combinatorial aspect), but also wish to optimize speed or quality of service by shifting service dates without changing the sequence order (a continuous optimization problem).
Some literature pointers if you are interested :
* Sourd, F., & Kedad-Sidhoum, S. (2003). The one-machine problem with earliness and tardiness penalties. Journal of Scheduling, 6(6), 533–549.
* Hashimoto, H., Ibaraki, T., Imahori, S., & Yagiura, M. (2006). The vehicle routing problem with flexible time windows and traveling times. Discrete Applied Mathematics, 154(16), 2271–2290.
* Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2011). A Unifying View on Timing Problems and Algorithms. CIRRELT Report, No. 2011-43.
Are looking for Mixed-Integer problems? Can you formulate your problem using linear programming?
For continuous (i.e. non-combinatorial) optimization you can check this two well-known benchmarks:
Black-Box Optimization Benchmark (used in GECCO)
http://coco.gforge.inria.fr/doku.php?id=bbob-2012
and
Large Scale Global Optimization (used in CEC)
http://staff.ustc.edu.cn/~ketang/cec2012/lsgo_competition.htm
From those links you should be able to find the documentation, the benchmark itself and some published papers with results.
Of course, you can also check some of my papers if you like ;)
http://ieeexplore.ieee.org/xpl/articleDetails.jsp;jsessionid=5H43QCWN45TyzBfD8yn2XGK2rPdrFhVryLBvm1yQ9tzSQ5FtF4vC!-1188685217?arnumber=6256566&contentType=Conference+Publications
http://rd.springer.com/chapter/10.1007/978-3-642-25832-9_28
you can also find those papers here:
http://yorku.academia.edu/StephenChen/Papers/1847348/Multi-swarm_hybrid_for_multi-modal_optimization
http://yorku.academia.edu/StephenChen/Papers/1305025/An_Analysis_of_Sub-swarms_in_Multi-swarm_Systems
First of all, thanks for the answer and the interest! Actually, I don't have a real-world problem (yet :-D), I am just wondering whether a technique I've been working on for a while (for a different purpose) could be used to solve problems with a mixture of combinatorial and non-combinatorial aspects. Now I will read the literature Thibault proposed and play a little with problems, just to test it. Thanks again!
