We develop integerprogramming (IP) solutions for some special college admission problems arising from the Hungarian higher education admission scheme. We focus on four special features, namely the solution concept of...
详细信息
We develop integerprogramming (IP) solutions for some special college admission problems arising from the Hungarian higher education admission scheme. We focus on four special features, namely the solution concept of stable score-limits, the presence of lower and common quotas, and paired applications. We note that each of the latter three special feature makes the college admissions problem NP-hard to solve. Currently, a heuristic based on the Gale-Shapley algorithm is being used in the Hungarian application. the IP methods that we propose are not only interesting theoretically, but may also serve as an alternative solution concept for this practical application, and other similar applications. We finish the paper by presenting a simulation using the 2008 data of the Hungarian higher education admission scheme.
A class of critical node detection problems based upon the metric of communication efficiency is considered. While both exact integerprogramming and heuristic centrality-based methods exist for the solution of these ...
详细信息
A class of critical node detection problems based upon the metric of communication efficiency is considered. While both exact integerprogramming and heuristic centrality-based methods exist for the solution of these problems, previous work has been mostly focused on the case where perfect information about the network is available. In this paper we suppose that some level of misinformation about nodes or edges has been inflicted on the observer's perception of the network, that is, there are hidden elements or fake additional elements. An extensive computational study is conducted to ascertain whether the exact integer-programming-based solutions perform better under imperfect information than heuristic methods. For large networks, exact methods cannot produce a solution in a reasonable amount of time, hence an approximation of the exact method is also considered for such instances. the obtained approximate solutions are again compared to centrality-based heuristics under the presence of imperfect data.
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results....
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We consider a robust formulation, introduced by Krause et al. (2008), of the classic cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. the robustness considered is w.r.t. adversarial removal of a given number of elements from the chosen set. In particular, for the fundamental case of single element removal, we show that one can approximate the problem up to a factor (1 - 1/e) - epsilon by making O(n(1/epsilon)) queries, for arbitrary epsilon > 0. the ideas are also extended to more general settings.
We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study ...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We introduce a method for proving Sum-of-Squares (SoS)/Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of "well-behaved" univariate polynomial inequalities. We illustrate the technique on two problems, one unconstrained and the other with constraints. More precisely, we give a short elementary proof of Grigoriev/Laurent lower bound for finding the integer cut polytope of the complete graph. We also show that the SoS hierarchy requires a non-constant number of rounds to improve the initial integrality gap of 2 for the Min-Knapsack linear program strengthened with cover inequalities.
Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-comp...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-complete to decide whether the Gomory-Chvatal closure of a rational polyhedron is empty, even when this polyhedron contains no integer point. this implies that the problem of deciding whether the Gomory-Chvatal closure of a rational polyhedron P is identical to the integer hull of P is NP-hard. Similar results are also proved for the {-1, 0, 1}-cuts and {0, 1}-cuts, two special types of Gomory-Chvatal cuts with coefficients restricted in {-1, 0, 1} and {0, 1}, respectively.
this paper presents an approach for the provision of minute reserve capacity products at the German minute reserve market provided by a pool of electric vehicles. therefore, the requirements of prequalification for ma...
详细信息
ISBN:
(纸本)9781509012985
this paper presents an approach for the provision of minute reserve capacity products at the German minute reserve market provided by a pool of electric vehicles. therefore, the requirements of prequalification for market participation have been analyzed and examined with regard to electric vehicle pools. A mixed integer linear programming model has been developed. It ensures the provision and delivery of capacity products in an optimal way, whilst the electric vehicles charging demands are also ensured.
Command-programming control contours of spacecraft are modelled with Markov chains. these models are used for the preliminary design of spacecraft control system effective structure. Corresponding optimization multi-o...
详细信息
ISBN:
(纸本)9789897581984
Command-programming control contours of spacecraft are modelled with Markov chains. these models are used for the preliminary design of spacecraft control system effective structure. Corresponding optimization multi-objective problems with algorithmically given functions of mixed variables are solved with a special stochastic algorithms called Self-configuring Non-dominated Sorting Genetic Algorithm II, Cooperative Multi-Objective Genetic Algorithm with Parallel Implementation and Co-Operation of Biology Related Algorithms for solving multi-objective integeroptimization problems which require no settings determination and parameter tuning. the high performance of the suggested algorithms is proved by solving real problems of the control contours structure preliminary design.
We generalize the reduction mechanism between linear programming problems from [1] in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we prov...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
We generalize the reduction mechanism between linear programming problems from [1] in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, the MaxCut problem and the Matching problem on 3-regular graphs. We also provide a new, very strong Lasserre integrality gap for the IndependentSet problem, which is strictly greater than the best known LP approximation, showing that the Lasserre hierarchy does not always provide the tightest SDP relaxation.
We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iteratio...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, withthe solution of a number of open instances from the MINLPLIB2 benchmark library.
We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We consider the s-t-path TSP: given a finite metric space with two elements s and t, we look for a path from s to t that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution x* as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of x* that has only one edge in each narrow cut (i.e., each cut C with x*(C) < 2). Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such "Gao trees" simultaneously at all sufficiently narrow cuts.
暂无评论