Dynamic Discretization Discovery: Solving Discrete Time Integer Programs

各部门和行业的决策者必须安排复杂的活动，以平衡和协调对资源的相互竞争的需求，同时实现业务的最大效率。活动的时间安排起关键作用的问题普遍存在。这些问题出现在各种应用中，如调度手术设施、发电、国防军事空运和海运网络的设计和运营，以及在线订单的当天和下一小时递送。这个项目致力于基础研究，导致计算方法，以解决具有挑战性的优化问题，这些问题是这些操作的基础。这些系统的改进设计和运行预计将产生显著的社会经济效益。研究成果将被纳入现有的优化、物流和供应链管理的本科生和研究生课程中。这个项目将促进对时间相关整数规划(IP)问题的基本理解。通过开发动态离散化方法，能够以有效的方式准确地发现需要哪些时间来获得最优解，所产生的IP变得在计算上容易处理。这项研究将涉及先验部分离散化方法，该方法将计划范围划分为时间间隔，并为在这些间隔内安排活动提供基础模型变量。该方法将嵌入三个关键组件：(I)基于时间的部分离散化的扩展、离散时间IP模型，即，仅使用其解在原始问题的值上产生对偶界的可能时间点的子集；(Ii)用于对偶界IP的解的“修复”机制，或基于部分离散化的不同扩展IP模型，以获得原始问题的可行解；以及(Iii)精化技术，其标识要添加到部分离散化的时间点，以改进对偶界。将研究离散化粒度方面的理论界限和可量化的逼近误差。

Decision-makers across a wide range of sectors and industries must schedule complex activities so as to balance and coordinate competing demands on resources while achieving maximum efficiency of operations. Problems where the timing of activities plays a critical role are pervasive. Such problems arise in diverse applications, such as scheduling surgical facilities, electric power generation, design and operation of military air- and sea-lift networks for national defense, and in same-day and next-hour delivery of online orders. This project addresses fundamental research leading to computational methods to solve challenging optimization problems that underly these operations. Improved design and operation of these systems is expected to result in significant socioeconomic benefits. The research findings will be incorporated into existing undergraduate and graduate courses in optimization, logistics, and supply chain management.This project will advance the fundamental understanding of time dependent integer programming (IP) problems. By developing dynamic discretization methods that can discover exactly which times are needed to obtain an optimal solution, in an efficient way, the resulting IPs become computationally tractable. The research will involve a priori partial discretization approaches, which divide the planning horizon into time intervals, and base model variables for placement of activities in these intervals. The methods will embed three key components: (i) extended, discrete time, IP models, based on a partial discretization of time, i.e., using only a subset of the possible time points, whose solution yields a dual bound on the value of the original problem; (ii) a "repair" mechanism for the solution to the dual bound IP, or a different extended IP model based on the partial discretization, to obtain feasible solutions to the original problem; and (iii) a refinement technique, that identifies time points to add to the partial discretization, so as to improve the dual bound. Theoretical bounds and quantifiable approximation errors in terms of discretization granularity will be studied.