Existence Theorems of Quasivariational Inclusion Problems with Applications to Bilevel Problems and Mathematical Programs with Equilibrium Constraint

In this paper, we establish existence theorems of quasivariational inclusion problems; from them, we establish existence theorems of mathematical programs with quasivariational inclusion constraint, bilevel problems, mathematical programs with equilibrium constraint and semi-infinite problems. This research was supported by the National Science Council of the Republic of China. The authors express their gradtitude to the referees for valuable suggestions.     

On RSA moduli with almost half of the bits prescribed

We show that using character sum estimates due to H. Iwaniec leads to an improvement of recent results about the distribution and finding RSA moduli M=pl, where p and l are primes, with prescribed bit patterns. We are now able to specify about n bits instead of about n/2 bits as in the previous work. We also show that the same result of H. Iwaniec can be used to obtain an unconditional version of a combinatorial result of W. de Launey and D. Gordon that was originally derived under the Extended Riemann Hypothesis.     

A mixed integer programming model for multistage mean–variance post-tax optimization

In this paper, we introduce a mixed integer stochastic programming approach to mean–variance post-tax portfolio management. This approach takes into account of risk in a multistage setting and allows general withdrawals from original capital. The uncertainty on asset returns is specified as a scenario tree. The risk across scenarios is addressed using the probabilistic approach of classical stochastic programming. The tax rules are used with stochastic linear and mixed integer quadratic programming models to compute an overall tax and return-risk efficient multistage portfolio. The incorporation of the risk term in the model provides robustness and leads to diversification over wrappers and assets within each wrapper. General withdrawals and risk aversion have an impact on the distribution of assets among wrappers. Computational results are presented using a study with different scenario trees in order to show the performance of these models.     

GENERAL INFORMATION

In this note, we obtain a sufficient and necessary condition for a point to be a local minimizer of a continuous optimization problem with maximin constraints via the local minimizers of its transformed standard nonlinear optimization problem.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Optimization models for the single delay management problem in public transportation

Passengers travelling in public transportation networks often have to use different lines to cover the trip from their origin to the desired destination. As a consequence, the reliability of connections between vehicles is a key issue for the attractiveness of the intermodal transportation network and it is strongly affected by some unpredictable events like breakdowns or vehicle delays. In such cases, a decision is required to determine if the connected vehicles should wait for the delayed ones or keep their schedule. The delay management problem (DMP) consists in defining the wait/depart policy which minimizes the total delay on the network. In this work, we present two equivalent mixed integer linear programming models for the DMP with a single initial delay, able to reduce the number of variables with respect to the formulations proposed by the literature. The two models are solved by a branch and cut procedure and by a constraint generation approach respectively, and preliminary computational results are presented.     

Non-Deterministic Closure Theory and Universal Arrows

Traditional closure theory discusses the closure operations on orders with graph-theoretic methods, or the reflectors on skeletal categories with category-theoretic methods. Both approaches are confined, like most of classical mathematics, to total and deterministic operations. So traditional closure theory makes it possible to define the semantics of the while-do commands only for terminating and deterministic programming. This paper outlines a closure theory for relations which transcend totality and determinism. For the sake of conciseness, the language used is that of graph theory but the methods are category-theoretic and some hints are offered for a possible translation into the language of category theory. Our basic idea is that closure relations consist of universal arrows in the sense of category theory. The new closure theory is appropriate for defining a semantics of the while-do commands both for terminating, deterministic programming and for non-terminating, non-deterministic programming.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale nonlinear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis*, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

An algorithmic framework for convex mixed integer nonlinear programs

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available.     

On the greedy solution in integer linear programming

A version of the greedy method not using any knapsack relaxation of the integer programming problem is considered in this paper. It is based on a natural partial ordering of the vectors. Our aim is to determine a large class of problems where the greedy solution is always optimal. The results generalize some theorems of an early paper of Magazine, Nemhauser and Trotter and at the same time show a connection between two different notions of combinatorics: the greedy method and the Hilbert basis.

---

Zusammenfassung In dieser Arbeit wird eine Version des Greedy-Algorithmus zur Lösung ganzzahliger linearer Optimierungsprobleme benutzt, die kein Rucksackproblem als Relaxation verwendet. Das Verfahren basiert auf der natürlichen partiellen Ordnung von Vektoren. Ziel der Arbeit ist es, eine möglichst große Problemklasse zu beschreiben, für die die Greedy-Lösung optimal ist. Die Ergebnisse verallgemeinern Sätze einer früheren Arbeit von Magazine, Nemhauser und Trotter und zeigen gleichzeitig einen Bezug zwischen zwei verschiedenen Gebieten der Kombinatorik auf: des Greedy-Verfahrens und von Hubert-Basen.