Large Scale Discrete Optimization

目标***提出的研究目标是使用整数线性规划（ILP）公式对工业中出现的问题进行建模，并开发技术来获得这些问题的大型实例的最优解或接近最优解。在这个建议中，我们着重于获得ILP公式，以及这些公式的有效不等式，从而减小了完整性差距。这两种方法通常都需要我们解决棘手的子问题。对于使用带有列生成的分解技术的公式，子问题对应于提取负降成本列。对于有效不等式，子问题对应于分离问题。我们将开发具有支持数据结构的启发式方法，以有效地解决这些子问题。我们将在分支和价格框架中使用它们来解决这些问题的大型实例。***我们考虑公用事业公司遇到的带有技能集（VRPSS）的车辆路线问题。在这个问题中，我们在欧几里得空间中给定一组工作，需要一组工人来完成。每个工作都有技能要求，每个工人都有一套技能。目标是推导出一组总长度最小的路线，每个工人一条路线，这样每个工作都由具有所需技能的工人服务。鉴于该问题在计算上难以处理，我们试图通过提供问题的ILP公式并使用CPLEX来解决该问题的实际实例。我们提供了一个使用列生成来减少完整性差距的公式。与单纯形法一样，子问题使用主问题中的对偶值来确定是否可以将负的降低成本列添加到基中。我们采用快速启发式方法重复求解子问题，在主问题中引入负降代价列。最后，我们计划使用分支和价格算法来获得主问题的最优整数解。***我们使用类似的方法来解决投票理论中出现的比例代表问题的大型实例：最小化Chamberlin-Courant投票方法中使用的错误陈述总和的问题。我们提供了一个使用列生成的问题的重新表述，减少了完整性差距。我们希望利用这一点来解决这个问题的大型实例。我们希望使用快速启发式来解决出现的计算上难以处理的子问题。***意义：我们希望获得更严格的最优边界，以及使用列生成方法的最优（或接近最优）解决方案，用于两个重要问题的大型实例：具有技能集的车辆路线问题，以及在Chamberlin-Courant投票方法中出现的比例代表问题。**

Objective***The objective of the proposed research is to model problems that arise in industry using integer linear programming (ILP) formulations, and develop techniques to either obtain optimal solutions, or solutions close to the optimal, for large instances of these problems.***Approach ***In this proposal, we focus on obtaining ILP formulations, as well as valid inequalities for these formulations which reduce the integrality gap. Both these approaches typically require us to solve intractable sub problems. For the formulations using decomposition techniques with column generation, the sub problem corresponds to extracting a negative reduced cost column. For the valid inequalities, the sub problem corresponds to the separation problem. We will develop heuristics, with supporting data structures, to solve these sub problems efficiently. We will use these in a branch and price framework to solve large instances of these problems. ***We consider the vehicle routing problem with skill sets (VRPSS), encountered by utility companies. In this problem, we are given a set of jobs in Euclidean space, that need to be served by a set of workers. Each job has a skill requirement, and each worker has a set of skills. The objective is to derive a set of routes with minimal total length, one route for each worker, such that each job is served by a worker with the required skill. Given that the problem is computationally intractable, we attempt to solve practical instances of the problem by providing an ILP formulation for the problem, and solving it using CPLEX. We provide a formulation using column generation to reduce the integrality gap. As in the simplex method, dual values in the master problem are used by the sub problem to determine if a negative reduced cost column can be added to the basis profitably. We use fast heuristics to repeatedly solve the sub problem to introduce negative reduced cost columns in the master problem. Finally, we plan to use a branch and price algorithm to obtain the optimal integer solution to the master problem. ***We use a similar approach to solve large instances of the proportional representation problem that arises in voting theory: the problem of minimizing the sum of misrepresentations used in the Chamberlin-Courant voting method. We provide a reformulation using column generation for the problem which reduces the integrality gap. We hope to exploit this to solve large instances of this problem. We hope to use fast heuristics to solve the computationally intractable sub problem that arises. ***Significance: We hope to obtain tighter bounds on the optimal, as well as solutions that are either optimal (or close to the optimal) using the column generation approach, for large instances of two important problems: the vehicle routing problem with skill sets, and the proportional representation problem that arises in the Chamberlin-Courant voting method. **