Large Scale Discrete Optimization

点击翻译按钮获取中文摘要

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