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

Multiprocessor scheduling under precedence constraints: polyhedral results

DISCRETE APPLIED MATHEMATICS 2006年第5期154卷 770-801页

作者： Coll, PE Ribeiro, CC de Souza, CC Univ Buenos Aires Dept Computac RA-1428 Buenos Aires DF Argentina Univ Fed Rio de Janeiro Dept Comp Sci BR-22453900 Rio De Janeiro Brazil Univ Estadual Campinas Inst Comp BR-13084971 Campinas SP Brazil

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are derived. A subset of the inequalities in this formulation has a strong combinatorial structure, which we use to define the polytope of partitions into linear orders. The facial structure of this polytope is investigated and facet defining inequalities are presented which may be helpful to tighten the integer programming formulation of other variants of multiprocessor scheduling problems. Numerical results on real-life problems are presented. (c) 2005 Elsevier B.V. All rights reserved.

关键词： polyhedral combinatorics valid inequalities order polytopes scheduling multiprocessors precedence constraints

来源：评论

学校读者我要写书评

暂无评论

Bend minimization in planar orthogonal drawings using integer programming

引用

SIAM JOURNAL ON OPTIMIZATION 2006年第3期17卷 665-687页

作者： Mutzel, Petra Weiskircher, Rene Univ Dortmund Lehrstuhl Algorithm Engn Expt Algorithmen Fachbereich Informat LS11 D-44227 Dortmund Germany CSIRO Math & Informat Sci Clayton Vic 3169 Australia

We consider the problem of minimizing the number of bends in a planar orthogonal graph drawing. While the problem can be solved via network flow for a given planar embedding of a graph, it is NP-hard if we consider all planar embeddings. Our approach for biconnected graphs combines a new integer linear programming (ILP) formulation for the set of all embeddings of a planar graph with the network flow formulation of the bend minimization problem fixed embeddings. We report on extensive computational experiments with two benchmark sets containing a total of more than 12,000 graphs where we compared the performance of our ILP-based algorithm with a heuristic and a previously published branch & bound algorithm for solving the same problem. Our new algorithm is significantly faster than the previously published approach for the larger graphs of the benchmark graphs derived from industrial applications and almost twice as fast for the benchmark graphs from the artificially generated set of hard instances.

关键词： graph drawing planar drawing orthogonal drawing bend minimization graph theory applications mixed integer programming combinatorial optimization polyhedral combinatorics branch-and-bound branch-and-cut applications of mathematical programming

来源：评论

学校读者我要写书评

暂无评论

The wheels of the OLS polytope: Facets and separation

引用

DISCRETE MATHEMATICS 2008年第16期308卷 3634-3651页

作者： Magos, D. Mourtos, I. Inst Educ Technol Dept Informat Athens 12210 Greece Univ Patras Dept Econ Patras 26500 Greece

Orthogonal Latin squares (OLS) are fundamental combinatorial objects with important theoretical properties and interesting applications. OLS can be represented by integer points satisfying a certain system of equalities. The convex hull of these points is the OLS polytope. This paper adds to the description of the OLS polytope by providing non-trivial facets arising from wheels. Specifically, for each wheel of size five, we identify the variables that can be added to the induced inequality, thus obtaining all distinct families of maximally lifted wheel inequalities. Each of these families induces facets of the OLS polytope which can be efficiently separated in polynomial time. (C) 2007 Elsevier B.V. All rights reserved.

关键词： orthogonal Latin squares polyhedral combinatorics wheel facet

来源：评论

学校读者我要写书评

暂无评论

A branch-and-cut algorithm for scheduling of projects with variable-intensity activities

引用

MATHEMATICAL PROGRAMMING 2005年第3期103卷 515-539页

作者： Kis, T Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary

In this paper we study a resource constrained project scheduling problem in which the resource usage of each activity may vary over time proportionally to its varying intensity. We formalize the problem by means of a mixed integer-linear program, prove that feasible solution existence is NP-complete in the strong sense and propose a branch-and-cut algorithm for finding optimal solutions. To this end, we provide a complete description of the polytope of feasible intensity assignments to two variable-intensity activities connected by a precedence constraint along with a fast separation algorithm. A computational evaluation confirms the effectiveness of our method on various benchmark instances.

关键词： project scheduling network flows polyhedral combinatorics branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

Base polytopes of series-parallel posets: Linear description and optimization

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 159-173页

作者： Schrader, R Schulz, AS Wambach, G Univ Koln Inst Informat D-50931 Cologne Germany Tech Univ Berlin Fachbereich Math D-10623 Berlin Germany

We define the base polytope B(P, g) of partially ordered set P and a supermodular function g on the ideals of P as the convex hull of the incidence vectors of all linear extensions of P. This new class of polytopes contains, among others, the base polytopes of supermodular systems and permutahedra as special cases. After introducing the notion of compatibility for g, we give a complete linear description of B(P, g) for series-parallel posets and compatible functions g. In addition, we describe a greedy-type procedure which exhibits Sidney's job sequencing algorithm to minimize the total weighted completion time as a natural extension of the matroidal greedy algorithm from sets to posets. (C) 1998 The Mathematical Programing Society, Inc. Published by Elsevier Science B.V.

关键词： polyhedral combinatorics series-parallel posets base polytopes supermodular functions greedy algorithm integer programming

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for the identical parallel machine scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2004年第3期152卷 758-769页

作者： Mokotoff, E Univ Alcala de Henares Dept Econ Alcala De Henares 28802 Spain

The NP-hard classical deterministic scheduling problem of minimizing the makespan on identical parallel machines is considered. The polyhedral structure of the problem is analyzed, and strong valid inequalities are identified for fixed values of the makespan. Thus, partial linear descriptions of the associated polytope are obtained and used to build an exact algorithm. Linear programming relaxations are solved iteratively until the integer solution is reached. The algorithm includes a preprocessing phase which reformulates the problem and simplifies it. Different constructive rules have been tried out in the computation of upper bound values and the incidence of this choice is reported. Computational results show that the proposed algorithm yields, in a short computational time, optimal solutions in almost all tested cases. (C) 2002 Elsevier B.V. All rights reserved.

关键词： optimization polyhedral combinatorics scheduling

来源：评论

学校读者我要写书评

暂无评论

On the star forest polytope for trees and cycles

引用

RAIRO-OPERATIONS RESEARCH 2019年第5期53卷 1763-1773页

作者： Aider, Meziane Aoudia, Lamia Baiou, Mourad Mahjoub, A. Ridha Viet Hung Nguyen Univ Sci & Technol Fac Math Algeirs Algeria CNRS LIMOS UMR 6158 Clermont Ferrand France Univ Paris 09 PSL CNRS UMR 7243LAMSADE Pl Marechal Lattre de Tassigny F-75775 Paris France Sorbonne Univ CNRS UMR 7606 LIP6 4 Pl Jussieu Paris France

Let G = (V, E) be an undirected graph where the edges in E have non-negative weights. A star in G is either a single node of G or a subgraph of G where all the edges share one common end-node. A star forest is a collection of vertex-disjoint stars in G. The weight of a star forest is the sum of the weights of its edges. This paper deals with the problem of finding a Maximum Weight Spanning Star Forest (MWSFP) in G. This problem is NP-hard but can be solved in polynomial time when G is a cactus [Nguyen, Discrete Math. Algorithms App.7 (2015) 1550018]. In this paper, we present a polyhedral investigation of the MWSFP. More precisely, we study the facial structure of the star forest polytope, denoted by SFP(G), which is the convex hull of the incidence vectors of the star forests of G. First, we prove several basic properties of SFP(G) and propose an integer programming formulation for MWSFP. Then, we give a class of facet-defining inequalities, called M-tree inequalities, for SFP(G). We show that for the case when G is a tree, the M-tree and the nonnegativity inequalities give a complete characterization of SFP(G). Finally, based on the description of the dominating set polytope on cycles given by Bouchakour et al. [Eur. J. Combin.29 (2008) 652-661], we give a complete linear description of SFP(G) when G is a cycle.

关键词： Combinatorial optimization polyhedral combinatorics star forest facility location dominating set

来源：评论

学校读者我要写书评

暂无评论

On a class of metrics related to graph layout problems

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2010年第11-12期433卷 1760-1777页

作者： Letchford, Adam N. Reinelt, Gerhard Seitz, Hanna Theis, Dirk Oliver Univ Libre Brussels Dept Math Brussels Belgium Univ Heidelberg Inst Comp Sci D-6900 Heidelberg Germany Univ Lancaster Dept Management Sci Lancaster LA1 4YW England

We examine the metrics that arise when a finite set of points is embedded in the real line, in such a way that the distance between each pair of points is at least 1. These metrics are closely related to some other known metrics in the literature, and also to a class of combinatorial optimization problems known as graph layout problems. We prove several results about the structure of these metrics. In particular, it is shown that their convex hull is not closed in general. We then show that certain linear inequalities define facets of the closure of the convex hull. Finally, we characterize the unbounded edges of the convex hull and of its closure. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Metric spaces Graph layout problems Convex analysis polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

AN ANALYSIS OF THE ASYMMETRIC QUADRATIC TRAVELING SALESMAN POLYTOPE

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第1期28卷 240-276页

作者： Fischer, Anja TU Dortmund Fak Math D-44227 Dortmund Germany

The quadratic traveling salesman problem asks for a tour of minimal total costs where the costs are associated with each of two arcs that are traversed in succession. This structure arises, e. g., if the succession of two arcs represents loading processes in transport networks or a switch between different technologies in communication networks. Based on an integer program with quadratic objective function we present a linearized integer programming formulation and study the corresponding polyhedral structure of the asymmetric quadratic traveling salesman problem (AQTSP), where the costs may depend on the direction of traversal. The constructive approach that is used to establish the dimension of the underlying polytope allows us to prove the facetness of several classes of valid inequalities. Some of them are related to the Boolean quadric polytope. Two new classes are developed that exclude conflicting configurations. Among these the first one is separable in polynomial time, and the separation problem for the second class is NP-complete. We present a general strengthening approach that allows us to lift valid inequalities for the asymmetric traveling salesman problem to stronger valid inequalities for AQTSP. Applying this approach to the subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. In general, the strengthening approach is not sufficient to obtain a facet. First computational results are presented to illustrate the importance of the new inequalities, especially for the solution of some real-world instances from biology.

关键词： combinatorial optimization polyhedral combinatorics quadratic 0-1 programming reload cost model

来源：评论

学校读者我要写书评

暂无评论

On a connection between facility location and perfect graphs

引用

OPERATIONS RESEARCH LETTERS 2014年第6-7期42卷 466-472页

作者： Baiou, Mourad Barahona, Francisco CNRS LIMOS Complexe Sci Cezeaux F-63173 Aubiere France IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10589 USA

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on ... 详细信息

关键词： Uncapacitated facility location problem Perfect graphs polyhedral combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：