Seminar on Applied Mathematics
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.
Nenad Mladenovic, Matematicki institut SANU
DESIGN OF BALANCED MBA STUDENT TEAMS
In some schools and universities, students must sometimes be divided into several teams in such a way that each team provides a good representation of the classroom population. In this paper two different ways of measuring the balance among teams are proposed: min-sum and min-max objective functions. For the first function and the L1-norm used in the space of attributes, an exact solution method based on a set partitioning formulation and on the enumeration of all possible team patterns is presented. For the second objective function, a set partitioning formulation is also considered, but as an approximation. In order to solve large problem instances, we have also developed metaheuristics based on variable neighborhood search. Models and methods are tested on data from a MBA program.
(joint work with J. Desrosiers and D. Willeneuve)
Snezana Mitrovic-Minic, Simon Fraser University, Vancouver
AN EFFICIENT VARIABLE NEIGHBORHOOD SEARCH HEURISTICS FOR THE GENERALIZED ASSIGNMENT PROBLEM
Sadrzaj: Generalized assignment problem is an important optimization model with extensive applications. In this paper we discuss new variable neighborhood search heuristics to solve the problem. Our algorithm exploits powerful neighborhood structures of very large size. Extensive computational results are reported.
(joint work with Prof. Abraham P. Punnen).
Jasmina Lazic, Matematicki institut SANU
VNS HEURISTIKA ZA KVANTIZACIJU BOJA U DIGITALNOJ SLICI
Sadrzaj: Kvantizacija boja je vid kompresije podataka kojim se smanjuje ukupan broj boja u datoj digitalnoj slici. Problem kvantizacije boja (CIQ, od eng. "color image quantization") predstavlja problem nalazenja najboljeg reprezentativnog podskupa boja datog polaznog skupa, tako da se minimizuje greska pri predstavljanju originalne slike samo pomocu boja iz dobijenog podskupa. Na ovom predavanju bice dat kratak pregled do sada poznatih metaheuristika za resavanje CIQ problema. Zatim ce biti detaljno objasnjeno kako se CIQ problem moze modelirati kao "minimum-sum-of-squares- clustering" problem i kako se moze primeniti VNS heuristika za nalazenje njegovog optimalnog resenja. Takodje ce biti predstavljeni rezultati primene VNS-a, kako numericki, tako i vizuelni, koji pokazuju da je VNS do sada jedna od najboljih tehnika kvantizacije boja.
(zajednicki rad sa P. Hansenom i N. Mladenovicem)
Guido Perboli, Politecnico di Torino
THE TWO-LEVEL VEHICLE ROUTING PROBLEM
Sadrzaj: Two-level distribution systems are quite common in supplychain and logistic systems. They are used by public administrations in their Transportation and Traffc Planning strategies as well as by companies to model their distribution systems. Unfortunately, the literature on combinatorial optimization methods for two-level distribution systems is limited. The Two-Level Vehicle Routing Problem (2L-VRP) is the extension of the classical VRP where the delivery from the depot to the customers can not be done by means of direct delivery, but the goods are delivered to intermediate deports, the satellites and from the satellites the goods are delivered to the customers. As in the classical one-level VRP, the objective is to deliver the goods to the customers with knowndemands, minimizing the delivery costs. If we have m satellites, the problem consists in m+1 VRP problems organized in two levels. Afirst routing (from the depot to the satellites), the first level routing, feeds the m routing problems (transport from each satellite to the customers assigned by the first level VRP). In this paper, we introduce the Two-Level Vehicle Routing Problem, giving different formulations and deriving some valid inequalities able to significantly improve the results on benchmark tests up to 50 customers and 4 satellites, showing the behavior of the models under different realistic scenarios.