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

作者：Zhang Pengbo; Kohn Wolf^*; Zabinsky Zelda B

来源：Entropy, 2013, 15(9): 3592-3601.

DOI：10.3390/e15093592

• large-scale binary integer programs
• linear quadratic tracking
• optimal control

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 interval [0; n] and 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.

• 出版日期2013-9