共查询到20条相似文献,搜索用时 151 毫秒
1.
A polyhedral approach to single-machine scheduling problems 总被引:2,自引:0,他引:2
J.M. van den Akker C.P.M. van Hoesel M.W.P. Savelsbergh 《Mathematical Programming》1999,85(3):541-572
We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete
characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex
hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify
conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex
hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in
the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We
evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job
completion times subject to release dates.
Received March 24, 1994 / Revised version received February 13, 1997
Published online June 28, 1999 相似文献
2.
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative
variables are allowed to be positive. This structure occurs, for example, in areas such as finance, location, and scheduling.
Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that
relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous
variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities
valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities,
we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we
show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial
facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate
the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables
over the traditional MIP approach for this class of problems.
Received: March 13, 2003
Published online: April 10, 2003
Key Words. mixed-integer programming – knapsack problem – cardinality constrained programming – branch-and-cut 相似文献
3.
Andrew J. Miller George L. Nemhauser Martin W.P. Savelsbergh 《Mathematical Programming》2003,94(2-3):375-405
We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This
model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated
production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex
hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce
facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results
for lifting valid inequalities for 0–1 continuous knapsack problems.
Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002
Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network
flow
Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations
of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors.
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America. 相似文献
4.
Yasuki Sekiguchi 《Operations Research Letters》1983,2(5):243-247
A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph. 相似文献
5.
The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of
depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way
that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots.
In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like
a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational
study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted
fans, is tested with success. 相似文献
6.
We consider the problem of a travelling merchant who makes money by buying commodities where they are cheap and selling them
in other places where he can make a profit. The merchant ships commodities of his own choice in a van of fixed capacity. Given
the prices of all the commodities in all of the places, and the cost of driving from one place to another, the problem the
merchant faces each day is to select a subset of the cities that he can visit in a day, and to determine the order in which
the cities are visited, such that the total profit is maximised. We call this problem the Merchant Subtour Problem. The MSP models the pricing problem of a rather complex pickup and delivery problem that was given to us by the Dutch logistics
company Van Gend & Loos.
We show that a special case of the MSP has a totally unimodular constraint matrix. This knowledge enables us to develop a
tabu-search algorithm for finding good feasible solutions to the MSP, and a branch-and-price-and-cut algorithm for solving
the MSP to optimality. The relaxations solved in each node of the branch-and-bound tree are strengthened by lifted knapsack
inequalities, lifted cycle inequalities and mod-k cuts. We present computational results on data sets derived from our main instance of the Van Gend & Loos pickup and delivery
problem.
Received: October 25, 2000 / Accepted: January 23, 2002 Published online: September 27, 2002
RID="★"
ID="★" This research was partially supported by EC – Fifth Framework Programme contract IST-1999-14186 (Project ALCOM-FT:
Algorithms and Complexity – Future Technologies). 相似文献
7.
We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the
first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing
or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number
of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the
total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required
to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by
an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first
case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme.
Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above.
Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002
Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function 相似文献
8.
Laurence A. Wolsey 《Mathematical Programming》2003,97(1-2):423-447
We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for
simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been
made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing
models. We conclude by citing briefly some of the more intriguing new avenues of research.
Received: January 15, 2003 / Accepted: April 10, 2003
Published online: May 28, 2003
Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing
This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian
State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.
Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union. 相似文献
9.
A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail. 相似文献
10.
Eitan Zemel 《Mathematical Programming》1978,15(1):268-277
We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero–one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero–one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality). 相似文献
11.
We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods. 相似文献
12.
《European Journal of Operational Research》1996,94(1):154-166
We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported. 相似文献
13.
A dynamic knapsack set is a natural generalization of the 0-1 knapsack set with a continuous variable studied recently. For
dynamic knapsack sets a large family of facet-defining inequalities, called dynamic knapsack inequalities, are derived by
fixing variables to one and then lifting. Surprisingly such inequalities have the simultaneous lifting property, and for small
instances provide a significant proportion of all the facet-defining inequalities.
We then consider single-item capacitated lot-sizing problems, and propose the joint study of three related sets. The first
models the discrete lot-sizing problem, the second the continuous lot-sizing problem with Wagner-Whitin costs, and the third
the continuous lot-sizing problem with arbitrary costs. The first set that arises is precisely a dynamic knapsack set, the
second an intersection of dynamic knapsack sets, and the unrestricted problem can be viewed as both a relaxation and a restriction
of the second. It follows that the dynamic knapsack inequalities and their generalizations provide strong valid inequalities
for all three sets.
Some limited computation results are reported as an initial test of the effectiveness of these inequalities on capacitated
lot-sizing problems.
Received: March 28, 2001 / Accepted: November 9, 2001 Published online: September 27, 2002
RID="★"
ID="★" Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Present address: Electrabel, Louvain-la-Neuve, B-1348 Belgium.
Key words. knapsack sets – valid inequalities – simultaneous lifting – lot-sizing – Wagner-Whitin costs 相似文献
14.
The stable admissions polytope– the convex hull of the stable assignments of the university admissions problem – is described by a set of linear inequalities.
It depends on a new characterization of stability and arguments that exploit and extend a graphical approach that has been
fruitful in the analysis of the stable marriage problem.
Received: April 10, 1998 / Accepted: June 3, 1999?Published online January 27, 2000 相似文献
15.
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete
graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge
of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper
we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs.
Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality.
We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof
is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities
of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing
inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
相似文献
16.
17.
We introduce a new class of second-order
cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the
performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention
on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds
a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order
cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives.
Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex
hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples
of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than
those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities
that limit sums over disjoint subsets of variables to be at most one.
相似文献
18.
Extended formulations in combinatorial optimization 总被引:1,自引:0,他引:1
Michele Conforti Gérard Cornuéjols Giacomo Zambelli 《4OR: A Quarterly Journal of Operations Research》2010,8(1):1-48
This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”,
we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect
formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem.
Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation
with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various
tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem,
Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming,
and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied.
In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings,
and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’
result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes. 相似文献
19.
We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function
over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions
under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex
extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest
convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving
convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited
by various underestimators of $x/y$ over a rectangle and prove that the extensions theory provides convex relaxations that
are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms.
Received: December 2000 / Accepted: May 2002 Published online: September 5, 2002
RID="*"
ID="*" The research was funded in part by a Computational Science and Engineering Fellowship to M.T., and NSF CAREER award
(DMI 95-02722) and NSF/Lucent Technologies Industrial Ecology Fellowship (NSF award BES 98-73586) to N.V.S.
Key words. convex hulls and envelopes – multilinear functions – disjunctive programming – global optimization 相似文献
20.
A feasible semismooth asymptotically Newton method for mixed complementarity problems 总被引:2,自引:0,他引:2
Semismooth Newton methods constitute a major research area for solving mixed complementarity problems (MCPs). Early research
on semismooth Newton methods is mainly on infeasible methods. However, some MCPs are not well defined outside the feasible
region or the equivalent unconstrained reformulations of other MCPs contain local minimizers outside the feasible region.
As both these problems could make the corresponding infeasible methods fail, more recent attention is on feasible methods.
In this paper we propose a new feasible semismooth method for MCPs, in which the search direction asymptotically converges
to the Newton direction. The new method overcomes the possible non-convergence of the projected semismooth Newton method,
which is widely used in various numerical implementations, by minimizing a one-dimensional quadratic convex problem prior
to doing (curved) line searches.
As with other semismooth Newton methods, the proposed method only solves one linear system of equations at each iteration.
The sparsity of the Jacobian of the reformulated system can be exploited, often reducing the size of the system that must
be solved. The reason for this is that the projection onto the feasible set increases the likelihood of components of iterates
being active. The global and superlinear/quadratic convergence of the proposed method is proved under mild conditions. Numerical
results are reported on all problems from the MCPLIB collection [8].
Received: December 1999 / Accepted: March 2002 Published online: September 5, 2002
RID="★"
ID="★" This work was supported in part by the Australian Research Council.
Key Words. mixed complementarity problems – semismooth equations – projected Newton method – convergence
AMS subject classifications. 90C33, 90C30, 65H10 相似文献