Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    An elementary survey of general duality theory in mathematical programming (1981)
    Springer
    Mathematical programming 21 (1981), S. 241-261 
    Details
    ISSN: 1436-4646
    Keywords: Dual problem ; Duality Theory ; Optimality Conditions ; Price Functions ; Nonlinear Programming ; Integer Programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We survey some recent developments in duality theory with the idea of explaining and unifying certain basic duality results in both nonlinear and integer programming. The idea of replacing dual variables (prices) by price functions, suggested by Everett and developed by Gould, is coupled with an appropriate dual problem with the consequence that many of the results resemble those used in linear programming. The dual problem adopted has a (traditional) economic interpretation and dual feasibility then provides a simple alternative to concepts such as conjugate functions or subdifferentials used in the study of optimality. In addition we attempt to make precise the relationship between primal, dual and saddlepoint results in both the traditional Lagrangean and the more general duality theories and to see the implications of passing from prices to price functions. Finally, and perhaps surprisingly, it appears that all the standard algorithms terminate by constructing primal and dual feasible solutions of equal value, i.e., by satisfying generalised optimality conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584248
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Generalized dynamic programming methods in integer programming (1973)
    Springer
    Mathematical programming 4 (1973), S. 222-232 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01584662
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Faces for a linear inequality in 0–1 variables (1975)
    Springer
    Mathematical programming 8 (1975), S. 165-178 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a linear inequality in 0–1 variables we attempt to obtain the faces of the integer hull of 0–1 feasible solutions. For the given inequality we specify how faces of a variety of lower-dimensional inequalities can be raised to give full-dimensional faces. In terms of a set, called a “strong cover”, we obtain necessary and sufficient conditions for any inequality with 0–1 coefficients to be a face, and characterize different forms that the integer hull must take. In general the suggested procedures fail to produce the complete integer hull. Special subclasses of inequalities for which all faces can be generated are demonstrated. These include the “matroidal” and “graphic” inequalities, where a count on the number of such inequalities is obtained, and inequalities where all faces can be derived from lower dimensional faces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580441
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Integer programming duality: Price functions and sensitivity analysis (1981)
    Springer
    Mathematical programming 20 (1981), S. 173-195 
    Details
    ISSN: 1436-4646
    Keywords: Integer Programming ; Duality ; Sensitivity Analysis ; Valid Inequalities ; Branch and Bound Methods ; Group Problems ; Lagrangean Relaxation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently a duality theory for integer programming has been developed. Here we examine some of the economic implications of this theory, in particular the necessity of using price functions in place of prices, and the possibility of carrying out sensitivity analysis of optimal solutions. In addition we consider the form of price functions that are generated by known algorithms for integer programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589344
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Optimizing constrained subtrees of trees (1995)
    Springer
    Mathematical programming 71 (1995), S. 113-126 
    Details
    ISSN: 1436-4646
    Keywords: Polyhedral combinatorics ; Packing subtrees ; Knapsacks with precedence ; Column generation ; Dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a treeG = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the “rooted subtree problem”, is to find a maximum weight subtree, with a specified root, from a given set of subtrees. The second problem, called “the subtree packing problem”, is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root. We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by “pasting together” the convex hulls of the rooted subtree problems. We examine in detail the case where the set of feasible subtrees rooted at nodei consists of all subtrees with at mostk nodes. For this case we derive valid inequalities, and specify the convex hull whenk ⩽ 4.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585993
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    bc–opt: a branch-and-cut code for mixed integer programs (1999)
    Springer
    Mathematical programming 86 (1999), S. 335-353 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A branch-and-cut mixed integer programming system, called bc–opt, is described, incorporating most of the valid inequalities that have been used or suggested for such systems, namely lifted 0-1 knapsack inequalities, 0-1 gub knapsack and integer knapsack inequalities, flowcover and continuous knapsack inequalities, path inequalities for fixed charge network flow structure and Gomory mixed integer cuts. The principal development is a set of interface routines allowing these cut routines to generate cuts for new subsets or aggregations of constraints. The system is built using the XPRESS Optimisation Subroutine Library (XOSL) which includes a cut manager that handles the tree and cut management, so that the user only essentially needs to develop the cut separation routines. Results for the MIPLIB3.0 library are presented - 37 of the instances are solved very easily, optimal or near optimal solution are produced for 18 other instances, and of the 4 remaining instances, 3 have 0, +1, -1 matrices for which bc–opt contains no special features.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s101070050092
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A time indexed formulation of non-preemptive single machine scheduling problems (1992)
    Springer
    Mathematical programming 54 (1992), S. 353-367 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to very large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586059
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    Further facet generating procedures for vertex packing polytopes (1976)
    Springer
    Mathematical programming 11 (1976), S. 158-163 
    Details
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580383
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    On the use of penumbras in blocking and antiblocking theory (1982)
    Springer
    Mathematical programming 22 (1982), S. 71-81 
    Details
    ISSN: 1436-4646
    Keywords: Blocking ; Antiblocking ; Polarity ; Penumbra
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract E. Johnson has recently shown that the concept of a penumbra leads to a simple geometric description of the blocker and antiblocker of a given set. Here we develop some basic results on penumbras which permit us to slightly generalize and simplify results on their relationship to blocking and antiblocking theory. In addition, motivated by the obvious symmetry of our results, we examine the effect of reversing the blocking and antiblocking operations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581026
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Lot-size models with backlogging: Strong reformulations and cutting planes (1988)
    Springer
    Mathematical programming 40 (1988), S. 317-335 
    Details
    ISSN: 1436-4646
    Keywords: Lot-sizing models ; backlogging ; cutting planes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We examine mixed integer programming reformulations of the uncapacitated lot-sizing problem with backlogging. First we consider the effect of using a standard reformulation technique for fixed charge network flow problems which involves the introduction of new variables, leading to a known plant location reformulation and a shortest path reformulation. Each of these reformulations is strong in the sense that its linear programming relaxation solves the lot-sizing problem. Secondly we attempt to treat the problem in the space of the original variables. We give an implicit description of the convex hull of solutions, and show how the problem of finding a violated cutting plane can be solved as a linear program. We also describe a family of strong valid inequalities which can be generated rapidly by a heuristic and which have proved effective in a cut generation algorithm. The efficiency of both the shortest path formulation and the cutting plane algorithm have been tested on a series of multi-item capacitated lot-sizing problems with backlogging. Near optimal solutions have been found to problems with 8 periods and up to 100 times.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580738
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...