Optima of dual integer linear programs

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.     

One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming

One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming (LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm obtains solutions of better quality than those obtained by other existing approaches.     

Randomized rounding: A technique for provably good algorithms and algorithmic proofs

We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem instance. This work was supported by Semiconductor Research Corporation grant SRC 82-11-008 and an IBM Doctoral Fellowship.     

A simple constraint qualification in convex programming

We introduce and characterize a class of differentiable convex functions for which the Karush—Kuhn—Tucker condition is necessary for optimality. If some constraints do not belong to this class, then the characterization of optimality generally assumes an asymptotic form.We also show that for the functions that belong to this class in multi-objective optimization, Pareto solutions coincide with strong Pareto solutions,. This extends a result, well known for the linear case.Research partly supported by the National Research Council of Canada.     

Interval methods for verifying structural optimality of circle packing configurations in the unit square

The paper is dealing with the problem of finding the densest packings of equal circles in the unit square. Recently, a global optimization method based exclusively on interval arithmetic calculations has been designed for this problem. With this method it became possible to solve the previously open problems of packing 28, 29, and 30 circles in the numerical sense: tight guaranteed enclosures were given for all the optimal solutions and for the optimum value. The present paper completes the optimality proofs for these cases by determining all the optimal solutions in the geometric sense. Namely, it is proved that the currently best-known packing structures result in optimal packings, and moreover, apart from symmetric configurations and the movement of well-identified free circles, these are the only optimal packings. The required statements are verified with mathematical rigor using interval arithmetic tools.     

Linear bilevel programs with multiple objectives at the upper level

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. Focus of the paper is on general bilevel optimization problems with multiple objectives at the upper level of decision making. When all objective functions are linear and constraints at both levels define polyhedra, it is proved that the set of efficient solutions is non-empty. Taking into account the properties of the feasible region of the bilevel problem, some methods of computing efficient solutions are given based on both weighted sum scalarization and scalarization techniques. All the methods result in solving linear bilevel problems with a single objective function at each level.     

Linear bilevel programming with interval coefficients

In this paper, we address linear bilevel programs when the coefficients of both objective functions are interval numbers. The focus is on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. We prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range.     

A characterization of pseudoinvexity for the efficiency in non-differentiable multiobjective problems. Duality

We prove that in order for the Kuhn-Tucker or Fritz John points to be efficient solutions, it is necessary and sufficient that the non-differentiable multiobjective problem functions belong to new classes of functions that we introduce here: KT-pseudoinvex-II or FJ-pseudoinvex-II, respectively. We illustrate it by examples. These characterizations generalize recent results given for the differentiable case. We study the dual problem and establish weak, strong and converse duality results.     

Scalarization and optimality conditions for vector equilibrium problems

In this paper, we investigated vector equilibrium problems and gave the scalarization results for weakly efficient solutions, Henig efficient solutions, and globally efficient solutions to the vector equilibrium problems without the convexity assumption. Using nonsmooth analysis and the scalarization results, we provided the necessary conditions for weakly efficient solutions, Henig efficient solutions, globally efficient solutions, and superefficient solutions to vector equilibrium problems. By the assumption of convexity, we gave sufficient conditions for those solutions. As applications, we gave the necessary and sufficient conditions for corresponding solutions to vector variational inequalities and vector optimization problems.     

Traveling wave solutions for the mKdV equation and the Gardner equations by new approach of the generalized (G′/G)-expansion method

In this paper, we demonstrate the effectiveness of the new generalized (G′/G)-expansion method by seeking more exact solutions via the mKdV equation and the Gardner equations. The method is direct, concise and simple to implement compared to other existing methods. The traveling wave solutions obtained by this method are expressed in terms of hyperbolic, trigonometric and rational functions. The method shows a wide application for handling nonlinear wave equations. Moreover, the method reduces the large amount of calculations.     

Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

A Linear Bound On The Diameter Of The Transportation Polytope*

We prove that the combinatorial diameter of the skeleton of the polytope of feasible solutions of any m×n transportation problem is at most 8(m+n−2). * Research for this paper was done while the second and third author were visiting the Isaac Newton Institute for Mathematical Sciences, Cambridge, U.K. All authors were supported by the TMR Network DONET of the European Community ERB TMRXCT98-0202. † Research partially funded by the Dutch BSIK/BRICKS project.     

Optimality conditions for various efficient solutions involving coderivatives: From set-valued optimization problems to set-valued equilibrium problems

We present a new approach to the study of a set-valued equilibrium problem (for short, SEP) through the study of a set-valued optimization problem with a geometric constraint (for short, SOP) based on an equivalence between solutions of these problems. As illustrations, we adapt to SEP enhanced notions of relative Pareto efficient solutions introduced in set optimization by Bao and Mordukhovich and derive from known or new optimality conditions for various efficient solutions of SOP similar results for solutions of SEP as well as for solutions of a vector equilibrium problem and a vector variational inequality.We also introduce the concept of quasi weakly efficient solutions for the above problems and divide all efficient solutions under consideration into the Pareto-type group containing Pareto efficient, primary relative efficient, intrinsic relative efficient, quasi relative efficient solutions and the weak Pareto-type group containing quasi weakly efficient, weakly efficient, strongly efficient, positive properly efficient, Henig global properly efficient, Henig properly efficient, super efficient and Benson properly efficient solutions. The necessary conditions for Pareto-type efficient solutions and necessary/sufficient conditions for weak Pareto-type efficient solutions formulated here are expressed in terms of the Ioffe approximate coderivative and normal cone in the Banach space setting and in terms of the Mordukhovich coderivative and normal cone in the Asplund space setting.     

Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben

The paper deals with the reduce of dimension size in the linear mixed integer problem by variables fixing. These criteria are generalizations of the known results for Knapsack-problems. Furthermore strategies of finding feasible solutions are discussed. Numerical tests show the usefulness of these results.     

Convergence behavior of interior-point algorithms

We show that most interior-point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. These algorithms include all path-following algorithms and some potential reduction algorithms. The result also holds for the monotone complementarity problem if a strict complementarity solution exists. In general, the limit point is a solution that maximizes the number of its nonzero components among all solutions.Research supported in part by NSF Grant DDM-8922636, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.     

A hybrid branch-and-bound approach for exact rational mixed-integer programming

We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP  solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the Miplib and Mittelmann libraries and for a new collection of numerically difficult instances.     

Relations between stochastic and parametric programming for decision problems with a random objective function

In this paper we study the relation between the general concept for an optimal solution for stochastic programming problems with a random objective function-the concept of an £-efficient solution-and the associated parametric problem, We show that it is possible under certain assumptions to obtain some or even all £-efficient solutions of the stochastic problem by solving the parametric problem with respect to a certain parameter set.     

Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra

We present a unifying framework to establish a lower bound on the number of semidefinite-programming-based lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by Lovász and Schrijver and have been used usually implicitly in the previous lower-bound analyses. In this paper, we formalize the lift-and-project commutative maps and propose a general framework for lower-bound analysis, in which we can recapture many of the previous lower-bound results on the lift-and-project ranks.     

Optimal allocation of service rates in Jackson network of queues with total finite accommodating space

This paper deals with the solutions of problems of optimal allocation of service rates in Jackson network of queues with total finite accommodating space. The optimal service rates have been found by using geometric programming techniques.Numerical results have also been given in the text.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000