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. **