-
作者：Berstein, Y.; Lee, J.; Onn, S.; Weismantel, R.
作者单位：International Business Machines (IBM); IBM USA; Technion Israel Institute of Technology; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We address optimization of parametric nonlinear functions of the form f(Wx), where f : R-d -> R is a nonlinear function, W is a d x n matrix, and feasible x are in some large finite set F of integer points in R-n. Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f, W and F. One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W. Another motivat...
-
作者：Kaparis, Konstantinos; Letchford, Adam N.
作者单位：Lancaster University; University of Southampton
摘要：Valid inequalities for 0-1 knapsack polytopes often prove useful when tackling hard 0-1 Linear Programming problems. To generate such inequalities, one needs separation algorithms for them, i.e., routines for detecting when they are violated. We present new exact and heuristic separation algorithms for several classes of inequalities, namely lifted cover, extended cover, weight and lifted pack inequalities. Moreover, we show how to improve a recent separation algorithm for the 0-1 knapsack pol...
-
作者：Martens, Maren; McCormick, S. Thomas; Queyranne, Maurice
作者单位：University of British Columbia; Zuse Institute Berlin
摘要：Production planning problems such as an Available to Promise (ATP) model of Chen et al. (2002) can involve material compatibility constraints that specify when components from various suppliers can be feasibly assembled into a final product. In a companion paper to Chen et al. (2002), Ball et al. (2003) showed that in many cases such constraints can be modeled as the set of feasible source-sink flows through an acyclic network. The flow through a node is the sum of the flows on all paths conta...
