A Discrete Meta-Control Procedure for Approximating Solutions to Binary Programs

Entropy

Pengbo Zhang²  Wolf Kohn¹ 

[1] Department of Industrial and Systems Engineering, University of Washington, Seattle, WA 98195, USA;

关键词: large-scale binary integer programs;    linear quadratic tracking;    optimal control;   

DOI  :  10.3390/e15093592

来源: mdpi

【 摘 要 】

Large-scale binary integer programs occur frequently in many real-world applications. For some binary integer problems, finding an optimal solution or even a feasible solution is computationally expensive. In this paper, we develop a discrete meta-control procedure to approximately solve large-scale binary integer programs efficiently. The key idea is to map the vector of n binary decision variables into a scalar function defined over a time intervaland construct a linear quadratic tracking (LQT) problem that can be solved efficiently. We prove that an LQT formulation has an optimal binary solution, analogous to a classical bang-bang control in continuous time. Our LQT approach can provide advantages in reducing computation while generating a good approximate solution. Numerical examples are presented to demonstrate the usefulness of the proposed method.

【 授权许可】

CC BY   
© 2013 by the authors; licensee MDPI, Basel, Switzerland.