Implied constraints and an alternate unified development of nonlinear programming theory

This paper offers an alternate unified view of nonlinear programming theory from the perspective of implied constraints. Optimality is identically characterized for both constrained and unconstrained problems in terms of implied constraints. It is shown that there is a weaker condition than the Guignard constraint qualification for the existence of finite multipliers in the Karush-Kuhn-Tucker conditions. Surprisingly, this condition does not directly qualify the constraints but instead qualifies the objective in terms of implied constraints. More surprisingly, the existence of the finite multipliers follows directly from this objective qualification — it is not necessary for the point to be a local optimum. Methods for generating implied constraints are used to obtain a more general sufficient condition for local and global optimality. A single unified formulation of duality shows that duality is nothing more than an effort to generate the tightest implied constraint. Duality theorems hold in general for this formulation — convexity is not required — and the existence of the duality gap in prior formulations is easily explained. The algorithmic potential of this approach is highlighted by showing that the Simplex method systematically tries to imply the objective from the constraints of the problem.     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

A penalty method for rank minimization problems in symmetric matrices

The problem of minimizing the rank of a symmetric positive semidefinite matrix subject to constraints can be cast equivalently as a semidefinite program with complementarity constraints (SDCMPCC). The formulation requires two positive semidefinite matrices to be complementary. This is a continuous and nonconvex reformulation of the rank minimization problem. We investigate calmness of locally optimal solutions to the SDCMPCC formulation and hence show that any locally optimal solution is a KKT point. We develop a penalty formulation of the problem. We present calmness results for locally optimal solutions to the penalty formulation. We also develop a proximal alternating linearized minimization (PALM) scheme for the penalty formulation, and investigate the incorporation of a momentum term into the algorithm. Computational results are presented.     

Optimizing glass coating lines: MIP model and valid inequalities

Glass coating is a specific transformation aiming at improving glass performance. The work presented in this paper deals with the determination of the optimal configuration of the production lines used to perform this operation. We propose a first MIP formulation of the problem and then discuss several types of valid inequalities for improving it. The main idea is to exploit explicit or implicit binary exclusion constraints to derive stronger valid inequalities: the maximal clique constraints. Efficient (polynomial time) separation algorithms exploiting special structure of the problem are described, giving rise to a cutting-plane generation procedure for strengthening the initial formulation. The computational study carried out shows that, with the enhanced formulation, good solutions can be obtained within reasonable computation times using currently available integer programming software.     

Quartic Formulation of Standard Quadratic Optimization Problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum-Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. To get rid of the (sign) constraints, we propose a quartic reformulation of StQPs, which is a special case (degree four) of a homogeneous program over the unit sphere. It turns out that while KKT points are not exactly corresponding to each other, there is a one-to-one correspondence between feasible points of the StQP satisfying second-order necessary optimality conditions, to the counterparts in the quartic homogeneous formulation. We supplement this study by showing how exact penalty approaches can be used for finding local solutions satisfying second-order necessary optimality conditions to the quartic problem: we show that the level sets of the penalty function are bounded for a finite value of the penalty parameter which can be fixed in advance, thus establishing exact equivalence of the constrained quartic problem with the unconstrained penalized version.     

A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

Solving Unit Commitment Problem Using Hybrid Particle Swarm Optimization

This paper presents a Hybrid Particle Swarm Optimization (HPSO) to solve the Unit Commitment (UC) problem. Problem formulation of the unit commitment takes into consideration the minimum up and down time constraints, start up cost and spinning reserve, which is defined as the minimization of the total objective function while satisfying all the associated constraints. Problem formulation, representation and the simulation results for a 10 generator-scheduling problem are presented. Results shown are acceptable at this early stage.     

An Augmented Arborescence Formulation for the Two-Level Network Design Problem

In this paper we discuss formulations for the Two Level Network Design (TLND) problem. In particular, we present an arborescence based formulation with extra constraints guaranteeing that the set of primary nodes is spanned by primary edges. This characterization suggests an arborescence based Lagrangian relaxation where the extra constraints are dualized. Although the Linear Programming (LP) value of the new formulation is proved to be theoretically weaker than the LP bound given by the flow based formulation presented by Balakrishnan, Magnanti and Mirchandani, our computational results show that for certain classes of instances the two LP bounds are quite close. Our results also show that the Lagrangian relaxation based method is quite efficient, providing a reasonable alternative to handle the problem.     

The coastal seaspace patrol sector design and allocation problem

In this paper, we model and solve the problem of designing and allocating coastal seaspace sectors for steady-state patrolling operations by the vessels of a maritime protection agency. The problem addressed involves optimizing a multi-criteria objective function that minimizes a weighted combination of proportional measures of the vessels’ distances between home ports and patrol sectors, the sector workload, and the sector span. We initially assure contiguity of each patrol sector in our mixed-integer programming formulation via an exponential number of subtour elimination constraints, and then propose three alternative solution methods, two of which are based on reformulations that suitably replace the original contiguity representation with a polynomial number of constraints, and a third approach that employs an iterative cut generation procedure based on identifying violated subtour elimination constraints. We further enhance these reformulations with symmetry defeating constraints, either in isolation or in combination with a suitable perturbation of the objective function using weighted functions based on such constraints. Computational comparisons are provided for solving the problem using the original formulation versus either of our three alternative solution approaches for a representative instance. Overall, a model formulation based on Steiner tree problem (STP) constructs and enhanced by the reformulation-linearization technique (RLT) yielded the best performance.     

A Representation and Economic Interpretation of a Two-Level Programming Problem

This paper first presents a formulation for a class of hierarchial problems that show a two-stage decision making process; this formulation is termed multilevel programming and could be defined, in general, as a mathematical programming problem (master) containing other multilevel programs in the constraints (subproblems). A two-level problem is analyzed in detail, and we develop a solution procedure that replaces the subproblem by its Kuhn-Tucker conditions and then further transforms it into a mixed integer quadratic programming problem by exploiting the disjunctive nature of the complementary slackness conditions.An example problem is solved and the economic implications of the formulation and its solution are reviewed.     

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

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

An Inverse Reliability-based Approach for Designing under Uncertainty with Application to Robust Piston Design

In this work, we propose an optimization framework for designing under uncertainty that considers both robustness and reliability issues. This approach is generic enough to be applicable to engineering design problems involving nonconvex objective and constraint functions defined in terms of random variables that follow any distribution. The problem formulation employs an Inverse Reliability Strategy that uses percentile performance to address both robustness objectives and reliability constraints. Robustness is achieved through a design objective that evaluates performance variation as a percentile difference between the right and left trails of the specified goals. Reliability requirements are formulated as Inverse Reliability constraints that are based on equivalent percentile performance levels. The general proposed approach first approximates the formulated problem via a Gaussian Kriging model. This is then used to evaluate the percentile performance characteristics of the different measures inherent in the problem formulation for various design variable settings via a Most Probable Point of Inverse Reliability search algorithm. By using these percentile evaluations in concert with the response surface methodology, a polynomial programming approximation is generated. The resulting problem formulation is finally solved to global optimality using the Reformulation–Linearization Technique (RLT) approach. We demonstrate this overall proposed approach by applying it to solve the problem of reducing piston slap, an undesirable engine noise due to the secondary motion of a piston within a cylinder.     

Improving the computational efficiency in a global formulation (GLIDE) for interactive multiobjective optimization

In this paper, we present a new general formulation for multiobjective optimization that can accommodate several interactive methods of different types (regarding various types of preference information required from the decision maker). This formulation provides a comfortable implementation framework for a general interactive system and allows the decision maker to conveniently apply several interactive methods in one solution process. In other words, the decision maker can at each iteration of the solution process choose how to give preference information to direct the interactive solution process, and the formulation enables changing the type of preferences, that is, the method used, whenever desired. The first general formulation, GLIDE, included eight interactive methods utilizing four types of preferences. Here we present an improved version where we pay special attention to the computational efficiency (especially significant for large and complex problems), by eliminating some constraints and parameters of the original formulation. To be more specific, we propose two new formulations, depending on whether the multiobjective optimization problem to be considered is differentiable or not. Some computational tests are reported showing improvements in all cases. The generality of the new improved formulations is supported by the fact that they can accommodate six interactive methods more, that is, a total of fourteen interactive methods, just by adjusting parameter values.     

A polyhedral approach to a production planning problem

Production planning in manufacturing industries is concerned with the determination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints. In general, production planning problems become harder when different types of constraints are present, such as capacity constraints, minimum lot sizes, changeover times, among others. Models incorporating some of these constraints yield, in general, NP-hard problems. We consider a single-machine, multi-item lot-sizing problem, with those difficult characteristics. There is a natural mixed integer programming formulation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is inefficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the set of feasible solutions are derived, and the corresponding separation problems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods. This revised version was published online in June 2006 with corrections to the Cover Date.     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.     

An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms

Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.     

Using a Conic Formulation for Finding Steiner Minimal Trees

We present a new mathematical programming formulation for the Steiner minimal tree problem. We relax the integrality constraints on this formulation and transform the resulting problem (which is convex, but not everywhere differentiable) into a standard convex programming problem in conic form. We consider an efficient computation of an ε-optimal solution for this latter problem using an interior-point algorithm.     

Relaxation Through Homogenization for Optimal Design Problems with Gradient Constraints

The problem of the relaxation of optimal design problems for multiphase composite structures in the presence of constraints on the gradient of the state variable is addressed. A relaxed formulation for the problem is given in the presence of either a finite or infinite number of constraints. The relaxed formulation is used to identify minimizing sequences of configurations of phases.     

A variational inequality approach to constrained control problems for parabolic equations

A distributed optimal control problem for parabolic systems with constraints in state is considered. The problem is transformed to control problem without constraints but for systems governed by parabolic variational inequalities. The new formulation presented enables the efficient use of a standard gradient method for numerically solving the problem in question. Comparison with a standard penalty method as well as numerical examples are given.     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.