Optimization Online


Models and Solution Techniques for Production Planning Problems with Increasing Byproducts

Srikrishna Sridhar(srikris***at***cs.wisc.edu)
Jeff Linderoth(linderoth***at***wisc.edu)
James Luedtke(jrluedt1***at***wisc.edu)

Abstract: We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation of this continuous-time problem is nonconvex. We present a discrete-time mixed-integer nonlinear programming (MINLP) formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed MINLP formulation. We describe three different mixed-integer linear programming (MILP) approximation and relaxation models of this nonconvex MINLP, and derive modifications that strengthen the linear programming relaxations of these models. We also introduce nonlinear programming formulations to choose piecewise-linear approximations and relaxations of multiple functions that share the same domain and use the same set of break points in the domain. We conclude with computational experiments that demonstrate that the proposed formulation is more accurate than the previous formulation, and that the strengthened MILP approximation and relaxation models can be used to obtain provably near-optimal solutions for large instances of this nonconvex MINLP. Experiments also illustrate the quality of the piecewise-linear approximations produced by our nonlinear programming formulations.

Keywords: Mixed Integer, Piecewise Linear Programming, Mixed Integer Non Linear Programming

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- Science and Engineering (Chemical Engineering )

Category 3: Applications -- Science and Engineering (Facility Planning and Design )


Download: [PDF]

Entry Submitted: 01/07/2014
Entry Accepted: 01/07/2014
Entry Last Modified: 01/07/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society