Some Relations Between Facets of Low- and High-Dimensional Group Problems

In this paper, we introduce an operation that creates families of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. We call this family sequential-merge inequalities because they are produced by applying two group cuts one after the other and because the resultant inequality depends on the order of the … Read more

An Integer Programming Approach to the Path Selection Problems

We consider two types of path selection problems defined on arc-capacitated networks. Given an arc-capacitated network and a set of selected ordered pairs of nodes (commodity) each of which has a demand quantity, the first problem is to select a subset of commodities and setup one path for each chosen commodity to maximize profit, while … Read more

A Computational Analysis of Lower Bounds for Big Bucket Production Planning Problems

In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to … Read more

Convex duality and entropy-based moment closure: Characterizing degenerate densities

A common method for constructing a function from a finite set of moments is to solve a constrained minimization problem. The idea is to find, among all functions with the given moments, that function which minimizes a physically motivated, strictly convex functional. In the kinetic theory of gases, this functional is the kinetic entropy; the … Read more

The Value of Information in Inventory Management

Inventory management traditionally assumes the precise knowledge of the underlying demand distribution and a risk-neutral manager. New product introduction does not fit this framework because (i) not enough information is available to compute probabilities and (ii) managers are generally risk-averse. In this work, we analyze the value of information for two-stage inventory management in a … Read more

The Value of Information in the Newsvendor Problem

In this work, we investigate the value of information when the decision-maker knows whether a perishable product will be in high, moderate or low demand before placing his order. We derive optimality conditions for the probability of the baseline scenario under symmetric distributions and analyze the impact of the cost parameters on simulation experiments. Our … Read more

Self-concordant Tree and Decomposition Based Interior Point Methods for Stochastic Convex Optimization Problem

We consider barrier problems associated with two and multistage stochastic convex optimization problems. We show that the barrier recourse functions at any stage form a self-concordant family with respect to the barrier parameter. We also show that the complexity value of the first stage problem increases additively with the number of stages and scenarios. We … Read more

On the Extension of a Mehrotra-Type Algorithm for Semidefinite Optimization

It has been shown in various papers that most interior-point algorithms and their analysis can be generalized to semidefinite optimization. This paper presents an extension of the recent variant of Mehrotra’s predictor-corrector algorithm that was proposed by Salahi et al. (2005) for linear optimization problems. Based on the NT (Nesterov and Todd 1997) direction as … Read more

A Coordinate Gradient Descent Method for Linearly Constrained Smooth Optimization and Support Vector Machines Training

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. … Read more

On the probabilistic complexity of finding an approximate solution for linear programming

We consider the problem of finding an $\epsilon-$optimal solution of a standard linear program with real data, i.e., of finding a feasible point at which the objective function value differs by at most $\epsilon$ from the optimal value. In the worst-case scenario the best complexity result to date guarantees that such a point is obtained … Read more