Solving constrained combinatorial optimization problems via MAP inference without high-order penalties

Simple item page
dc.contributor.authorZhang, Z.
dc.contributor.authorShi, Q.
dc.contributor.authorMcAuley, J.
dc.contributor.authorWei, W.
dc.contributor.authorZhang, Y.
dc.contributor.authorYao, R.
dc.contributor.authorVan Den Hengel, A.
dc.contributor.conferenceThirty-first AAAI Conference on Artificial Intelligence (AAAI-17) (4 Feb 2017 - 9 Feb 2017 : San Francisco)
dc.date.issued2017
dc.description.abstractSolving constrained combinatorial optimization problems via MAP inference is often achieved by introducing extra potential functions for each constraint. This can result in very high order potentials, e.g. a 2nd-order objective with pairwise potentials and a quadratic constraint over all N variables would correspond to an unconstrained objective with an order-N potential. This limits the practicality of such an approach, since inference with high order potentials is tractable only for a few special classes of functions. We propose an approach which is able to solve constrained combinatorial problems using belief propagation without increasing the order. For example, in our scheme the 2nd-order problem above remains order 2 instead of order N. Experiments on applications ranging from foreground detection, image reconstruction, quadratic knapsack, and the M-best solutions problem demonstrate the effectiveness and efficiency of our method. Moreover, we show several situations in which our approach outperforms commercial solvers like CPLEX and others designed for specific constrained MAP inference problems.
dc.description.statementofresponsibilityZhen Zhang, Qinfeng Shi, Julian McAuley, WeiWei, Yanning Zhang, Rui Yao, Anton van den Hengel
dc.identifier.citationProceedings of the ... AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence, 2017, pp.3804-3810
dc.identifier.issn2159-5399
dc.identifier.issn2374-3468
dc.identifier.orcidZhang, Z. [0000-0003-2805-4396]
dc.identifier.orcidShi, Q. [0000-0002-9126-2107]
dc.identifier.orcidVan Den Hengel, A. [0000-0003-3027-8364]
dc.identifier.urihttp://hdl.handle.net/2440/115994
dc.language.isoen
dc.publisherAAAI
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140102270
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160100703
dc.relation.ispartofseriesAAAI Conference on Artificial Intelligence
dc.rightsCopyright © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
dc.source.urihttps://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14450
dc.titleSolving constrained combinatorial optimization problems via MAP inference without high-order penalties
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Computer Science publications
Australian Institute for Machine Learning publications