A quadratic programming approach to the multi-product newsvendor problem with side constraints

A quadratic programming approach is proposed for solving the newsvendor problem with side constraints. Among its salient features are the facts that it: utilizes familiar packages to solve the problem such as Excel Solver and Lingo, can accommodate lower bounds of product’s demands that are larger than zero, and facilitates the performance of sensitivity analysis tasks.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

A linear programming approach to solving bilinear programmes

This paper discusses the maximization of a bilinear function over two independent polytopes. The maximization problem is converted into a max—min problem, using duality. This problem is then solved via a sequence of dual linear programmes, whose constraint vectors are successively determined bytth order optima of a master linear programme.     

Risk optimization with p-order conic constraints: A linear programming approach

The paper considers solving of linear programming problems with p-order conic constraints that are related to a certain class of stochastic optimization models with risk objective or constraints. The proposed approach is based on construction of polyhedral approximations for p-order cones, and then invoking a Benders decomposition scheme that allows for efficient solving of the approximating problems. The conducted case study of portfolio optimization with p-order conic constraints demonstrates that the developed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods.     

A geometric approach for solving fuzzy linear programming problems

In this paper we first recall some definitions and results of fuzzy plane geometry, and then introduce some definitions in the geometry of two-dimensional fuzzy linear programming (FLP). After defining the optimal solution based on these definitions, we use the geometric approach for obtaining optimal solution(s) and show that the algebraic solutions obtained by Zimmermann method (ZM) and our geometric solutions are the same. Finally, numerical examples are solved by these two methods.     

Determining order quantities in multi-product inventory systems subject to multiple constraints and incremental discounts

This paper presents a mixed-integer programming model for ordering items in multi-product multi-constraint inventory systems from suppliers who offer incremental quantity discounts. The model is based on a piecewise linear approximation of the number of orders function. It allows any number of linear constraints and determines if independent or common (fixed) cycle ordering has a lower total cost. The paper discusses implementation issues and presents results of computational tests on example problems from the operational research literature as well as randomly generated test problems.     

The multi-product newsboy problem with supplier quantity discounts and a budget constraint

This paper considers the multi-product newsboy problem with both supplier quantity discounts and a budget constraint, while each feature has been addressed separately in the literature. Different from most previous nonlinear optimization models on the topic, the problem is formulated as a mixed integer nonlinear programming model due to price discounts. A Lagrangian relaxation approach is presented to solve the problem. Computational results on both small and large-scale test instances indicate that the proposed algorithm is extremely effective for the problem. An extension to multiple constraints and preliminary computational results are also reported.     

Multi-tier binary solution method for multi-product newsvendor problem with multiple constraints

This paper considers a multi-product newsvendor problem with multiple constraints. Multiple constraints in the problem make it more challenging to solve. Previous research has attempted to solve the problem by considering two-constraint case or/and using approximation techniques or active sets methods. The solution methods in literature for solving multi-constraint problem are limited or cumbersome. In this paper, by analyzing structural properties of the multi-constraint multi-product newsvendor problem, we develop a multi-tier binary solution method for yielding the optimal solution to the problem. The proposed method is applicable to the problem with any continuous demand distribution and more than two constraints, and its computational complexity is polynomial in the number of products. Numerical results are presented for showing the effectiveness of our method.     

Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming

Duality results are established in convex programming with the set-inclusive constraints studied by Soyster. The recently developed duality theory for generalized linear programs by Thuente is further generalized and also brought into the framework of Soyster's theory. Convex programming with set-inclusive constraints is further extended to fractional programming.     

Non-differentiable symmetric duality for multiobjective programming with cone constraints

Two pairs of non-differentiable multiobjective symmetric dual problems with cone constraints over arbitrary cones, which are Wolfe type and Mond–Weir type, are considered. On the basis of weak efficiency with respect to a convex cone, we obtain symmetric duality results for the two pairs of problems under cone-invexity and cone-pseudoinvexity assumptions on the involved functions. Our results extend the results in Khurana [S. Khurana, Symmetric duality in multiobjective programming involving generalized cone-invex functions, European Journal of Operational Research 165 (2005) 592–597] to the non-differentiable multiobjective symmetric dual problem.     

Using separable programming to solve the multi-product multiple ex-ante constraint newsvendor problem and extensions

This paper provides an approximating programming technique to solve the multi-product newsvendor model in which product demands are independent and stocking quantities are subject to two or more ex-ante linear contraints, such as budget or volume constraints. Previous research has attempted to solve this problem with Lagrange relaxation techniques or by limiting the distribution of demand. However, by taking advantage of the separable nature of the problem, a close approximation of the optimal solution can be found using convex separable programming for any demand distribution in the traditional newsvendor model and extensions. Sensitivity analysis of the linear program provides managerial insight into the effects of parameters of the problem on the optimal solution and future decisions.     

A hybrid heuristic and linear programming approach to multi-product machine scheduling

A new heuristic approach is presented for scheduling economic lots in a multi-product single-machine environment. Given a pre-defined master sequence of product setups, an integer linear programming formulation is developed which finds an optimal subsequence and optimal economic lots. The model takes explicit account of initial inventories, setup times and allows setups to be scheduled at arbitrary epochs in continuous time, rather than restricting setups to a discrete time grid. We approximate the objective function of the model and solve to obtain an optimal capacity feasible schedule for the approximate objective. The approach was tested on a set of randomly generated problems, generating solutions that are on average 2.5% above a lower bound on the optimal cost. We also extend the approach to allow shortages.     

Mathematical programming approach to the Petri nets reachability problem

This paper focuses on the resolution of the reachability problem in Petri nets, using the mathematical programming paradigm. The proposed approach is based on an implicit traversal of the Petri net reachability graph. This is done by constructing a unique sequence of Steps that represents exactly the total behaviour of the net. We propose several formulations based on integer and/or binary linear programming, and the corresponding sets of adjustments to the particular class of problem considered. Our models are validated on a set of benchmarks and compared with standard approaches from IA and Petri nets community.     

A semidefinite programming approach to the generalized problem of moments

We consider the generalized problem of moments (GPM) from a computational point of view and provide a hierarchy of semidefinite programming relaxations whose sequence of optimal values converges to the optimal value of the GPM. We then investigate in detail various examples of applications in optimization, probability, financial economics and optimal control, which all can be viewed as particular instances of the GPM. This work was supported by french ANR-grant NT05-3-41612, and part of it was completed in January 2006 while the author was a member of IMS, the Institute for Mathematical Sciences of NUS (The National University of Singapore).     

Solution approach to infinite linear programming problem with capacity constraints

The purpose of this article is to investigate a kind of infinite linear programming problem (ILPP) arising from infinite multiclass network equilibrium problems. In several cases, we construct special feasible solutions to the ILPP. By virtue of the nature of network, we prove that the solutions are optimal. Marcotte and Zhu (Oper Res Lett 37:211?C214, 2009) proved the existence of the valid tolls for the infinite multiclass network equilibrium problems. Based on this, we analyze the property of the tolls vector, i.e., the relationship between breakpoints and the tolls. We also consider the solutions in the network where origin-destination pairs may differ in their probability density functions.     

On alternative optimal solutions to quasimonotonic programming with linear constraints

In this paper, the nonlinear programming problem with quasimonotonic （ both quasiconvex and quasiconcave ）objective function and linear constraints is considered. With the decomposition theorem of polyhedral sets, the structure of optimal solution set for the programming problem is depicted. Based on a simplified version of the convex simplex method, the uniqueness condition of optimal solution and the computational procedures to determine all optimal solutions are given, if the uniqueness condition is not satisfied. An illustrative example is also presented.     

A mathematical programming approach to key-based election analysis

This article describes a fast, easily implemented MILP algorithm which selects optimal boolean factors (called keys) for predicting the outcomes of Presidential elections in the United States. Results derived from the method support the validity and parsimony of the key-based election model offered by Lichtman and Keilis-Borok.     

Lagrangean decomposition for integer nonlinear programming with linear constraints

We present a Lagrangean decomposition to study integer nonlinear programming problems. Solving the dual Lagrangean relaxation we have to obtain at each iteration the solution of a nonlinear programming with continuous variables and an integer linear programming. Decreasing iteratively the primal—dual gap we propose two algorithms to treat the integer nonlinear programming.This work was partially supported by CNPq and FINEP.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.     

Relaxations of linear programming problems with first order stochastic dominance constraints

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.