Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$20,000.00

Large Scale Discrete Optimization

FY 2015-16

Summary
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.
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-03660
Name nom
Krishnamurti, Ramesh
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
20000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
1
Nb partie
5
Application title
Large Scale Discrete Optimization
Keyword
NSERC
Application summary
<p>Objective</p> <p>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.</p> <p>Approach </p> <p>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. </p> <p>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. </p> <p>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. </p> <p>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. </p>