Issue 1, Volume 22, June 1997

1997 · Open access

1. Foreword PDF

   5-6
2. RECOGNIZING FACET DEFINING INEQUALITIES E. BALAS PDF

   ▸ Abstract

   We discuss a method for determining whether a valid inequality for a 0-1 polytope is facet defining. The method is based on a
   new procedure for generating a sequence of 0-1 points on a face of the polytope, guaranteed to be linearly independent. The sequence moves along $k$-dimensional surfaces of the face, and whenever this is possible for small $k$, the procedure becomes particularly simple. As a result, we give a new sufficient condition for a valid inequality to be facet defining, that generalizes several earlier conditions. We also give a necessary and sufficient condition. None of these conditions is always verifiable in polynomial time. yet in many situations their use has led to the discovery of new classes of facets. We illustrate this on the case of the vertex packing and set covering polyhedra.

   7-28
3. GENERATING THE EFFICIENT OUTCOME SET IN MULTIPLE OBJECTIVE LINEAR PROGRAMS: THE BICRITERIA CASE HAROLD P. BENSON PDF

   ▸ Abstract

   This article presents an algorithm called OUTSET for generating the efficient outcome set of a multiple objective linear program (BX) with two objective functions. Unlike standard vector maximization approaches to generate the efficient decision set for problem (BX), which can be large and quite complicated. Instead, it directly generates the efficient faces of the smaller, simpler efficient outcome set. As a result, it is expected that in practice, the OUTSET algorithm will have the potential to allow decision makers to solve bicriteria linear programming problems relatively easily and accurately, including those large-scale problems that heretofore were too large to be amenable to standard vector maximization methods for multiple objective linear programming.

   29-51
4. CHARACTERIZATIONS OF BANACH SPACES VIA CONVEX AND OTHER LOCALLY LIPSCHITZ FUNCTIONS J. BORWEIN, M. FABIAN, J. VANDERWERFF PDF

   ▸ Abstract

   Various properties of Banach spaces, including the reflexivity and the Schur property of a space, are characterized in terms of properties of corresponding classes of locally Lipschitz functions on those spaces.

   53-69
5. OPTIMIZATION OF C-ORTHOGONAL POSYNOMIALS K. H. ELSTER, R. ELSTER PDF

   ▸ Abstract

   We introduce a new class of posynomials, called c-orthogonal posynomials, and we consider the corresponding c-orthogonal programs. The treatment of such programs is motivated by the fact that c-orthogonal posynomial programs having a positive degree of difficulty can be solved under weak assumptions, while ''normal" posynomial programs with such a positive degree reduce in general the spectacular power of geometric programming. The optimal value of an unconstrained or constrained c-orthogonal program is equal to the sum of (positive) coefficients of the objectives, respectively. Especially, using the gained results several interesting inequalities can be proved in a simple way.

   71-105
6. LP RELAXATIONS BETTER THAN CONVEXIFICATION FOR MULTICOMMODITY NETWORK OPTIMIZATION PROBLEMS WITH STEP INCREASING COST FUNCTIONS V. GABREL, M. MINOUX PDF

   ▸ Abstract

   We address here a class of particularly hard-to-solve combinatorial optimization problems namely multicommodity network optimization when the link cost functions are discontinuous step increasing. The main focus is on the development of relaxations for such problems in order to derive lower bounds. A straightforward way of getting lower bounds is to solve the “convexification” of the problem, i.e. a minimum cost multicommodity flow problem in which each link cost function is replaced by its best lower convex approximation. We propose here an alternative relaxation of the problem in terms of a large scale LP model, which can be solved by a generalized linear programming approach. Computational results on a series of test problems, typical of telecommunication networks, are presented showing that this relaxation leads to lower bounds strictly improving upon convexification in all the examples treated (the values of the improvement typically ranging from 10 to 20%).
   As far as we know, this is the first time a systematic way of generating bounds better than convexification to multicommodity network optimization problems with discontinuous step increasing cost functions is proposed.

   123-145
7. REDUCTION OF MONOTONE LINEAR COMPLEMENTARITY PROBLEMS OVER CONES TO LINEAR PROGRAMS OVER CONES M. KOJIMA, M. SHIDA, S. SHINDOH PDF

   ▸ Abstract

   This short note presents a constructive way of reducing monotone LCPs (linear complementarity problems) over cones to LPs (linear programs) over cones. In particular, the monotone semidefinite linear complementarity problem (SDLCP) in symmetric matrices, which was recently proposed by Kojima, Shindoh and Hara, is reducible to an SDP (semidefinite program). This gives a negative answer to their question whether the monotone SDLCP in symmetric matrices is an essential generalization of the SDP.

   147-157
8. A PSEUDO-POLYNOMIAL ALGORITHM FOR SOLVING RANK THREE CONCAVE PRODUCTION-TRANSPORTATION PROBLEMS TAKAHITO KUNO PDF

   ▸ Abstract

   In this paper, we extend the parametrization technique of Tuy et al. into a class of concave production-transportation problems with $m$ $(\geq 3)$ sources, $n$ terminals and three nonlinear variables. We develop a depth-first-search algorithm for finding a globally optimal solution of this rank three concave minimization problem and show that the algorithm is pseudo-polynonomial in the problem input length but polynomial in $m$ and $n$.

   159-182
9. PIVOTING ALGORITHMS BASED ON BOOLEAN VECTOR LABELING HANS VAN MAAREN PDF

   ▸ Abstract

   We reconsider complementary pivoting algorithms on the base of a modified form of Scarf’s primitive sets and Tuy’s abstract pivotal method. Here, the pivots are to be controled by a new type of labeling. The analysis of the limiting stage provides a new variety of fixed point results, where the usual convexity assumptions are relaxed drastically. The results mentioned also connect separation and fixed point theory in a natural way and are even applicable outside the domain of linear spaces. Moreover, they focus on the differences between integer and vector labeling in a very accurate manner.

   183-198
10. SOLUTION OF GENERAL LINEAR COMPLEMENTARITY PROBLEMS VIA NONDIFFERENTIABLE CONCAVE MINIMIZATION O. L. MANGASARIAN PDF

    ▸ Abstract

    Finite termination, at point satisfying the minimum principle necessary optimality condition, is established for a stepless (no line
    search) successive linearization algorithm (SLA) for minimizing a nondifferentiable concave function on a polyhedral set. The SLA is then applied to the general linear complementarity problem (LCP), formulated as minimizing a piecewise-linear concave error function on the usual polyhedral feasible region defining the LCP. When the feasible region is nonempty, the concave error function always has a global minimum at a vertex, and the minimum is zero if and only if the LCP is solvable. The SLA terminates at a solution or stationary point of the problem in a finite number of steps. A special case of the proposed algorithm [8] solved without failure 80 consecutive cases of the LCP formulation of the knapsack feasibilty problem, ranging in size between 10 and 3000.

    199-205
11. LEXICOGRAPHICAL CHARACTERIZATION OF THE FACES OF CONVEX SETS J. E. MARTINEZ-LEGAZ PDF

    ▸ Abstract

    We prove that a nonempty proper subset of a convex set $C$ is a face if and only if it is the set of points where a linear mapping achieves its lexicographical maximum over $C$.

    207-211
12. A REMARK ON VECTOR-VALUED EQUILIBRIA AND GENERALIZED MONOTONICITY W. OETTLI PDF

    ▸ Abstract

    It is the purpose of this note to show that existence results for vector-valued equilibria, of the type considered recently in [1] or [2],
    can be deduced in a straightforward way from corresponding results about scalar-valued equilibria. We shall proceed as follows. First we prove an existence result for scalar-valued equilibria, employing a certain notion of generalized monotonicity, and from this we deduce several results for the vector-valued case, by using appropriate gauge functions.

    213-221
13. QUASIDIFFERENTIABLE FUNCTIONS AND PAIRS OF CONVEX COMPACT SETS D. PALLASCHKE, R. URBANSKI PDF

    ▸ Abstract

    In the theory of optimization several types of piecewise differentiable functions occur in a quite natural way. As a typical example
    for such nondifferentiable functions we mention the finite max-min combinations of differentiable functions. A more general class are the quasidifferentiable functions, which are investigated in detail by V. F. Demyanov and A. M. Rubinov (see for instance [1]).
    The directional derivatives of these functions can be represented as a difference of two sublinear functions. Since a sublinear function is uniquely described by its subdifferential in the origin, there exists a natural correspondence between the directional derivatives and the set of pairs of convex compact sets. In this paper we give a comprehensive representation of the results in [5], [6] and [7]. Moreover we show that there exists a natural definition for the difference between pairs of convex compact sets.

    223-243
14. CONVEX ENVELOPES OF MULTILINEAR FUNCTIONS OVER A UNIT HYPERCUBE AND OVER SPECIAL DISCRETE SETS HANIF D. SHERALI PDF

    ▸ Abstract

    In this paper, we present some general as well as explicit characterizations of the convex envelope of multilinear functions defined over a unit hypercube. A new approach is used to derive this characterization via a related convex hull representation obtained by applying the Reformulation-Linearization Technique (RLT) of Sherali and Adams (1990, 1994). For the special cases of multilinear functions having coefficients that are either all +1 or all -1, we develop explicit formulae for the corresponding convex envelopes. Extensions of these results are given for the case when the multilinear function is defined over discrete sets, including explicit formulae for the foregoing special cases when this discrete set is represented by generalized upper bounding (GUB) constraints in binary variables. For more general cases of multilinear functions, we also discuss how this construct can be used to generate suitable relaxations for solving nonconvex optimization problems that include such structures.

    245-270
15. A GLOBAL OPTIMIZATION METHOD FOR MINIMUM MAXIMAL FLOW PROBLEM J. SHI, Y. YAMAMOTO PDF

    ▸ Abstract

    In this paper, we present two approaches for solving an $\mathcal{NP}$-hard problem: minimum maximal flow problem, i.e., $\min\{\| \xi\|\,| \, \xi \text{ is a maximal flow}\}$. We introduce lower bounds on flow, and cast the problem into a minimization of a concave function over a convex set. We solve the problem by a global optimization method. As an application, we consider the minimum maximal matching problem. Some numerical experiments are also reported.

    271-287
16. CONVEX ANALYSIS APPROACH TO D. C. PROGRAMMING: THEORY, ALGORITHMS AND APPLICATIONS PHAM DINH TAO, LE THI HOAI AN PDF

    ▸ Abstract

    This paper is devoted to a thorough study on convex analysis approach to d.c. (difference of convex functions) programming and gives the State of the Art. Main results about d.c. duality, local and global optimalities in d.c. programming are presented. These materials constitute the basis of the DCA (d.c. algorithms). Its convergence properties have been tackled in detail, especially in d.c. polyhedral programming where it has finite convergence. Exact penalty, Lagrangian duality without gap, and regularization techniques have been studied to find appropriate d.c. decompositions and to improve consequently the DCA. Finally we present
    the application of the DCA to solving a lot of important real-life d.c. programs.

    289-355
17. A NEW BOUNDING TECHNIQUE IN BRANCH-AND-BOUND ALGORITHMS FOR MIXED INTEGER PROGRAMMING TRAN VU THIEU, TRAN XUAN SINH PDF

    ▸ Abstract

    A branch-and-bound algorithm using a new bounding technique is presented for solving the mixed integer problem. The technique
    involves considering a piecewise linear and concave function of a parameter $\lambda\in\mathbb R^1$ whose maximum gives the largest lower bound. A parametric method is developed for finding the maximum of a such function.

    357-366
18. A RELAXATION ALGORITHM FOR SOLVING MIXED INTEGER PROGRAMMING PROBLEMS NGUYEN VU TIEN, LE DUNG MUU PDF

    ▸ Abstract

    We propose an algorithm for solving mixed integer linear programming problem, which is a combination of branch-and-bound and
    decomposition procedure. For branching and bounding we divide a rectangular domain into smaller and smaller subrectangles, and to each generated subrectangle $R$ we associate a lower bound for the objective function with respect to $y\in R$ by using a suitable relaxation involving the continuous linear constraint but not the integer ones. This relaxation thus allows us to decompose the problem into subprograms each of them consists of a linear program and one-dimensional integer linear problems.

    367-378