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.     

On a Finite Branch and Bound Algorithm for the Global Minimization of a Concave Power Law Over a Polytope

In this paper, a finite branch-and-bound algorithm is developed for the minimization of a concave power law over a polytope. Linear terms are also included in the objective function. Using the first order necessary conditions of optimality, the optimization problem is transformed into an equivalent problem consisting of a linear objective function, a set of linear constraints, a set of convex constraints, and a set of bilinear complementary constraints. The transformed problem is then solved using a finite branch-and-bound algorithm that solves two convex problems at each of its nodes. The method is illustrated by means of an example from the literature.     

A note on reduction of quadratic and bilinear programs with equality constraints

Reduction of some classes of global optimization programs to bilinear programs may be done in various ways, and the choice of method clearly influences the ease of solution of the resulting problem. In this note we show how linear equality constraints may be used together with graph theoretic tools to reduce a bilinear program, i.e., eliminate variables from quadratic terms to minimize the number of complicating variables. The method is illustrated on an example. Computer results are reported on known test problems.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Bilinear Control and Application to Flexible a.c. Transmission Systems

The purpose of this paper is an integrated overview of bilinear systems (BLS) research which has evolved over the past few decades, and a new result on control of flexible a.c. transmission systems (FACTS) is presented. BLS may be derived in many cases from principles of physics, chemistry, biology, socioeconomics, and engineering. In other cases, BLS are more accurate approximations to nonlinear systems than are traditional linear systems, as shown for example by the added bilinear terms (in state and control) for the Taylor series.While an appropriately designed linear control system may be optimum relative to some quadratic performance index without added constraints, bilinear or parametric control can be designed to improve more global performance and indeed to increase the region of attainable states. Such controllability and stabilization of BLS and of a series line-capacitor controlled FACTS is presented.     

Optimal control synthesis for the constrained bilinear biquadratic regulator problem

Optimal process control with control constraints is a challenging task related to many real-life problems. In this paper, a single input continuous time constrained linear quadratic regulator problem, is defined and fully solved. The constraints include both bilinear inequality constraints and customary control force bounds. As a first step, the problem is reformulated as an equivalent constrained bilinear biquadratic optimal control problem. Next, Krotov’s method is used to solve it. To this end, a sequence of improving functions suitable to the problem’s new formulation is constructed and the corresponding successive algorithm is derived. The required computational steps are arranged as an algorithm and proof outlines for the convergence and optimality of the solution are given. The efficiency of the suggested method is demonstrated by numerical example.     

指数跟踪问题的广义双线性规划模型

本文对指数跟踪问题建立了一种广义的双线性规划模型,其中考虑了交易费用、持仓限制与重平衡问题.根据该模型的特殊结构,本文给出了近似规划算法,通过逐次逼近的线性规划求解最优指数跟踪问题.     

The linear complementarity problem as a separable bilinear program

The nonmonotone linear complementarity problem (LCP) is formulated as a bilinear program with separable constraints and an objective function that minimizes a natural error residual for the LCP. A linear-programming-based algorithm applied to the bilinear program terminates in a finite number of steps at a solution or stationary point of the problem. The bilinear algorithm solved 80 consecutive cases of the LCP formulation of the knapsack feasibility problem ranging in size between 10 and 3000, with almost constant average number of major iterations equal to four.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9322479 and CDA-9024618.     

Concavity cuts for disjoint bilinear programming

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which make use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint sets and 100 constraints, and dense problems with up to 60 variables again in each sets and 60 constraints are solved in reasonable computing times. Received: October 1999 / Accepted: January 2001?Published online March 22, 2001     

Mixed strategy solutions for quadratic games

Mixed strategy solutions are given for two-person, zero-sum games with payoff functions consisting of quadratic, bilinear, and linear terms, and strategy spaces consisting of closed balls in a Hilbert space. The results are applied to linear-quadratic differential games with no information, and with quadratic integral constraints on the control functions.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

A global supply chain model with transfer pricing and transportation cost allocation

We present a model for the optimization of a global supply that maximizes the after tax profits of a multinational corporation and that includes transfer prices and the allocation of transportation costs as explicit decision variables. The resulting mathematical formulation is a non-convex optimization problem with a linear objective function, a set of linear constraints, and a set of bilinear constraints. We develop a heuristic solution algorithm that applies successive linear programming based on the reformulation and the relaxation of the original problem. Our computational experiments investigate the impact of using different starting points. The algorithm produces feasible solutions with very small gaps between the solutions and their upper bound (UB).     

求线性比式和问题全局解的输出空间分枝定界算法

基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.     

On the SQH Scheme to Solve Nonsmooth PDE Optimal Control Problems

A sequential quadratic Hamiltonian (SQH) scheme for solving different classes of nonsmooth and nonconvex partial differential equation (PDE) optimal control problems is investigated considering seven different benchmark problems with increasing difficulty. These problems include linear and nonlinear PDEs with linear and bilinear control mechanisms, nonconvex, and discontinuous costs of the controls, L¹ tracking terms, and the case of state constraints. The SQH method is based on the characterization of optimality of PDE optimal control problems by the Pontryagin’s maximum principle (PMP). For each problem, a theoretical discussion of the PMP optimality condition is given and results of numerical experiments are presented that demonstrate the large range of applicability of the SQH scheme.     

External Estimates for Reachable Sets of a Control System with Uncertainty and Combined Nonlinearity

The problem of estimating the trajectory tubes of a nonlinear control dynamic system with uncertainty in the initial data is studied. It is assumed that the dynamic system has a special structure in which the nonlinear terms are defined by quadratic forms in the state coordinates and the values of uncertain initial states and admissible controls are subject to ellipsoidal constraints. The matrix of the linear terms in the velocities of the system is not known exactly; it belongs to a given compact set in the corresponding space. Thus, the dynamics of the system is complicated by the presence of bilinear components in the righthand sides of the differential equations of the system. We consider a complicated case and generalize the author’s earlier results. More exactly, we assume the simultaneous presence in the dynamics of the system of bilinear functions and quadratic forms (without the assumption of their positive definiteness) and we also take into account the uncertainty in the initial data and the impact of the control actions, which may also be treated here as undefined additive disturbances. The presence of all these factors greatly complicates the study of the problem and requires an adequate analysis, which constitutes the main purpose of this study. The paper presents algorithms for estimating the reachable sets of a nonlinear control system of this type. The results are illustrated by examples.     

A new Lagrangean approach to the pooling problem

We present a new Lagrangean approach for the pooling problem. The relaxation targets all nonlinear constraints, and results in a Lagrangean subproblem with a nonlinear objective function and linear constraints, that is reformulated as a linear mixed integer program. Besides being used to generate lower bounds, the subproblem solutions are exploited within Lagrangean heuristics to find feasible solutions. Valid cuts, derived from bilinear terms, are added to the subproblem to strengthen the Lagrangean bound and improve the quality of feasible solutions. The procedure is tested on a benchmark set of fifteen problems from the literature. The proposed bounds are found to outperform or equal earlier bounds from the literature on 14 out of 15 tested problems. Similarly, the Lagrangean heuristics outperform the VNS and MALT heuristics on 4 instances. Furthermore, the Lagrangean lower bound is equal to the global optimum for nine problems, and on average is 2.1% from the optimum. The Lagrangean heuristics, on the other hand, find the global solution for ten problems and on average are 0.043% from the optimum.     

Maximization of A convex quadratic function under linear constraints

This paper addresses itself to the maximization of a convex quadratic function subject to linear constraints. We first prove the equivalence of this problem to the associated bilinear program. Next we apply the theory of bilinear programming developed in [9] to compute a local maximum and to generate a cutting plane which eliminates a region containing that local maximum. Then we develop an iterative procedure to improve a given cut by exploiting the symmetric structure of the bilinear program. This procedure either generates a point which is strictly better than the best local maximum found, or generates a cut which is deeper (usually much deeper) than Tui's cut. Finally the results of numerical experiments on small problems are reported.     

Solving a two-dimensional trim-loss problem with MILP

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.     

A new reformulation-linearization technique for bilinear programming problems

This paper is concerned with the development of an algorithm for general bilinear programming problems. Such problems find numerous applications in economics and game theory, location theory, nonlinear multi-commodity network flows, dynamic assignment and production, and various risk management problems. The proposed approach develops a new Reformulation-Linearization Technique (RLT) for this problem, and imbeds it within a provably convergent branch-and-bound algorithm. The method first reformulates the problem by constructing a set of nonnegative variable factors using the problem constraints, and suitably multiplies combinations of these factors with the original problem constraints to generate additional valid nonlinear constraints. The resulting nonlinear program is subsequently linearized by defining a new set of variables, one for each nonlinear term. This RLT process yields a linear programming problem whose optimal value provides a tight lower bound on the optimal value to the bilinear programming problem. Various implementation schemes and constraint generation procedures are investigated for the purpose of further tightening the resulting linearization. The lower bound thus produced theoretically dominates, and practically is far tighter, than that obtained by using convex envelopes over hyper-rectangles. In fact, for some special cases, this process is shown to yield an exact linear programming representation. For the associated branch-and-bound algorithm, various admissible branching schemes are discussed, including one in which branching is performed by partitioning the intervals for only one set of variables x or y, whichever are fewer in number. Computational experience is provided to demonstrate the viability of the algorithm. For a large number of test problems from the literature, the initial bounding linear program itself solves the underlying bilinear programming problem.This paper was presented at the II. IIASA Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

A global optimization algorithm for linear fractional and bilinear programs

In this paper a deterministic method is proposed for the global optimization of mathematical programs that involve the sum of linear fractional and/or bilinear terms. Linear and nonlinear convex estimator functions are developed for the linear fractional and bilinear terms. Conditions under which these functions are nonredundant are established. It is shown that additional estimators can be obtained through projections of the feasible region that can also be incorporated in a convex nonlinear underestimator problem for predicting lower bounds for the global optimum. The proposed algorithm consists of a spatial branch and bound search for which several branching rules are discussed. Illustrative examples and computational results are presented to demonstrate the efficiency of the proposed algorithm.