post doctoral fellow DISI, Università di Bologna Tel. +39 051 20 93270 email: michele<dot>lombardi2<at>unibo<dot>it |

I am a fixed-term Assistant Professor at the DISI department of the University of Bologna, working on Combinatoral Optimization and Decision Support Systems. In particular, my research activity is focused on hybrid optimization methods, based on heterogeneous techniques such as Constraint Programming, (Mixed) Integer Linear (and Non-Linear) Programming, and Machine Learning. My main application fields are Resource allocation and Scheduling problems, Cyclic Scheduling (e.g for control system design), and Scheduling problems in the presence of Uncertainty.

More recently, I have started to work with prof. Michela Milano on a methodology to solve optimization problems over complex system by embedding Machine Learning models withing optimization models: we called it "Empirical Model Learning". If you are interested, you can find more information here, or you can check some code for embedding Neural Networks in CP.

I have to say that I like this "Empirical Model Learning" idea very much, and not just because it's something I am working on. I actually like the idea that by hybridizing CP (or another optimization technique) and learning we can tackle problems that would be impossible to address by using either of the techniques alone.

**Some shared resources (some refer to past activities...):**

- Together with Standa Zivny, I was Doctoral Programme chair at CP 2012. If you are interested have a look at the Doctoral Programme web site.
- Together with Paolo Liberatore and Floriano Scioscia, I chaired the Doctoral Consortium of the AIxIA Symposium 2012. For more information you can check the DC web site.

- The full text of my PhD thesis is available for download (see the link on the left).
- I gave lectures at the
**2012 ACP Summer School in Wroclaw**, Poland. You can access here lesson 1, lesson 2 and lesson 3.

**I have recently started to share code via git repositories and Virtual Machines. **Currently, I have:

- A repository about a work on devising a Lagrangian Propagator for Neural Networks in CP
- More VMs are coming...

I'm a post-doctoral fellow at DEIS, University of Bologna since April 2010, within the Artificial Intelligence group. I got my PhD degree at University of Bologna in April 2010, with topic "Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments".My research activity is related to Constraint Programming and its integration with Integer Programming techniques; in particular, my focus is on resource allocation and scheduling problems, with applications to emebedded system design based on multiprocessor platform.I got a Master Degree in Computer Science at University of Bologna, with disseration "Allocation and Scheduling of Conditional Task Graphs on MultiProcessor Systems on Chip: a stochastic, constraint based, approach", and grade 110/110 CL. My bachelor degree is from the same university with dissertation "Development of a support web site for scientific research", and grade 110/110.In the period April 2006 - September 2006 and in January 2007 I did some research at the Intelligent Information Systems Institute of Cornell University (Ithaca, NY). From June 2009 to December 2010 took an intership at the Ecole Polytechnique Féderale de Lausanne (EPFL), in the LSI lab.

The pages in this section contain code and data (typically: results or instances) from some of the research topics I have worked on. I have recently started to use git repositories and Virtual Machines to share code. Currently, I have:

- A repository about a work on devising a Lagrangian Propagator for Neural Networks in CP

You can find some code for Neuron Constraints in the section about Empirical Model Learning.

This is the generator used to build instances for works on uncertain durations and those making use of Logic based Benders' Decomposition (i.e. Conditional Task Grapha and multi-stage LBBD). A paper describing some of the features of a flexible graph generator was presented at the ICAPS07 workshop "Scheduling a scheduling competition". The generator is designed to produce Task Graph representing "realistic applications"; options are customized via a configuration file, passed to the software as a command line argument. The generator can label arcs and nodes in the graph wit a user-defined set of attributes; attribute values are obtained by combining randomly generated numbers *and* other attributes values; this allows to state (e.g.) that a task maximum duration is always larger than the minimum duration. The code for the generator is available for download. Be careful, however: it is not well polished and there is no documentation at the moment. **UPDATE:** there's guy at our lab working on a brand new graph generator; I'll let you know when it is available.

Here you can access data and code related to the paper:

A. Bonfietti, M. Lombardi, M. Milano, "De-cyclic Cyclic Scheduling Problems", Proc. of ICAPS 2013

- The code (downloadable here) is a single, fairly simple, cpp file for ILOG CP Optimizer. I am afraid the documentation is poor, but you can contact me via email to get more information.
- The instances (get a zip file with the whole lot here) are syntetically generated and feature a single resource. The resource requirement are specified in each file, while the resource capacity is passaed as a parameter to the solver.

[NEW!] I have just released the code of the PCP solver we used for the experimentation, with all the MCS detection algorithm implemented.

This page contains links to pseudo-code and experimental results for an MCS detection method we proposed, based on the solution of a minimum flow problem. In exerimentation we compare:

- the min-flow based strategy (referred to as MINFLOW)
- the enumerative strategy from:
*"Laborie, P. (2005). Complete MCS-Based Search: Application to Resource Constrained Project Scheduling. Proc. of IJCAI (pp. 181-186). Professional Book Center."*, referred to as ENUM - the envelope based strategy from
*"Policella, N., Smith, S. F., Cesta, A., & Oddi, A. (2004). Generating Robust Schedules through Temporal Flexibility. Proc. of ICAPS (pp. 209-218)."*, referred to as PEAKS - min-flow plus random CS minimization, referred to as RAND

All appraoches are tested within a (retively) classical CP Depth First Search approach (referred to as CP) and an optimization appraoch based on the destructive computation of increasing lower bounds (referred to as SWEEP). More details can be found in this paper.

Here is the pseudo-code for minium flow computation and for the extracttion of the maximum weight independent set (if the graph has been build by splitting nodes with non-null flow resource requirement):

LEGENDA: - Q = queue containing nodes (indices) to be visited - pre[i] = predecessor of node "i" along a diminishing path; in detail, if the predecessor is node "j", pre[i] stores "j+1" if node "i" is reached through a forward arc, "-j-1" if it is reached through a backward arc - d[i] = maximum allowed variation at node "i" on a diminishing path - source = index of the source node - sink = index of the sink node - flow[i][j] = flow on arc (t, j) - r[i][j] = minimum flow requirement on arc (i, j) find initial flow (with any technique) // start building diminishing paths stop = false while stop is false: // reset current diminishing path set all pre[i] to 0 // add source node to the current diminishing path pre[source] = source + 1 d[source] = infinity // start building the path while Q is not empty and pre[sink] = 0: pop a node index "i" from Q // visit forward arcs for each arc (i, j) in the graph with pre[j] != 0: // visit a forward arc only if it appears in the residual graph if flow[i][j] > r[i][j]: pre[j] = i + 1 d[i] = min(d[i], flow[i][j] - r[i][j]) push j on Q // visit backward arcs for each arc (j, i) in the graph with pre[j] != 0: // always visit backward arcs (there's not upper limit on the flow) pre[j] = -i -1 d[j] = min(d[i], infinity) push j on Q // now, if the sink has not been reached, the minimum flow has been found if pre[sink] = 0: stop = true // else, we have to diminish the flow along the path else: i = sink while i != source: if pre[i] > 0: // update flow on a forward arc j = pre[i]-1 subtract d[sink] from flow[j][i] else: // update flow on a backward arc j = -pre[i] -1 sum d[sink] to flow[i][j] // move to previous node on the path i = j // extract relevant arcs from the S/T cut (in the modified resource graph, // those correspond to activities/requirements for each arc (i, j) in the graph: // if node i has been visited, node j has not and the flow is not null if pre[i] != 0 and pre[j] = 0 and flow[i][j] > 0: add pair (i, j) to the set of relevant arcs in the S/T cut // compute overall flow value f = sum of flow[source][i] for every arc (source, i) in the graph

Beware, while the real code has been extensively tested, the pseudo code has not.

The following list contains link to tables with the results for single approaches and pairwise comparisons; note that since comparison are done on an instance basis, their data cannot be deduced by single approach tables. All tables are in CSV format and use Linux EOL.

The following list is a selection of summary results; they are much more readable than the previous ones.

- summary for single approaches
- pairwise appraoch comparison, with CP strategy
- pairwise approach comparison, with SWEEP strategy
- comparison of CP and SWEEP strategy for each approach
- summary for j120

I have been workng for some time on model learning and Neuron Constraints. You can find more details (including code) here.

This page contains the code of a solver to build optimized robust schedules for problems where tasks have fixed or even uncertain duration. The approach couples an off-line optimizer and an simple on-line scheduling policy and was moslty developed in the context of the FP7 Project SMECY.

The off-line optimizer is based on the Precedence Constraint Posting technique, i.e. a "schedule" is in fact a set of precedence constraints that make the original graph conflict free. The solver searches for feasible schedules by branching over Minimal Critical Sets, which can be identified using a number of different techniques.

The on-line scheduling policy can be arbitrarily chosen, provided that some basic specifications are satisfied. In detail, we support two broad classes of on-line schedulers:

- Non-delay schedulers: an policy in this classes never delays a task if all its predecessors have completed executions and enough resources are available. Many widely adopted methods fall into this category (e.g. First Come First Served, Fixed Priority Scheduling...).
*In case a non-delay scheduler is used, it is possible to instruct the off-line optimizer to take into account the policy behavior: this results in the addition of fewer precedence constraints and hence lower run-time overhead.* - General on-line schedulers: a policy in this class may abritrarily decide to delay a task. This may be useful if the optimized application is not the only one running on the system, so that a task may be delayed to perform some computation belonging to a different application. In this case, the on-line scheduler must also guarantee the satisfactio of a set of restricted deadlines, provided by the off-line optimizer.

The code is known to compile on Ubuntu Linux distributions. Dependencies include the boost library and the IBM ILOG CP suite (version 1.5 or above), available for free for academic use via the IBM Academic Initiative. The code is released with a detailed README file, containing instruction about how to build and run the software. Moreover, we include a subset of Resource Constraint Scheduling Problem instances from the PSPlib library, in the input format required by the PCP scheduler.

Here are the links to al available resources:

- Optimizer code + examples from the PSPlib (all with fixed durations)
- Synthetic task graph instances, pre-mapped on two different platforms (NOTE: you need to change some compile time options to make this work, in particular the minimum/maximum property names: check the README about this)

If you need further information, you can contact me via email or refer to references [1][2][3][4]

- Lombardi, M., and M. Milano,
"A min-flow algorithm for Minimal Critical Set detection in Resource Constrained Project Scheduling",
*Artificial Intelligence*, 2012. - Lombardi, M., M. Milano, and L. Benini,
"Robust Scheduling of Task Graphs under Execution Time Uncertainty",
*IEEE Transactions on Computers*, vol. 62, issue 1, no. 99: IEEE, pp. 90--111, 2013. - Lombardi, M., and M. Milano,
"Constraint based scheduling to deal with uncertain durations and self timed execution",
*Principles and Practice of Constraint Programming 16th International Conference, CP 2010, St. Andrews, Scotland*, pp. 383-397, 2010. - Lombardi, M., and M. Milano,
"A Precedence Constraint Posting Approach for the RCPSP with Time Lags and Variable Durations",
*Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal*, pp. 569-583, 2009.

Here we provide the instances and the Empirical System Model for two Thermal Aware Workload Dispatching Problems on multicore CPUs. You can contanct Michele Lombardi via email for a detailed description of the data format.

- Quad core system (linear floorplan)
- Empirical System Model (an Artificial Neural Network)
- Instances (homogeneous starting temperatures)
- Instances (heterogeneous starting temperatures)

- Quad core system (square floorplan)

- Empirical System Model (an Artificial Neural Network)
- Instances (homogeneous starting temperatures)
- Instances (heterogeneous starting temperatures)

- Empirical System Model [3-Layers ANN] [2-Layers ANN] [1-Layer ANN]
- Workloads

In this project, we investigated the impact of information extracted from *sampling* and *diving* on the solution of Constraint Satisfaction Problems (CSP). A sample is a complete assignment of variables to values taken from their domain according to a given distribution. Diving consists in repeatedly performing depth first search attempts with random variable and value selection, constraint propagation enabled and backtracking disabled; each attempt is called a dive and, unless a feasible solution is found, it is a partial assignment of variables (whereas a sample is a --possibly infeasible-- complete assignment). While the probability of finding a feasible solution via sampling or diving is negligible if the problem is difficult enough, samples and dives are very fast to generate and, intuitively, even when they are infeasible, they can provide some statistical information on search space structure. The aim of this paper is to understand to what extent it is possible to support the CSP solving process with information derived from sampling and diving. In particular, we are interested in extracting from samples and dives precise indications on the quality of individual variable-value assignments with respect to feasibility. We formally prove that even uniform sampling could provide precise evaluation of the quality of single variable-value assignments; as expected, this requires huge sample sizes and is therefore not useful in practice. On the contrary, diving is much better suited for assignment evaluation purposes. We undertake a thorough experimental analysis on a collection of Partial Latin Square and Car Sequencing instances to assess the quality of information provided by dives. Dive features are identified and their impact on search is evaluated. Results show that diving provides information that can be fruitfully exploited.

Here are the instances used for the experimentation and part of the results:

Further details are available upon request: the download size would be large and (at this point of time) too many explanations required in order to have them available on a web page).

I defended my PhD thesis in April 2010; the title was "Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments" and the full text is available for download.

"Embedding Decision Trees and Random Forests in Constraint Programming",
*Integration of {AI} and {OR} Techniques in Constraint Programming - 12th International Conference, {CPAIOR} 2015, Barcelona, Spain, May 18-22, 2015, Proceedings*, pp. 74–90, 2015.

"Understanding the Potential of Propagators",
*Integration of {AI} and {OR} Techniques in Constraint Programming - 12th International Conference, {CPAIOR} 2015, Barcelona, Spain, May 18-22, 2015, Proceedings*, pp. 427–436, 2015.

"CROSS cyclic resource-constrained scheduling solver",
*Artificial Intelligence*, vol. 206, pp. 25–52, 2014.
Abstract

"Disregarding Duration Uncertainty in Partial Order Schedules? Yes, We Can!",
*CPAIOR*, pp. 210-225, 2014.

"Proactive Workload Dispatching on the EURORA Supercomputer",
*Principles and Practice of Constraint Programming - 20th International Conference, {CP} 2014, Lyon, France, September 8-12, 2014. Proceedings*, pp. 765–780, 2014.

"Strategic decision making on complex systems",
*Constraints*, vol. 19(2), pp. 174-185, 2014.
Download: cp2012Position.pdf (878.34 KB)

"Strategic decision making on complex systems",
*Constraints*, vol. 19, no. 2, pp. 174–185, 2014.

"De-Cycling Cyclic Scheduling Problems",
*Twenty-Third International Conference on Automated Planning and Scheduling*, 2013.

"Maximum-throughput mapping of SDFGs on multi-core SoC platforms",
*Journal of Parallel and Distributed Computing*: Academic Press, 2013.

"Robust Scheduling of Task Graphs under Execution Time Uncertainty",
*IEEE Transactions on Computers*, vol. 62, issue 1, no. 99: IEEE, pp. 90--111, 2013.

"A min-flow algorithm for Minimal Critical Set detection in Resource Constrained Project Scheduling",
*Artificial Intelligence*, 2012.

"Optimal Methods for Resource Allocation and Scheduling: a Cross-Disciplinary Survey",
*Constraints*, vol. 17, issue 1, pp. 51-85, 2012.
Download: SurveyConstraintAS.pdf (624.06 KB)

"Optimization and Controlled Systems: A Case Study on Thermal Aware Workload Dispatching",
*Proceedings of AAAI*, 2012.
Abstract

"A constraint based approach to cyclic RCPSP",
*Principles and Practice of Constraint Programming*, Perugia, Spinger, 2011.

"Deriving Information from Sampling and Diving",
*Fundamenta Informaticae*, vol. 107, issue 2-3, pp. 267-287, 2011.

"MPOpt-Cell: a high-performance data-flow programming environment for the CELL BE processor",
*Conf. Computing Frontiers*, pp. 11, 2011.

"Neuron Constraints to Model Complex Real World Problems",
*Principles and Practice of Constraint Programming*, Perugia, Springer, 2011.

"Optimal Resource Allocation and Scheduling for the CELL BE Platform",
*Annals of OR*, vol. 184, issue 1, pp. 51-77, 2011.

"Precedence Constraint Posting for Cyclic Scheduling Problems",
*CPAIOR*, pp. 137-153, 2011.

"Allocation and scheduling of Conditional Task Graphs",
*Artificial Intelligence*, vol. 174, no. 7-8, pp. 500-529, 2010.

"Constraint based scheduling to deal with uncertain durations and self timed execution",
*Principles and Practice of Constraint Programming 16th International Conference, CP 2010, St. Andrews, Scotland*, pp. 383-397, 2010.

"Discrepancy-Based Sliced Neighborhood Search",
*Artificial Intelligence: Methodology, Systems, and Applications, 14th International Conference, AIMSA 2010, Varna, Bulgaria*, pp. 91-100, 2010.