New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

Discrete location for bundled demand points

This paper considers a discrete location problem where the demand points are grouped. We propose a formulation, an enforcement for it, and an associated Lagrangian relaxation, and then we build feasible solutions to the problem from the optimal solutions to the relaxed subproblems. Valid inequalities for the formulation are also identified and added to the set of relaxed constraints. This method produces good feasible solutions and enables us to address large instances of the problem. Computational experiments have been performed with benchmark instances from the literature on related problems.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Approximations of Relaxed Optimal Control Problems

In the present paper, we investigate an approximation technique for relaxed optimal control problems. We study control processes governed by ordinary differential equations in the presence of state, target, and integral constraints. A variety of approximation schemes have been recognized as powerful tools for the theoretical studying and practical solving of Infinite-dimensional optimization problems. On the other hand, theoretical approaches to the relaxed optimal control problem with constraints are not sufficiently advanced to yield numerically tractable schemes. The explicit approximation of the compact control set makes it possible to reduce the sophisticated relaxed problem to an auxiliary optimization problem. A given trajectory of the relaxed problem can be approximated by trajectories of the auxiliary problem. An optimal solution of the introduced optimization problem provides a basis for the construction of minimizing sequences for the original optimal control problem. We describe how to carry out the numerical calculations in the context of nonlinear programming and establish the convergence properties of the obtained approximations.The authors thank the referees for helpful comments and suggestions.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Dynamic Programming State-Space Relaxation for Single-Machine Scheduling

The problem of sequencing jobs on a single machine to minimize total cost is considered. Machine capacity constraints require that, at any time, at most one job is processed. Also, no machine idle-time between processing jobs is allowed. In contrast to most research, it is not assumed that the cost is a non-decreasing function of completion time. A dynamic programming formulation of the problem is presented. Since the number of states required by this formulation is prohibitively large, the possibilities for branch and bound algorithms are explored. It is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state-space and performing the recursion on this smaller state-space, thereby giving a lower bound. Techniques for improving this lower bound through the use of penalties and through the use of state-space modifiers are discussed. Computational results are presented for the problem in which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date.     

A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

In this paper, we present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation–Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which in turn is tighter than the formulation based on the exponential number of Dantzig–Fulkerson–Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and we explore several dominance relationships among these. We also extend these formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.     

A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints

In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified easily. This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and Culture of Japan. The authors are grateful to an anonymous referee for critical comments.     

New Relaxation Method for Mathematical Programs with Complementarity Constraints

In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising.     

A branch and bound network approach to the canonical constrained entropy problem

In this paper, we present a branch and bound algorithm for solving the constrained entropy mathematical programming problem. Unlike other methods for solving this problem, our method solves more general problems with inequality constraints. The advantage of the proposed technique is that the relaxed problem solved at each node is a singly constrained network problem. The disadvantage is that the relaxed problem has twice as many variables as the original problem. An application to regional planning is given, and an example problem is solved.     

Shape optimization for Dirichlet problems: Relaxed formulation and optimality conditions

We study an optimal design problem for the domain of an elliptic equation with Dirichlet boundary conditions. We introduce a relaxed formulation of the problem which always admits a solution, and we prove some necessary conditions for optimality both for the relaxed and for the original problem.     

Overall Optimization with Optimal Relaxations of the Constraints

Sometimes one or more constraints seriously affect the optimization of an objective function and therefore some relaxation of the constraints is desired if possible. It is assumed that constraints can be relaxed at the cost of introducing some penalty functions into the objective function. In some cases the optimization of the modified objective function (which includes penalty functions) subject to optimally relaxed constraints is preferred. This note deals with the optimal relaxation of the constraints with regard to the linear programming problem which consequently results in overall optimization.     

The layout problem of two kinds of graph elements with performance constraints and its optimality conditions

This paper presents an optimization model with performance constraints for two kinds of graph elements layout problem. The layout problem is partitioned into finite subproblems by using graph theory and group theory, such that each subproblem overcomes its on-off nature about optimal variable. Furthermore each subproblem is relaxed and the continuity about optimal variable doesn’t change. We construct a min-max problem which is locally equivalent to the relaxed subproblem and develop the first order necessary and sufficient conditions for the relaxed subproblem by virtue of the min-max problem and the theories of convex analysis and nonsmooth optimization. The global optimal solution can be obtained through the first order optimality conditions.     

Minimising total average cycle stock subject to practical constraints

Silver and Moon (J Opl Res Soc 50(8) (1999) 789–796) address the problem of minimising total average cycle stock subject to two practical constraints. They provide a dynamic programming formulation for obtaining an optimal solution and propose a simple and efficient heuristic algorithm. Hsieh (J Opl Res Soc 52(4) (2001) 463–470) proposes a 0–1 linear programming approach to the problem and a simple heuristic based on the relaxed 0–1 programming formulation. We show in this paper that the formulation of Hsieh can be improved for solving very large size instances of this inventory problem. So the mathematical approach is interesting for several reasons: the definition of the model is simple, its implementation is immediate by using a mathematical programming language together with a mixed integer programming software and the performance of the approach is excellent. Computational experiments carried out on the set of realistic examples considered in the above references are reported. We also show that the general framework for modelling given by mixed integer programming allows the initial model to be extended in several interesting directions.     

Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems

We address nonconvex mixed-integer bilinear problems where the main challenge is the computation of a tight upper bound for the objective function to be maximized. This can be obtained by using the recently developed concept of multiparametric disaggregation following the solution of a mixed-integer linear relaxation of the bilinear problem. Besides showing that it can provide tighter bounds than a commercial global optimization solver within a given computational time, we propose to also take advantage of the relaxed formulation for contracting the variables domain and further reduce the optimality gap. Through the solution of a real-life case study from a hydroelectric power system, we show that this can be an efficient approach depending on the problem size. The relaxed formulation from multiparametric formulation is provided for a generic numeric representation system featuring a base between 2 (binary) and 10 (decimal).     

On relaxing the integrality of the allocation variables of the reliability fixed-charge location problem

The aim of the reliability fixed-charge location problem is to find robust solutions to the fixed-charge location problem when some facilities might fail with probability q. In this paper we analyze for which allocation variables in the reliability fixed-charge location problem formulation the integrality constraint can be relaxed so that the optimal value matches the optimal value of the binary problem. We prove that we can relax the integrality of all the allocation variables associated to non-failable facilities or of all the allocation variables associated to failable facilities but not of both simultaneously. We also demonstrate that we can relax the integrality of all the allocation variables whenever a family of valid inequalities is added to the set of constraints or whenever the parameters of the problem satisfy certain conditions. Finally, when solving the instances in a data set we discuss which relaxation or which modification of the problem works better in terms of resolution time and we illustrate that relaxing the integrality of the allocation variables inappropriately can alter the objective value considerably.     

卫星舱三维布局优化模型及判断不干涉性算法

本以人造卫星仪器舱布局问题为背景。建立了在抛物圆柱体空间中带性能约束的长方体群的布局优化模型。分析模型中不干涉性约束的性质，利用凸集分离定理给出了等价的显式表达式，并构造了判断不干涉性的算法。     

Mixed Frank–Wolfe Penalty Method with Applications to Nonconvex Optimal Control Problems

We consider a general optimization problem which is an abstract formulation of a broad class of state-constrained optimal control problems in relaxed form. We describe a generalized mixed Frank–Wolfe penalty method for solving the problem and prove that, under appropriate assumptions, accumulation points of sequences constructed by this method satisfy the necessary conditions for optimality. The method is then applied to relaxed optimal control problems involving lumped as well as distributed parameter systems. Numerical examples are given.     

Discrete approximation of relaxed optimal control problems

We consider a general nonlinear optimal control problem for systems governed by ordinary differential equations with terminal state constraints. No convexity assumptions are made. The problem, in its so-called relaxed form, is discretized and necessary conditions for discrete relaxed optimality are derived. We then prove that discrete optimality [resp., extremality] in the limit carries over to continuous optimality [resp., extremality]. Finally, we prove that limits of sequences of Gamkrelidze discrete relaxed controls can be approximated by classical controls.     

An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices

The multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route lies within a given distance of a route. This paper tackles a particular case of m-CTP where only the restriction on the number of vertices is considered, i.e., the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a metaheuristic. To develop the branch-and-cut algorithm, we use a new integer programming formulation based on a two-commodity flow model. The metaheuristic is based on the evolutionary local search (ELS) method proposed in [23]. Computational results are reported for a set of test problems derived from the TSPLIB.