matlab - Discrete optimization algorithm -



matlab - Discrete optimization algorithm -

i'm trying decide on best approach problem, follows:

i have set of objects (about 3k-5k) want uniquely assign 10 groups (1 grouping per object). each object has set of grades corresponding how fits within each group. each grouping has capacity of objects can manage (the constraints). goal maximize sum of grades assignments receive.

for example, let's have 3 objects (o1, o2, o3) , 2 groups (g1,g2) cap. of 1 object each. assume grades are:

o1: g1=11, g2=8

o2: g1=10, g2=5

o3: g1=5, g2=6

in case, optimal result g1 should receive o2, , g2 should receive o1, yielding total of 10+8=18 points.

note number of objects can either exceed sum of quotas (e.g. leaving o3 "leftover") or fall short filling quotas.

how should address problem (traveling salesman, sort of weighted knap-sack etc.)? how long should brute-forcing take on regular computer? there standard tools such linprog function in matlab back upwards sort of problem?

it can solved min cost flow algorithm. graph can next way:

it should bipartite. left part represents objects(one vertex each object). right part represents groups(one vertex each group). there border each vertex left part each vertex right part capacity = 1 , cost = -grade pair. there border source vertex each vertex left part capacity = 1 , cost = 0 , there border each vertex right part sink vertex(sink , source 2 additional vertices) capacity = constraints grouping , cost = 0.

the reply -the cheapest flow cost source sink.

it possible implement o(n^2 * m * log(n + m)) time complexity(using dijkstra algorithm potentials)(n number of objects, m number of groups).

algorithm matlab mathematical-optimization

Comments

Post a Comment

Popular posts from this blog

model view controller - MVC Rails Planning -

model view controller - MVC Rails Planning - i'm starting rails , i'm building app stores films info, user can watch film , give grade on web application. i have coded cinema model, controller , views. now, have 2 questions: should need create model , controller grading? in case, should create or should wait , create first users model , controller? yes, on model , controller grades. that'd feasible way maintain track of who's graded what. it's create first, i'd start users, since grades depend on both films , users. ruby-on-rails model-view-controller
Read more

ruby on rails - Devise Logout Error in RoR -

ruby on rails - Devise Logout Error in RoR - while using devise in ror, encountering unusual error when trying log out url different root url. displays me : actioncontroller::invalidauthenticitytoken in devise::sessionscontroller#destroy" for illustration if rooting path after log in '/structure', , seek log out '/general' error, while logging out '/structure' fine. any help highly appreciated. ruby-on-rails ruby devise
Read more

html - Submenu setup with jquery and effect 'fold' -

html - Submenu setup with jquery and effect 'fold' - i want open submenu jquery effect fold, problem if user "hover effect" fast menu remain open, how can avoid this, jquery code is: $('ul.mainmenu li').hover( function() { $(this).children('ul').show('fold', 570); }, function() { $(this).children('ul').hide('fold', 500); } ); my jsfiddle link is: http://jsfiddle.net/9wkbf/ updated fiddle the reason behind problem is, first event $(this).children('ul').show('fold', 570); queued , until completes, sec animation not start. the next snippet can workaround $('ul.mainmenu > li').hover( function() { $(this).children('ul').show('fold', 570); }, function() { $('ul:not(.mainmenu)').hide('fold', 500); } ); *important note : work current scenario. jquery html css
Read more