A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

DOI10.1007/S10107-020-01522-0MaRDI QIDQ2235141zbMATH OpenOpenAlexFDO

Authors Sergei Chubanov

Publication date 20 October 2021

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-020-01522-0

zbMATH Keywords

nonlinear optimizationgreedy algorithmdiameterscalingsimplex methodbinary optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 2086909
• Scaling: A general framework
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

Cites work

• 0/1-Integer programming: Optimization and Augmentation are equivalent
• A bound for the number of different basic solutions generated by the simplex method
• A generalized simplex method for integer problems given by verification oracles
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximate Local Search in Combinatorial Optimization
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the diameter of convex polytopes
• On the relative complexity of 15 problems related to~0/1-integer programming
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• The Hirsch conjecture is true for (0,1)-polytopes

Cited in

(1)

• Scalable Minimizing-Operators on Polyhedra via Parametric Linear Programming

This page was built for publication: A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2235141)