Models and Solution Techniques for Production Planning Problems with Increasing Byproducts

Srikrishna Sridhar, Jeff Linderoth and James R. Luedtke

Computer Sciences, Technical Report

Preprints

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 formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed formulation. We describe three different mixed-integer linear programming approximation and relaxation models of this formulation, and we show how to strengthen these models using integrality and monotonicity properties of the formulation. 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 to demonstrate the improved accuracy of the proposed formulation, compare the solution times of various models, and illustrate the quality of the piecewise-linear approximations produced by our nonlinear program- ming formulations.

Instances

Coming soon!