Michele Lombardi Home Page

Me on kayaking

Michele Lombardi

post doctoral fellow

DISI, Università di Bologna
Viale del Risorgimento 2, 40136 - Bologna (IT)

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...):

 

I have recently started to share code via git repositories and Virtual MachinesCurrently, I have:

About me

 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. 

Data & Code

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:

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

A Task Graph generator

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.

De-cycling Scheduling Problems

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.

Min-flow based MCS Detection

[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.

 

Neuron Constraints

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

Robust Scheduling

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:

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


References

  1. Lombardi, M., and M. Milano, "A min-flow algorithm for Minimal Critical Set detection in Resource Constrained Project Scheduling", Artificial Intelligence, 2012.
  2. 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.
  3. 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.
  4. 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.

Thermal Aware Workload Dispatching

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.

Problem 1: Final Temperature Minimization
Problem 2: Maximize Efficiency in the Presence of Thermal Controllers

 

Deriving Information from Sampling and Diving

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).

PhD Thesis

 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.

Publications

 

Export 40 results:
Sort by: Author Title Type [ Year  (Desc)]
Filters: Author is Lombardi  [Clear All Filters]
2015
Bonfietti, A., M. Lombardi, and M. Milano, "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.
Cauwelaert, S. V., M. Lombardi, and P. Schaus, "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.
2014
Bartolini, A., A. Borghesi, T. Bridi, M. Lombardi, and M. Milano, "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.
Milano, M., and M. Lombardi, "Strategic decision making on complex systems", Constraints, vol. 19(2), pp. 174-185, 2014.  Download: cp2012Position.pdf (878.34 KB)
Milano, M., and M. Lombardi, "Strategic decision making on complex systems", Constraints, vol. 19, no. 2, pp. 174–185, 2014.
2013
Bonfietti, A., M. Lombardi, and M. Milano, "De-Cycling Cyclic Scheduling Problems", Twenty-Third International Conference on Automated Planning and Scheduling, 2013.
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.
2012
2011
2010
Lombardi, M., and M. Milano, "Allocation and scheduling of Conditional Task Graphs", Artificial Intelligence, vol. 174, no. 7-8, pp. 500-529, 2010.
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.
Parisini, F., M. Lombardi, and M. Milano, "Discrepancy-Based Sliced Neighborhood Search", Artificial Intelligence: Methodology, Systems, and Applications, 14th International Conference, AIMSA 2010, Varna, Bulgaria, pp. 91-100, 2010.