检索结果-内蒙古大学图书馆

A new reformulation-linearization technique for bilinear programming problems

Journal of Global Optimization 1992年第4期2卷 379-410页

作者： Sherali, Hanif D. Alameddine, Amine Department of Industrial and Systems Engineering Virginia Polytechnic Institute and State University Blacksburg 24061-0118 VA United States

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. © 1992 Kluwer Academic Publishers.

关键词： bilinear programming branch-and-bound global optimization nonconvex programming reformulation-linearization technique

来源：评论

学校读者我要写书评

暂无评论

PI-controller design for constrained linear systems using positive invariance and bilinear programming

PI-controller design for constrained linear systems using po...

引用

IEEE IFAC International Conference on Automation (ICA) / 24th Congress of the Chilean-Association-of-Automatic-Control (ACCA)

作者： Franca dos Santos, Geovana A. Castelan, Eugenio B. Ernesto, Jackson G. DAS PPGEAS UFSC Dept Automat & Syst Engn BR-88040900 Florianopolis SC Brazil

ISBN: (纸本)9781665401272

We address the step reference tracking for monovariable systems subject to state and control constraints via PI-control law with a feedforward term. We determine amplitude limits for the step reference that guarantees the regional closed-loop stability and constraints fulfillment, using invariance and contractivity properties of polyhedral sets, such that the Internal Model Principle remains valid in the polyhedral region. The first main result is based on the positive-invariance property applied to an extended state-space representation that takes the reference model into account, leading to more complex conditions than the ones based on the Delta-invariance property. Based on these two complementary results, a set of bilinear programming problems is proposed to find solutions for the associated constrained tracking problem. A numerical example illustrates the proposal.

关键词： bilinear programming constrained reference tracking PI-Control Polyhedral sets Positive and Delta-invariance

来源：评论

学校读者我要写书评

暂无评论

Non-Convex Optimization and Applications to bilinear programming and Super-Resolution Imaging

Non-Convex Optimization and Applications to Bilinear Program...

引用

作者： Gronski, Jessica University of Colorado Boulder

学位级别：博士

bilinear programs and Phase Retrieval are two instances of nonconvex problems that arise in engineering and physical applications, and both occur with their fundamental difficulties. In this thesis, we consider various methods and algorithms for tackling these challenging problems and discuss their effectiveness. bilinear programs (BLPs) are ubiquitous in engineering applications, economics, and operations research, and have a natural encoding to quadratic programs. They appear in the study of Lyapunov functions used to deduce the stability of solutions to differential equations describing dynamical systems. For multivariate dynamical systems, the problem formulation for computing an appropriate Lyapunov function is a BLP. In electric power systems engineering, one of the most practically important and well-researched subfields of constrained nonlinear optimization is Optimal Power Flow wherein one attempts to optimize an electric power system subject to physical constraints imposed by electrical laws and engineering limits, which can be naturally formulated as a quadratic program. In a recent publication, we studied the relationship between data flow constraints for numerical domains such as polyhedra and bilinear constraints. The problem of recovering an image from its Fourier modulus, or intensity, measurements emerges in many physical and engineering applications. The problem is known as Fourier phase retrieval wherein one attempts to recover the phase information of a signal in order to accurately reconstruct it from estimated intensity measurements by applying the inverse Fourier transform. The problem of recovering phase information from a set of measurements can be formulated as a quadratic program. This problem is well-studied but still presents many challenges. The resolution of an optical device is defined as the smallest distance between two objects such that the two objects can still be recognized as separate entities. Due to the physics of diffraction

关键词： non-convex optimization super-resolution imaging bilinear programming quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Set-theoretic output feedback control: A bilinear programming approach

引用

AUTOMATICA 2023年第1期153卷

作者： Lucia, Walter Ernesto, Jackson G. Castelan, Eugenio B. Concordia Univ Concordia Inst Informat Syst Engn CIISE Montreal PQ H3G 1M8 Canada Univ Fed Santa Catarina Grad Program Automat & Syst Engn PPGEAS BR-88040900 Florianopolis SC Brazil Univ Fed Santa Catarina Dept Automat & Syst DAS CTC BR-88040900 Florianopolis SC Brazil

This paper addresses the problem of designing output feedback controllers for constrained linear systems subject to bounded process and measurement disturbances. The proposed solution extends the set-theoretic model predictive control framework to deal with constrained output regulation problems. In particular, this is here achieved by adequately exploiting the extended Farka's lemma to offline compute through bilinear optimization problems, a family of robust one-step controllable sets, and associated output feedback control gains. It is then formally proved that such computations can be online leveraged to design a simple switching controller capable of ensuring, by construction, that the state-trajectory of the system is always uniformly ultimately bounded, in a finite number of steps, into a small robust control invariant region. Finally, the effectiveness and benefits of the proposed solution are verified through a numerical example and compared with three alternative schemes.(c) 2023 Elsevier Ltd. All rights reserved.

关键词： Output feedback control Constrained control Set-theoretic MPC Extended Farkas?s lemma bilinear programming

来源：评论

学校读者我要写书评

暂无评论

An integer linear programming approach for bilinear integer programming

引用

OPERATIONS RESEARCH LETTERS 2012年第2期40卷 74-77页

作者： Freire, Alexandre S. Moreno, Eduardo Vielma, Juan Pablo Univ Adolfo Ibanez Fac Sci & Engn Santiago Chile Univ Sao Paulo IME Sao Paulo Brazil Univ Pittsburgh Dept Ind Engn Pittsburgh PA 15261 USA

We introduce a new Integer Linear programming (ILP) approach for solving Integer programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear P. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. (C) 2011 Elsevier B.V. All rights reserved.

关键词： bilinear programming Integer linear programming Product bundling

来源：评论

学校读者我要写书评

暂无评论

On piecewise linear approximations of bilinear terms: structural comparison of univariate and bivariate mixed-integer programming formulations

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第4期85卷 789-819页

作者： Baermann, Andreas Burlacu, Robert Hager, Lukas Kleinert, Thomas Friedrich Alexander Univ Erlangen Nurnberg Chair Analyt & Mixed Integer Optimizat Cauerstr 11 D-91058 Erlangen Germany Fraunhofer Inst Integrated Circuits IIS Nordostpk 93 D-90411 Nurnberg Germany Energie Campus Nurnberg Further Str 250 D-90429 Nurnberg Germany

bilinear terms naturally appear in many optimization problems. Their inherent non-convexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of univariate functions. Each univariate function can again be approximated by a piecewise linear function and modelled via an MIP formulation. In the literature, heterogeneous results are reported concerning which approach works better in practice, but little theoretical analysis is provided. We fill this gap by structurally comparing bivariate and univariate approximations with respect to two criteria. First, we compare the number of simplices sufficient for an s-approximation. We derive upper bounds for univariate approximations and compare them to a lower bound for bivariate approximations. We prove that for a small prescribed approximation error s, univariate s-approximations require fewer simplices than bivariate s-approximations. The second criterion is the tightness of the continuous relaxations (CR) of corresponding sharp MIP formulations. Here, we prove that the CR of a bivariate MIP formulation describes the convex hull of a variable product, the so-called McCormick relaxation. In contrast, we show by a volume argument that the CRs corresponding to univariate approximations are strictly looser. This allows us to explain many of the computational effects observed in the literature and to give theoretical evidence on when to use which kind of approximation.

关键词： bilinear programming Piecewise linear approximations MIP formulations Univariate reformulations Convex relaxations

来源：评论

学校读者我要写书评

暂无评论

A bilinear algorithm for optimizing a linear function over the efficient set of a multiple objective linear programming problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2005年第1期31卷 1-16页

作者： Jorge, JM Univ La Laguna Dept Estadist Invest Operat & Computac Tenerife 38271 Spain

The problem Q of optimizing a linear function over the efficient set of a multiple objective linear program serves several useful purposes in multiple criteria decision making. However, Q is in itself a difficult global optimization problem, whose local optima, frequently large in number, need not be globally optimal. Indeed, this is due to the fact that the feasible region of Q is, in general, a nonconvex set. In this paper we present a monotonically increasing algorithm that finds an exact, globally-optimal solution for Q. Our approach does not require any hypothesis on the boundedness of neither the efficient set E-P nor the optimal objective value. The proposed algorithm relies on a simplified disjoint bilinear program that can be solved through the use of well-known specifically designed methods within nonconvex optimization. The algorithm has been implemented in C and preliminary numerical results are reported.

关键词： bilinear programming global optimization multiple objective linear programming optimization over efficient sets

来源：评论

学校读者我要写书评

暂无评论

Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions

引用

Computational Optimization and Applications 1995年第3期4卷 203-203页

作者： Muu, Le Dung Phong, Thai Quynh Tao, Pham Dinh Institute of Mathematics Hanoi Vienam LMI-INSA Rouen Mont Saint Aignan France

We develop convergent decomposition branch and bound algorithms for solving a class of bilinear programming problems. As an application of the proposed method, we apply it to quadratic programs with a few negative eig... 详细信息

关键词： adaptive bisection bilinear programming decomposition method quadratic minimization quadratic mixed integer

来源：评论

学校读者我要写书评

暂无评论

A Mixed-Integer Linear programming Reduction of Disjoint bilinear Programs via Symbolic Variable Elimination 1

引用

20th International Conference on the Integration of Constraint programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Jeong, Jihwan Sanner, Scott Kumar, Akshat Univ Toronto Toronto ON Canada Singapore Management Univ Singapore Singapore Vector Inst Toronto ON Canada

ISBN: (数字)9783031332715

ISBN: (纸本)9783031332708;9783031332715

Adisjointly constrained bilinear program (DBLP) has various practical and industrial applications, e.g., in game theory, facility location, supply chain management, and multi-agent planning problems. Although earlier work has noted the equivalence of DBLP and mixed-integer linear programming (MILP) from an abstract theoretical perspective, a practical and exact closed-form reduction of a DBLP to a MILP has remained elusive. Such explicit reduction would allow us to leverage modern MILP solvers and techniques along with their solution optimality and anytime approximation guarantees. To this end, we provide the first constructive closed-form MILP reduction of a DBLP by extending the technique of symbolic variable elimination (SVE) to constrained optimization problems with bilinear forms. We apply our MILP reduction method to difficult DBLPs including XORs of linear constraints and show that we significantly outperform Gurobi. We also evaluate our method on a variety of synthetic instances to analyze the effects of DBLP problem size and sparsity w.r.t. MILP compilation size and solution efficiency.

关键词： bilinear programming Symbolic variable elimination

来源：评论

学校读者我要写书评

暂无评论

Pooling problem: Alternate formulations and solution methods

引用

MANAGEMENT SCIENCE 2004年第6期50卷 761-776页

作者： Audet, C Brimberg, J Hansen, P Le Digabel, S Mladenovic, N Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Succursalle Ctr Ville Montreal PQ H3C 3A7 Canada Univ Prince Edward Isl Sch Business Adm Charlottetown PE C1A 4P3 Canada Ecole Hautes Etud Commerciales Montreal PQ H3T 2A7 Canada

The pooling problem, which is fundamental to the petroleum industry, describes a situation in which products possessing different attribute qualities are mixed in a series of pools in such a way that the attribute qualities of the blended products of the end pools must satisfy given requirements. It is well known that the pooling problem can be modeled through bilinear and nonconvex quadratic programming. In this paper, we investigate how best to apply a new branch-and-cut quadratic programming algorithm to solve the pooling problem. To this effect, we consider two standard models: One is based primarily on flow variables, and the other relies on the proportion. of flows entering pools. A hybrid of these two models is proposed for general pooling problems. Comparison of the computational properties of flow and proportion models is made on several problem instances taken from the literature. Moreover, a simple alternating procedure and a variable neighborhood search heuristic are developed to solve large instances and compared with the well-known method of successive linear programming. Solution of difficult test problems from the literature is substantially accelerated, and larger ones are solved exactly or approximately.

关键词： pooling problem bilinear programming branch-and-cut heuristics variable neighborhood search

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：