This paper presents an annotated bibliography of greedy randomized adaptive search procedures (GRASP). The bibliography is current up to early 2004. The bibliography contains: background material; tutorials and surveys; enhancements to the basic method; hybrid methods; software; parallel GRASP; graph theory; quadratic and other assignment problems; location, layout, and cutting; covering, clustering, packing, and partitioning; … Read more
In multicriteria optimization, several objective functions, conflicting with each other, have to be minimized simultaneously. We propose a new efficient method for approximating the solution set of a multiobjective programming problem, where the objective functions involved are arbitary convex functions and the set of feasible points is convex. The method is based on generating warm-start … Read more
We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more
In many industrial settings, managers face the problem of establishing a pricing policy that maximizes the revenue from selling a given inventory of items by a fixed deadline, with the full inventory of items being available for sale from the beginning of the selling period. This problem arises in a variety of industries, including the … Read more
In this paper we propose a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. At each iteration, the method would select a target on the central path with a large update from the current iterate, and then the Newton method is used to get the search directions, followed by … Read more
We consider knapsack constraints involving one general integer and many binary variables. We introduce the concept of a cover for such a constraint and we construct a new family of valid inequalities based on this concept. We generalize this idea to extended covers, and we propose a specialized lifting procedure for cover inequalities. Finally, we … Read more
We introduce an axiomatic definition of a conditional convex risk mapping and we derive its properties. In particular, we prove a representation theorem for conditional risk mappings in terms of conditional expectations. We also develop dynamic programming relations for multistage optimization problems involving conditional risk mappings. Citation Preprint Article Download View Conditional Risk Mappings
We consider sets defined by the usual stochastic ordering relation and by the second order stochastic dominance relation. Under fairy general assumptions we prove that in the space of integrable random variables the closed convex hull of the first set is equal to the second set. Article Download View Convexification of Stochastic Ordering
The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of boolean formulas in $3$-conjunctive normal form as such an intersection. The corresponding approximation problems are shown $NP$-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown $W[P]$-hard. … Read more
We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely … Read more