U ovom semestru sastanci Seminara za primenjenu i industrijsku matematiku će se održavati na Fakultetu organizacionih nauka po dole navedenom rasporedu. U Sali 2 Matematickog Insituta održavaće se samo vanredni sastanci, o čemu ce učesnici biti posebno obaveštavani.

Utorak, 26.07.2005. u 14:15, Sala 2, SANU:

Dr Leo Liberti, DEI, Politecnico di Milano, Italy
COMPACT MODEL FOR THE MULTIPROCESSOR SCHEDULING PROBLEM WITH COMMUNICATION DELAYS

Abstract: We propose a novel formulation for scheduling tasks to an arbitrary network of homogeneous processors with precedence constraints between tasks and communication delays between processors. Existing formulations involve a large number of binary variables, resulting from assignment variables with three indices (task, processor, order of execution of task on processor) and linearization variables for bilinear terms with six indices. The model discussed here is based on the idea of packing small rectangles --- representing tasks --- in a bigger rectangle. It only uses original binary variables with at most two indices and linearizing variables with four, and therefore considerably reduces the overall number of variables. The computational improvements are in the order of three to four orders of magnitude.

Utorak, 26.07.2005. 15:15, Sala 2, SANU:

Dr MAurizio Bruglieri, DEI, Politecnico di Milano, Italy
A TWO-PHASE RELAXATION-BASED HEURISTIC FOR THE MAXIMUM FEASIBLE SUBSYSTEM PROBLEM

Abstract: We consider the maximum feasible subsystem problem in which, given an infeasible system of linear inequalities, one wishes to determine a largest feasible subsystem. The focus is on the version with bounded variables that naturally arises in several fields of application. To tackle this NP-hard problem, we propose a simple but efficient two-phase relaxation-based heuristic. First a feasible subsystem is derived from a relaxation (linearization) of an exact continuous bilinear formulation, and then a smaller subproblem is solved to optimality in order to establish whether other inequalities can be added to the current feasible subsystem while preserving feasibility. Computational results, reported for several classes of instances arising, from classification and telecommunication applications, indicate that our method compares well with one of the best available heuristic and with a state-of-the-art exact algorithm.