Asymmetry and Ambiguity in Newsvendor Models

The traditional decision-making framework for newsvendor models is to assume a distribution of the underlying demand. However, the resulting optimal policy is typically sensitive to the choice of the distribution. A more conservative approach is to assume that the distribution belongs to a set parameterized by a few known moments. An ambiguity-averse newsvendor would choose … Read more

Representation of nonnegative convex polynomials

We provide a specific representation of convex polynomials nonnegative on a convex (not necessarily compact) basic closed semi-algebraic set $K$ of $R^n$. Namely, they belong to a specific subset of the quadratic module generated by the concave polynomials that define $K$. Citation To appear in Archiv der Mathematik Article Download View Representation of nonnegative convex … Read more

A New Full-Newton step (n)$ Infeasible Interior-Point Algorithm for Semidefinite Optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed an efficient primal-dual infeasible interior-point algorithm with full Newton steps for linear optimization problems. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence … Read more

Hybrid GRASP heuristics

Experience has shown that a crafted combination of concepts of different metaheuristics can result in robust combinatorial optimization schemes and produce higher solution quality than the individual metaheuristics themselves, especially when solving difficult real-world combinatorial optimization problems. This chapter gives an overview of different ways to hybridize GRASP (Greedy Randomized Adaptive Search Procedures) to create … Read more

GRASP: Basic components and enhancements

GRASP (Greedy Randomized Adaptive Search Procedures) is a multistart metaheuristic for producing good-quality solutions of combinatorial optimization problems. Each GRASP iteration is usually made up of a construction phase, where a feasible solution is constructed, and a local search phase which starts at the constructed solution and applies iterative improvement until a locally optimal solution … Read more

GRASP

GRASP is a multi-start metaheuristic for combinatorial optimization problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. An intensification … Read more

GRASP: Advances and applications

GRASP is a multi-start metaheuristic for combinatorial optimization problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this … Read more

Extended Formulations for Packing and Partitioning Orbitopes

We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch (Math. Program. 114 (1), 2008, 1-36). These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, resp. exactly, one 1-entry per row. They are … Read more

On Non-Convex Quadratic Programming with Box Constraints

Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more