首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
Institution:1. Department of e-Business, School of Information, Central University of Finance and Economics, Beijing, 100081, PR China;2. School of Statistics, Renmin University of China, Beijing, 100872, PR China;3. Center for Applied Statistics, Renmin University of China, Beijing, 100872, PR China;4. Consulting Center of Statistics, Renmin University of China, Beijing, 100872, PR China;1. Université libre de Bruxelles, Département de Mathématique, Boulevard du Triomphe, B-1050 Brussels, Belgium;2. Otto-von-Guericke-Universität Magdeburg, Universitätsplatz 2, D-39106 Magdeburg, Germany;1. Université d’Avignon et des Pays du Vaucluse, Laboratoire d’Informatique d’Avignon (LIA), 339, chemin des Meinajaries, Agroparc BP 91228, 84911 Avignon Cedex 9, France;2. KEDGE Business School, 680 cours de la Libération, 33405 Talence Cedex, France
Abstract:We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号