Bansal, Manish (Department of Industrial and Systems Engineering, Virginia Tech)

Manish Bansal speaker

Manish Bansal
Assistant Professor
Department of Industrial and Systems Engineering
Virginia Tech

Phone: 540-231-6636


Cut-Generation Approaches for Deterministic and Stochastic Mixed Integer Programs

The agenda of this talk is to give a high-level view of my research on solving mixed integer programs (MIPs), stochastic MIPs, and distributionally robust MIPs. More specifically, I will present some unifying results in cutting planes theory for MIPs, and new approaches akin to Benders’ decomposition algorithm for solving two-stage stochastic MIPs, two-stage stochastic p-order conic MIPs, and two-stage distributionally robust mixed binary programs. The emphasis will be on simple-language explanation of ideas instead of delving into complicated technical details. We will begin with a short overview of cutting planes and basic ideas behind cut generation for MIPs. Then we will present facets and extended formulation for a multi-parameter multi-constraint mixed integer set, which we call continuous multi-mixing set. We will show that this research generalizes several existing concepts in cutting plane theory. We will also present our computational results, which show that our cuts are very effective in solving multi-module lot-sizing problems. In the second part of this talk, we will discuss about second-stage convexification approach for solving two-stage stochastic MIPs and two-stage stochastic p-order conic MIPs, and its computational effectiveness.

Appropriate audience: Graduate students

Planar Maximum Coverage Location Problem with Partial Coverage

The planar maximum coverage location problem (MCLP) is a well-known classical problem, in which p service facilities with known service range are to be located anywhere in the continuous plane such that the total covered demand is maximized. In MCLP, it is assumed that the coverage is “binary”, i.e., the demand zone is assumed to be either totally covered or not covered at all. We introduce a new generalization of the MCLP in which “partial coverage” is allowed in true sense, i.e., covering only part of a request is allowed and the coverage accrued in the objective function as a result of this is proportional to the weight of the covered part only. We denote this problem by MCLP-PC which also has applications in geographical informative systems for disaster management and telerobotics. We present a greedy algorithm and a pseudo-greedy algorithm for approximately solving the MCLP-PC, and showcase that the solution value corresponding to the greedy solution is within a fact  or of 1 − 1/e of the optimal solution value where e is the base of natural logarithm. Next, we provide theoretical properties for MCLP-PC with rectilinear distances and an exact algorithm to solve it along with our computational results.

Appropriate audience: Graduate students

Education & Background

  • PhD, Industrial Engineering, Texas A&M University
  • MS, Texas A&M University
  • B. Tech, Electrical Engineering, National Institute of Technology, India