A continuous approach for the concave cost supply problem via DC programming and DCA

The paper addresses an important but difficult class of concave cost supply management problems which consist in minimizing a separable increasing concave objective function subject to linear and disjunctive constraints. We first recast these problems into mixed zero-one nondifferentiable concave minimization over linear constraints problems and then apply exact penalty techniques to state equivalent nondifferentiable polyhedral DC (Difference of Convex functions) programs. A new deterministic approach based on DC programming and DCA (DC Algorithms) is investigated to solve the latter ones. Finally numerical simulations are reported which show the efficiency, the robustness and the globality of our approach.     

A decomposition algorithm for solving certain classes of production-transportation problems with concave production cost

This paper addresses a method for solving two classes of production-transportation problems with concave production cost. By exploiting a special network structure both problems are reduced to a kind of resource allocation problem. It is shown that the resultant problem can be solved by using dynamic programming in time polynomial in the number of supply and demand points and the total demand.The author was partially supported by Grand-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)05650061.     

Application of average dynamic programming to inventory systems

We show the existence ofaverage cost (AC-) optimal policy for an inventory system withuncountable state space; in fact, the AC-optimal cost and an AC-optimal stationary policy areexplicitly computed. In order to do this, we use a variant of thevanishing discount factor approach, which have been intensively studied in recent years but the available results not cover the inventory problem we are interested in.The work of the first author (OVA) was partially supported by Fondo del Sistema de Investigación del Mar de Cortéz under grant SIMAC/94/CT-005. The work of the second author (RMdO) was partially supported by Consejo Nacional de Ciencia y Tecnologia (CONACyT) under grant 0635P-E9506.     

A deterministic inventory/production model with general inventory cost rate function and piecewise linear concave production costs

We present a thorough analysis of the economic production quantity model with shortages under a general inventory cost rate function and piecewise linear concave production costs. Consequently, an effective solution procedure, particularly useful for an approximation scheme, is proposed. A computational study is appended to illustrate the performance of the proposed solution procedure.     

Continuity properties of the Karush-Kuhn-Tucker point set in quadratic programming problems

Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998     

A hybrid model for airline seat inventory control of the multi-leg problems

To address the discrepancy between dynamic models and industrial practice in airline revenue management, we propose a hybrid model for the multi-leg problem that integrates static and dynamic models. We formulate the problem using a stochastic dynamic program and characterize the optimal booking policy as a switching-curve (surface) type.     

Basis- and partition identification for quadratic programming and linear complementarity problems

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus. Received April 9, 1996 / Revised version received April 27, 1998? Published online May 12, 1999     

Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems

ln) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρ_f is a feasibility measure. We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility (primal or dual) can be detected in O(ln) iterations, where ρ_· is a primal or dual infeasibility measure. Received April 25, 1996 / Revised version received March 4, 1998 Published online October 9, 1998     

Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms

We study the mixed 0-1 knapsack polytope, which is defined by a single knapsack constraint that contains 0-1 and bounded continuous variables. We develop a lifting theory for the continuous variables. In particular, we present a pseudo-polynomial algorithm for the sequential lifting of the continuous variables and we discuss its practical use.This research was supported by NSF grants DMI-0100020 and DMI-0121495Mathematics Subject Classification (2000): 90C11, 90C27     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

Optimal control problems on manifolds: a dynamic programming approach

Dynamic programming identifies the value function of continuous time optimal control with a solution to the Hamilton-Jacobi equation, appropriately defined. This relationship in turn leads to sufficient conditions of global optimality, which have been widely used to confirm the optimality of putative minimisers. In continuous time optimal control, the dynamic programming methodology has been used for problems with state space a vector space. However there are many problems of interest in which it is necessary to regard the state space as a manifold. This paper extends dynamic programming to cover problems in which the state space is a general finite-dimensional C^∞ manifold. It shows that, also in a manifold setting, we can characterise the value function of a free time optimal control problem as a unique lower semicontinuous, lower bounded, generalised solution of the Hamilton-Jacobi equation. The application of these results is illustrated by the investigation of minimum time controllers for a rigid pendulum.     

Testing optimality for quadratic 0-1 problems

Received June 4, 1996 / Revised version received November 19, 1997 Published online November 24, 1998     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001     

A note on negative dynamic programming for risk-sensitive control

Negative dynamic programming for risk-sensitive control is studied. Under some compactness and semicontinuity assumptions the following results are proved: the convergence of the value iteration algorithm to the optimal expected total reward, the Borel measurability or upper semicontinuity of the optimal value functions, and the existence of an optimal stationary policy.     

Computational study of a column generation algorithm for bin packing and cutting stock problems

This paper reports on our attempt to design an efficient exact algorithm based on column generation for the cutting stock problem. The main focus of the research is to study the extend to which standard branch-and-bound enhancement features such as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be usefully incorporated in a branch-and-price algorithm. We review and compare lower bounds for the cutting stock problem. We propose a pseudo-polynomial heuristic. We discuss the implementation of the important features of the integer programming column generation algorithm and, in particular, the implementation of the branching scheme. Our computational results demonstrate the efficiency of the resulting algorithm for various classes of bin packing and cutting stock problems. Received October 18, 1996 / Revised version received May 14, 1998?Published online July 19, 1999     

An improved rounding method and semidefinite programming relaxation for graph partition

Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming (SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut, and Max-Vertex-Cover. Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002     

Approximate dynamic programming for stochastic linear control problems on compact state spaces

This paper addresses Markov Decision Processes over compact state and action spaces. We investigate the special case of linear dynamics and piecewise-linear and convex immediate costs for the average cost criterion. This model is very general and covers many interesting examples, for instance in inventory management. Due to the curse of dimensionality, the problem is intractable and optimal policies usually cannot be computed, not even for instances of moderate size.     

A dual dynamic programming for minimax optimal control problems governed by parabolic equation

In the article, minimax optimal control problems governed by parabolic equations are considered. We apply a new dual dynamic programming approach to derive sufficient optimality conditions for such problems. The idea is to move all the notions from a state space to a dual space and to obtain a new verification theorem providing the conditions, which should be satisfied by a solution of the dual partial differential equation of dynamic programming. We also give sufficient optimality conditions for the existence of an optimal dual feedback control and some approximation of the problem considered, which seems to be very useful from a practical point of view.