On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

On multiple simple recourse models

We consider multiple simple recourse (MSR) models, both continuous and integer versions, which generalize the corresponding simple recourse (SR) models by allowing for a refined penalty cost structure for individual shortages and surpluses. It will be shown that (convex approximations of) such MSR models can be represented as explicitly specified continuous SR models, and thus can be solved efficiently by existing algorithms. This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.     

Approximate nonlinear programming algorithms for solving stochastic programs with recourse

This paper summarizes the main results on approximate nonlinear programming algorithms investigated by the author. These algorithms are obtained by combining approximation and nonlinear programming algorithms. They are designed for programs in which the evaluation of the objective functions is very difficult so that only their approximate values can be obtained. Therefore, these algorithms are particularly suitable for stochastic programming problems with recourse.Project supported by the National Natural Science Foundation of China.     

Portfolio theory for the recourse certainty equivalent maximizing investor

The portfolio selection problem with one safe andn risky assets is analyzed via a new decision theoretic criterion based on the Recourse Certainty Equivalent (RCE). Fundamental results in portfolio theory, previously studied under the Expected Utility criterion (EU), such as separation theorems, comparative static analysis, and threshold values for inclusion or exclusion of risky assets in the optimal portfolio, are obtained here. In contrast to the EU model, our results for the RCE maximizing investor do not impose restrictions on either the utility function or the underlying probability laws. We also derive a dual portfolio selection problem and provide it with a concrete economic interpretation.Research partly supported by ONR Contracts N0014-81-C-0236 and N00014-82-K-0295, and NSF Grant SES-8408134 with the Center for Cybernetic Studies, The University of Texas at Austin.Partly supported by NSF Grant DDM-8896112.Partly supported by AFOSR Grant 0218-88 and NSF Grant ECS-8802239 at the University of Maryland, Baltimore Campus.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Stochastic programming with integer variables

 Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing results in the field and indicate departure points for their extension. Received: December 2, 2002 / Accepted: April 23, 2003 Published online: May 28, 2003 Mathematics Subject Classification (2000): 90C15, 90C11, 90C06, 90C57     

An algorithm for the construction of convex hulls in simple integer recourse programming

We consider the objective function of a simple integer recourse problem with fixed technology matrix and discretely distributed right-hand sides. Exploiting the special structure of this problem, we devise an algorithm that determines the convex hull of this function efficiently. The results are improvements over those in a previous paper. In the first place, the convex hull of many objective functions in the class is covered, instead of only one-dimensional versions. In the second place, the algorithm is faster than the one in the previous paper. Moreover, some new results on the structure of the objective function are presented.     

Stochastic programs with recourse: An upper bound and the related moment problem

The probability measureP ^O on multidimensional intervals in the extension of the Edmundson-Madansky upper bound for stochastically dependent random variables, derived recently in [7], is shown to be the uniquely determined extremal solution of a particular multivariate moment problem. A necessary and sufficient condition for the feasibility of this moment problem is derived, which is shown to coincide for the univariate moment problem with the simplex containing the moment space (see [15]).A first draft of this paper was written during the authors stay at the Mathematics Research Center, University of Wisconsin-Madison, during January 1986, with support by the National Science Foundation, Grant No. DCR-8502202; the generous support by these institutions is greatly appreciated.     

Integrating local search techniques into mixed integer programming

We survey the main results of the authors PhD thesis that was supervised by Claude Le Pape (ILOG, France) and Philippe Michelon (Université dAvignon, France) and has been defended in June 2004. The dissertation is written in French and is available from the author. It introduces several strategies for integrating local search techniques into mixed integer programming, with an emphasis on generic algorithms.Received: June 2004, MSC classification: 90C11, 90C59     

Symmetric duality for minimax multiobjective variational mixed integer programming problems with partial-invexity

A pair of symmetric dual multiobjective variational mixed integer programs for the polars of arbitrary cones are formulated, which some primal and dual variables are constrained to belong to the set of integers. Under the separability with respect to integer variables and partial-invexity assumptions on the functions involved, we prove the weak, strong, converse and self-duality theorems to related minimax efficient solution. These results include some of available results.     

A simulation-based approach to two-stage stochastic programming with recourse

In this paper we consider stochastic programming problems where the objective function is given as an expected value function. We discuss Monte Carlo simulation based approaches to a numerical solution of such problems. In particular, we discuss in detail and present numerical results for two-stage stochastic programming with recourse where the random data have a continuous (multivariate normal) distribution. We think that the novelty of the numerical approach developed in this paper is twofold. First, various variance reduction techniques are applied in order to enhance the rate of convergence. Successful application of those techniques is what makes the whole approach numerically feasible. Second, a statistical inference is developed and applied to estimation of the error, validation of optimality of a calculated solution and statistically based stopping criteria for an iterative alogrithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), Brasília, Brazil, through a Doctoral Fellowship under grant 200595/93-8.     

Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis

In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the expected integer recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest improvements to reduce the number of function evaluations needed.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

非线性整数规划的一个近似算法

利用连续总体优化填充函数法的思想，本文设计了非线性整数规划的一个近似算法．首先，给出了非线性整数规划问题离散局部极小解的定义，设计了找离散局部极小解的局部搜索算法；其次，用所设计的局部搜索算法极小化填充函数来找比当前离散局部极小解好的解．本文的近似算法是直接法，且与连续总体优化的填充函数法相比，本文填充函数中的参数易于选取．数值试验表明，本文的近似算法是有效的．     

On structure and stability in stochastic programs with random technology matrix and complete integer recourse

For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure.Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.The main part of the paper was written while the author was an assistant at the Department of Mathematics at Humboldt University Berlin.     

Cartographic line simplification and polygon CSG formulæ in O(n log n) time

A constructive solid geometry (CSG) conversion for a polygon takes a list of vertices and produces a formula representing the polygon as an intersection and union of primitive halfspaces. The cartographers' favorite line simplification algorithm recursively selects from a list of data points those to be used to represent a linear feature, such as a coastline, on a map. By using a data structure that maintains convex hulls of polygonal lines under splits, both were known to have O(n log n) time solutions in the worst-case. This paper shows that both are easier than sorting by presenting an O(n log^* n) algorithm for maintaining convex hulls under splits at extreme points. It opens the question of whether there are practical, linear-time solutions to these problems.     

Ranking in integer linear fractional programming problems

An algorithm is developed which ranks the feasible solutions of an integer fractional programming problem in decreasing order of the objective function values.

---

Zusammenfassung Es wird ein Algorithmus angegeben, der die zulässigen Lösungen eines ganzzahligen Quotientenprogrammes nach fallenden Zielfunktionswerten liefert.

     

An integral transformation for integer programming problems

It is shown that every integer programming problem can be transformed into an equivalent integer program with free variables in polynomial time. The transformation is advantageous because the equivalent problem it generates can be solved very easily in some restricted cases.     

一个新的非线性整数规划问题的单参数填充函数算法

非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法.构造一个新的单参数填充函数,分析并证明了其填充性质;然后,基于该填充函数并结合离散最速下降法提出了一种新的填充函数算法;最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的.