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

parametric integer programming in Fixed Dimension

MATHEMATICS OF OPERATIONS RESEARCH 2008年第4期33卷 839-850页

作者： Eisenbrand, Friedrich Shmonin, Gennady Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland

parametric integer programming deals with a family of integer programs that is defined by the same constraint matrix but where the right-hand sides are points of a given polyhedron. The question is whether all these integer programs are feasible. Kannan showed that this can be checked in polynomial time if the number of variables in the integer programs is fixed and the polyhedron of right-hand sides has fixed affine dimension. In this paper, we extend this result by providing a polynomial algorithm for this problem under the only assumption that the number of variables in the integer programs is fixed. We apply this result to deduce a polynomial algorithm to compute the maximum gap between the optimum values of an integer program in fixed dimension and its linear programming relaxation, as the right-hand side is varying over all vectors for which the integer program is feasible.

关键词： parametric integer programming fixed dimension integer programming gap

来源：评论

学校读者我要写书评

暂无评论

parametric MIXED integer programming - AN APPLICATION TO SOLID-WASTE MANAGEMENT

引用

MANAGEMENT SCIENCE 1982年第11期28卷 1270-1284页

作者： JENKINS, L Royal Military College of Canada Kingston Ontario

A method is developed for carrying out parametric analysis on a mixed integer linear program (MILP) as either objective function coefficients or right-hand-side values of the constraints are varied continuously. The method involves solving MILPs at point values of the parameters of variation and joining the results by LP parametric analysis.

关键词： parametric integer programming facility location solid waste management

来源：评论

学校读者我要写书评

暂无评论

A BRANCH-AND-BOUND ALGORITHM FOR 0-1 parametric MIXED integer programming

引用

OPERATIONS RESEARCH LETTERS 1985年第1期4卷 41-45页

作者： OHTAKE, Y NISHIDA, N SCI UNIV TOKYO DEPT MANAGEMENT SCISHINJUKU KUTOKYO 162JAPAN

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.

关键词： parametric integer programming mixed integer programming branch-and-bound algorithm

来源：评论

学校读者我要写书评

暂无评论

Mixed integer parametric bilevel programming for optimal strategic bidding of energy producers in day-ahead electricity markets with indivisibilities

引用

OPTIMIZATION 2013年第8期62卷 1045-1068页

作者： Kozanidis, George Kostarelou, Eftychia Andrianesis, Panagiotis Liberopoulos, George Univ Thessaly Dept Mech Engn Volos Greece

We address the problem of finding the optimal bidding strategy of an energy producer that participates in a single-period day-ahead electricity market, assuming full knowledge of the market's parameters. The problem is formulated as a mixed integer bilevel optimization model, with the producer maximizing his individual profit, at the upper level, and an independent system operator clearing the market at the minimum total system bid-cost, at the lower level. The model utilizes discrete variables to represent the commitment of the production units, which prohibits the application of typical methodologies for finding its optimal solution, such as the substitution of the lower level problem by its first-order KKT optimality conditions. We develop an exact algorithm for the solution of the problem that utilizes important findings from the theory of parametric integer programming, and we report experimental results demonstrating its efficiency on random problem instances. We conclude with a discussion on several computational issues pertaining to the behaviour of this algorithm, and an outline of how the theory developed in the present work can be modified to fit alternative market designs.

关键词： day-ahead electricity markets optimal strategic bidding energy producers mixed integer bilevel optimization parametric integer programming 90C11 90C26 90C30 90C31

来源：评论

学校读者我要写书评

暂无评论

parametric methods in integer linear programming

引用

Annals of Operations Research 1990年第1期27卷 77-96页

作者： Jenkins, Larry Department of Engineering Management Royal Military College of Canada Kingston K7K 5L0 Ontario Canada

In contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm. The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization. © 1990 J.C. Baltzer A.G. Scientific Publishing Company.

关键词： parametric integer programming

来源：评论

学校读者我要写书评

暂无评论

Continuity and Stability of a Quadratic Mixed-integer Stochastic Program

引用

NUMERICAL FUNCTIONAL ANALYSIS AND OPTIMIZATION 2009年第5-6期30卷 462-477页

作者： Chen, Zhiping Xu, Zongben Xi An Jiao Tong Univ Fac Sci Dept Sci Comp & Appl Software Xian 710049 Shaanxi Peoples R China

For the two-stage quadratic stochastic program where the second-stage problem is a general mixed-integer quadratic program with a random linear term in the objective function and random right-hand sides in constraints, we study continuity properties of the second-stage optimal value as a function of both the first-stage policy and the random parameter vector. We also present sufficient conditions for lower or upper semicontinuity, continuity, and Lipschitz continuity of the second-stage problem's optimal value function and the upper semicontinuity of the optimal solution set mapping with respect to the first-stage variables and/or the random parameter vector. These results then enable us to establish conclusions on the stability of optimal value and optimal solutions when the underlying probability distribution is perturbed with respect to the weak convergence of probability measures.

关键词： Continuity parametric integer programming Quadratic stochastic programs Stability Two-stage Weak convergence

来源：评论

学校读者我要写书评

暂无评论

Continuity and stability of fully random two-stage stochastic programs with mixed-integer recourse

引用

OPTIMIZATION LETTERS 2014年第5期8卷 1647-1662页

作者： Chen, Zhiping Zhang, Feng Xi An Jiao Tong Univ Sch Math & Stat Dept Comp Sci Xian 710049 Shaanxi Peoples R China

In order to derive continuity and stability of two-stage stochastic programs with mixed-integer recourse when all coefficients in the second-stage problem are random, we first investigate the quantitative continuity of the objective function of the corresponding continuous recourse problem with random recourse matrices. Then by extending derived results to the mixed-integer recourse case, the perturbation estimate and the piece-wise lower semi-continuity of the objective function are proved. Under the framework of weak convergence for probability measure, the epi-continuity and joint continuity of the objective function are established. All these results help us to prove a qualitative stability result. The obtained results extend current results to the mixed-integer recourse with random recourse matrices which have finitely many atoms.

关键词： Stochastic programming Mixed-integer programming Continuity Stability parametric integer programming

来源：评论

学校读者我要写书评

暂无评论

A new and faster representation for counting integer points in parametric polyhedra

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2024年 1-51页

作者： Gribanov, Dmitry V. Malyshev, Dmitry S. Pardalos, Panos M. Zolotykh, Nikolai Yu. Moscow Inst Phys & Technol Lab Discrete & Combinatorial Optimizat Inst Lane 9 Moscow 141700 Russia HSE Univ Lab Algorithms & Technol Network Anal 136 Rodionova Ulitsa Nizhnii Novgorod 603093 Russia Univ Florida Dept Ind & Syst Engn 401 Weil Hall 116595 Gainesville FL USA Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

In this paper, we consider the counting function EP(y)=|Py boolean AND Znx|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y) = |{{\,\mathrm{\mathcal {P}}\,}}_{y} \cap {{\,\mathrm{\mathbb {Z}}\,}}<^>{n_x}|$$\end{document} for a parametric polyhedron Py={x is an element of Rnx:Ax <= b+By}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{\mathcal {P}}\,}}_{y} = \{ x \in {{\,\mathrm{\mathbb {R}}\,}}<^>{n_x} :A x \le b + B y\}$$\end{document}, where y is an element of Rny\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y \in {{\,\mathrm{\mathbb {R}}\,}}<^>{n_y}$$\end{document}. We give a new representation of EP(y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\mathrm{{{\,\mathrm{\mathcal {E}}\,}}_{{{\,\mathrm{\mathcal {P}}\,}}}}\,}}(y)$$\end{document}, called a piece-wise step-polynomial with periodic coefficients, which is a generalization of piece-wise step-polynomials and integer/rational Ehrhart's quasi-polynomials. It gives the fastest way to calculate EP(y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{

关键词： integer linear programming parametric integer programming Short rational generating function Bounded sub-determinants Multidimensional knapsack problem Subset-sum problem Counting problem

来源：评论

学校读者我要写书评

暂无评论

SETUP COST STABILITY REGION FOR THE MULTILEVEL DYNAMIC LOT-SIZING PROBLEM

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1995年第1期87卷 132-141页

作者： VOROS, J UNIV PECS FAC BUSINESS & ECONRAKOCZI 80H-7622 PECSHUNGARY

In this paper the multi-level dynamic lot sizing problem is investigated in which setup costs are parameters and the range within which setup costs can vary without changing the optimal solution is determined. The computations are significantly shortened by the fact that the holding cost function is convex in the number of setups. The topic also raises the problem of convexity of a multi-variable integer function and the search for the neighbouring integer points of the minimum.

关键词： LOT SIZING parametric integer programming DYNAMIC programming

来源：评论

学校读者我要写书评

暂无评论

ON STRUCTURE AND STABILITY IN STOCHASTIC PROGRAMS WITH RANDOM TECHNOLOGY MATRIX AND COMPLETE integer RECOURSE

引用

MATHEMATICAL programming 1995年第1期70卷 73-89页

作者： SCHULTZ, R Konrad-Zuse-Zentrum für Informationstechnik Berlin Berlin Germany

For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure. Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.

关键词： STOCHASTIC integer programming parametric integer programming CONTINUITY STABILITY WEAK CONVERGENCE OF PROBABILITY MEASURES

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：