We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which a...
详细信息
ISBN:
(纸本)9783540727910
We discuss an open source implementation and preliminary computational testing of three variants of the Balas-Perregaard procedure for generating lift-and-project cuts from the original simplex tableau, two of which are new. Variant 1 is the original procedure of [6] with minor modifications. Variant 2 uses a new procedure for choosing the pivot element: After identifying the set of row candidates for an improving pivot, the pivot element (and column) is chosen by optimizing over the entries of all candidate rows. Finally, Variant 3 replaces the source row with its disjunctive modularization, and after each pivot it again modularizes the resulting source row. We report on computational results withthe above three variants and their combinations on 65 MIPLIB.3 instances.
We consider the class of packing integer programs (PIPs) that are column sparse, where there is a specified upper bound k on the number of constraints that each variable appears in. We give an Unproved (ek+o(k))-appro...
详细信息
ISBN:
(纸本)9783642130359
We consider the class of packing integer programs (PIPs) that are column sparse, where there is a specified upper bound k on the number of constraints that each variable appears in. We give an Unproved (ek+o(k))-approximation algorithm for k-column sparse PIPs. Our algorithm is based on a linear programming relaxation, and involves randomized rounding combined with alteration. We also show that the integrality gap of our LP relaxation is at least 2k-1;it is known that even special cases of k-column sparse PIPs are Omega(k/log k)-hard to approximate. We generalize our result to the case of maximizing monotone submodular functions over k-column sparse packing constraints, and obtain an (e(2)k/e-1 + o(k))-approximation algorithm. In obtaining this result,. we prove a new property of submodular functions that generalizes the fractionally subadditive property, which might be of independent interest.
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increa...
详细信息
ISBN:
(纸本)9783319339542;9783319339535
Nursing workload in hospitals has an impact on the quality of care and on job satisfaction. Understandably there has been much recent research on improving the staffing and nurse-patient assignment decisions in increasingly realistic settings. On a version of the nurse-patient assignment problem given a fixed staffing of neonatal intensive care units, constraint programming (CP) was shown to perform better than competing optimization methods. In this paper we take advantage of recent improvements to the CP approach to solve the integrated problem of staffing and nurse-patient assignment. We then consider a more difficult but also more realistic version of the problem in which patients are categorized into a small number of types and the workload associated with each type is nurse-dependent.
this book constitutes the refereed proceedings of the 19thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2017, held in Waterloo, IN, Canada, in June 2017.
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592497
this book constitutes the refereed proceedings of the 19thinternationalconference on integerprogramming and combinatorialoptimization, IPCO 2017, held in Waterloo, IN, Canada, in June 2017.
In this paper, we study the problem of determining the optimal association in multi-cell WLANs in the presence of hidden terminals and inter-AP collisions. Unlike most work in this area which deal with networks withou...
详细信息
ISBN:
(纸本)9781450302746
In this paper, we study the problem of determining the optimal association in multi-cell WLANs in the presence of hidden terminals and inter-AP collisions. Unlike most work in this area which deal with networks without inter-AP interference, we reveal that association control alone is not sufficient to achieve fair throughput allocation and load balancing across APs. Instead, we advocate the joint association control, rate control and contention control to improve network performance. Based on this, we formulate a cross-layer optimization problem whose objective is to allocate downlink throughput according to the proportional fairness principle. As the problem turns out to be a non-convex mixed integerprogramming problem, which is known to be NP-hard, we relax it into a continuous convex problem and propose a distributed algorithm to solve it. We then design a simple yet effective distributed approximation algorithm to construct an solution that fulfills the discrete integral association constraint. the output of the algorithm provides the optimal association, the maximum achievable rate for each downlink flow and each AP's optimal average backoff time. Numerical experiments and simulation results show that our algorithm converges rapidly and works effectively.
Mixed-integer Programs (MIP's) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally an automatic prob...
详细信息
ISBN:
(纸本)3540221131
Mixed-integer Programs (MIP's) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally an automatic problem reformulation of quite general applicability, aimed at removing the model dependency on the big-M coefficients. Our solution scheme defines a master integer Linear Problem (ILP) with no continuous variables, which contains combinatorial information on the integer-variable feasible combinations that can be "distilled" from the original MIP model. the master solutions are sent to a slave Linear Program (LP), which validates them and possibly returns combinatorial inequalities to be added to the current master ILP. the inequalities are associated to minimal (or irreducible) infeasible subsystems of a certain linear system, and can be separated efficiently in case the master solution is integer. this produces an LP relaxation of the master problem which can be considerably tighter than the one associated with original MIP formulation. Computational results on two specific classes of hard-to-solve MIP's indicate the new method produces a reformulation which can be solved some orders of magnitude faster than the original MIP model.
We present a class of problems that arise in the design of the Next Generation Access Networks. the main features of these networks are: to be based on fiber links of relatively long length with respect to traditional...
详细信息
ISBN:
(纸本)9783642135194
We present a class of problems that arise in the design of the Next Generation Access Networks. the main features of these networks are: to be based on fiber links of relatively long length with respect to traditional copper based networks, users may be reached directly by fibers, and the presence of few central offices managing a large number of users. We present an integerprogramming model that captures the technological constraints and the deployment costs. the model serves as a basis for a decision support tool in the design of the Next Generation Access Networks. Pure integerprogramming cannot handle real-life problem instances, giving rise to new challenges and opportunities for hybrid Constraint programming-Mathematical programming methods. In this paper, we compare a LP-based randomized rounding algorithm with a Constraint-based Local Search formulation. the use of an LP relaxation is twofold: it gives lower bounds to the optimal solution, and it is easily embedded into a randomized rounding algorithm. the Constraint-based Local Search algorithm is then exploited to explore the set of feasible solutions. Withthese algorithms we are able to solve real-life instances for one of the problems presented in this paper.
Cutting plane methods are widely used for solving convex optimization problems and are of fundamental importance, e.g., to provide tight bounds for Mixed-integer Programs (MIPs). this is obtained by embedding a cut-se...
详细信息
ISBN:
(纸本)9783642135194
Cutting plane methods are widely used for solving convex optimization problems and are of fundamental importance, e.g., to provide tight bounds for Mixed-integer Programs (MIPs). this is obtained by embedding a cut-separation module within a search scheme. the importance of a sound search scheme is well known in the Constraint programming (CP) community. Unfortunately, the "standard" search scheme typically used for MIP problems, known as the Kelley method, is often quite unsatisfactory because of saturation issues. In this paper we address the so-called Lift-and-Project closure for 0-1 MIPs associated with all disjunctive cuts generated from a given set of elementary disjunction. We focus on the search scheme embedding the generated cuts. In particular, we analyze a general meta-scheme for cutting plane algorithms, called in-out search, that was recently proposed by Ben-Ameur and Neto [1]. Computational results on test instances from the literature are presented, showing that using a more clever meta-scheme on top of a black-box cut generator may lead to a significant improvement.
For a given set X ⊆ Z d of integer points, we investigate the smallest number of facets of any polyhedron whose set of integer points is conv(X) ∩ Z d . this quantity, which we call the relaxation complexity of X, co...
详细信息
this paper presents a mixed-integeroptimization approach to the yearly hydrothermal scheduling problem. the proposed method is applied to a hydrothermal system comprising 29 thermal units and 13 hydroplants, includin...
详细信息
ISBN:
(纸本)9781424417438
this paper presents a mixed-integeroptimization approach to the yearly hydrothermal scheduling problem. the proposed method is applied to a hydrothermal system comprising 29 thermal units and 13 hydroplants, including 2 pumped storage plants, similar to the Greek Power System. the generation scheduling model is based on an hourly load curve. Perfect competition assumption is adopted and an thermal generators are assumed to bid their marginal cost. A large mixed-integerprogramming problem is formulated and implemented in GAMS. Binary variables represent thermal unit hourly commitment status. Results on an hourly basis, including thermal unit commitment and dispatch, hydroplant generation and pumping and system marginal price are presented.
暂无评论