共查询到18条相似文献,搜索用时 312 毫秒
1.
求解中大规模复杂凸二次整数规划问题的新型分枝定界算法 总被引:1,自引:0,他引:1
针对现有分枝定界算法在求解高维复杂二次整数规划问题时所存在的诸多不足,本文通过充分挖掘二次整数规划问题的结构特性来设计选择分枝变量与分枝方向的新方法,并将HNF算法与原问题松弛问题的求解相结合来寻求较好的初始整数可行解,由此导出可用于有效求解中大规模复杂二次整数规划问题的改进型分枝定界算法.数值试验结果表明所给算法大大改进了已有相关的分枝定界算法,并具有较好的稳定性与广泛的适用性. 相似文献
2.
3.
4.
5.
研究带有凹的交易费函数的离散多因素投资组合模型.与传统的投资组合模型不同的是,该模型中投资组合的决策变量是交易手数(整数),其最优化模型是一个非线性整数规划问题.为此本文提出了一个基于拉格朗日松弛和连续松弛的混合分枝定界算法,为测试算法的有效性,我们分别采用美国股票市场真实数据和随机产生的数据,数值结果表明该算法是有效的. 相似文献
6.
金照林 《数学的实践与认识》2023,(4):43-51
提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解. 相似文献
7.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
8.
研究带有凹的交易费函数的离散多因素投资组合模型.与传统的投资组合模型不同的是,该模型中投资组合的决策变量是交易手数(整数),其最优化模型是一个非线性整数规划问题.为此本文提出了一个基于拉格朗日松弛和连续松弛的混合分枝定界算法,为测试算法的有效性,我们分别采用美国股票市场真实数据和随机产生的数据,数值结果表明该算法是有效的. 相似文献
9.
非负约束条件下组合证券投资决策的分枝定界法 总被引:3,自引:0,他引:3
张京 《数学的实践与认识》2004,34(5):18-23
研究非负约束条件下 ,实现预期收益率的组合证券投资决策问题 ,将整数线性规划的分枝定界法用于该问题的求解 ,并应用于一个四元证券投资决策问题 相似文献
10.
本文用混合整数目标规划建立了工厂(企业)的生产(经营)计划模型,并将目标单纯形法和分枝定界法相结合给出了一个算法。文中所研制的双混合整数目标规划模型和求解这一模型的计算机软件系统已用于制订某工厂年度和季度生产经营计划。得到的方案为该厂的生产和经营管理提供了科学依据,显著地提高了工厂的经济效益。 相似文献
11.
A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical
learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by
second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral
conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that
solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the
branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order
conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are
nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear
cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming.
We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance
capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that
conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer
programs and, hence, improving their solvability.
This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation. 相似文献
12.
Pierre Bonami Lorenz T. Biegler Andrew R. Conn Grard Cornujols Ignacio E. Grossmann Carl D. Laird Jon Lee Andrea Lodi Franois Margot Nicolas Sawaya Andreas Wchter 《Discrete Optimization》2008,5(2):186-204
This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch-and-bound and polyhedral outer approximation are the two extreme cases, are proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported. Both the library of mixed integer nonlinear problems that exhibit convex continuous relaxations, on which the experiments are carried out, and a version of the software used are publicly available. 相似文献
13.
A branch-and-bound algorithm to solve 0–1 parametric mixed integer linear programming problems has been developed. The present algorithm is an extension of the branch-and-bound algorithm for parametric analysis on pure integer programming. The characteristic of the present method is that optimal solutions for all values of the parameter can be obtained. 相似文献
14.
H. P. Benson 《Journal of Optimization Theory and Applications》2007,135(1):1-17
This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem,
the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the
algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients.
Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used
to good advantage as a starting solution to the next problem. 相似文献
15.
Pamela H. Vance 《Computational Optimization and Applications》1998,9(3):211-228
We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented. 相似文献
16.
Global optimization of mixed-integer nonlinear programs: A theoretical and computational study 总被引:1,自引:0,他引:1
This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.The research was supported in part by ExxonMobil Upstream Research Company, National Science Foundation awards DMII 95-02722, BES 98-73586, ECS 00-98770, and CTS 01-24751, and the Computational Science and Engineering Program of the University of Illinois. 相似文献
17.
This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer
constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and
discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without
duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual
solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is
equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique.
Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm
is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite
programming method is revealed. 相似文献
18.
Behdin Vahedi-Nouri Parviz Fattahi Mohammad Rohaninejad Reza Tavakkoli-Moghaddam 《Applied Mathematical Modelling》2013
This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed. 相似文献