This paper presents a new data classification method based on mixed-integer programming. Traditional approaches that are based on partitioning the data sets into two groups perform poorly for multi-class data classification problems. The proposed approach is based on the use of hyper-boxes for defining boundaries of the classes that include all or some of the … Read more
Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more
The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more
We show that for any fixed rank, the closure of a set covering problem (and related problems) can be approximated in polynomial time — we can epsilon-approximate any linear program over the closure in polynomial time. Citation CORC report TR-2003-01, Computational Optimization Research Center, Columbia University Article Download View Approximate fixed-rank closures of set covering … Read more
Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the … Read more
We present a simulation-based analytic center cutting plane method to solve a sample average approximation of a call center problem of minimizing staffing costs, while maintaining an acceptable level of service in multiple time periods. We establish convergence of the method when the service level functions are discrete pseudoconcave. An extensive numerical study of a … Read more
We extend a static mixed intger diajunctive (MID) transmission expansion planning model so as to deal with circuit contingency criterion. The model simultaneously represents the network constraints for base case and each selected circuit contingency. The MID approach aloows a commercial optimization solver to achieve and prove solution aptimiality. The proposed approach is applied to … Read more
One of the main issues in the glass industry is the minimization of the trim loss generated when cutting large parts (stocks) into small items. In our application stocks are produced in the plant. Many distinct stock sizes are feasible, and technical constraints limit the variety of cutting patterns to those producing a single type … Read more
We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more
We present the optimization component of a decision support system developed for a sedan service provider. The system assists supervisors and dispatchers in scheduling driver shifts and routing the fleet throughout the day to satisfy customer demands within tight time windows. We periodically take a snapshot of the dynamic data and formulate an integer program, … Read more