General purpose cutting planes have played a central role in modern IP solvers. In practice, the Gomory mixed integer cut has proven to be among the most useful general purpose cuts. One may obtain this inequality fro...
详细信息
ISBN:
(纸本)9783642130359
General purpose cutting planes have played a central role in modern IP solvers. In practice, the Gomory mixed integer cut has proven to be among the most useful general purpose cuts. One may obtain this inequality from the group relaxation of an IP, which arises by relaxing non-negativity on the basic variables. We study the mixed integer cut as a facet of the master cyclic group polyhedron and characterize its extreme points and adjacent facets in this setting. Extensions are provided under automorphic and homomorphic mappings.
In this article, we investigate the costs of optical network Capital Expenditure (CapEx) components which include fiber, optical amplifier (OA), cable and conduit. the CapEx of high-capacity optical network under give...
详细信息
ISBN:
(纸本)9781479972197
In this article, we investigate the costs of optical network Capital Expenditure (CapEx) components which include fiber, optical amplifier (OA), cable and conduit. the CapEx of high-capacity optical network under given traffic requests is optimized, and results are analyzed to evaluate the influences of Multi-core Fiber (MCF) communication system on the components of optical network CapEx. To solve the optimization problem, network CapEx is modelled and an integer linear programming (ILP) formulation is proposed. Numerical results show that by using MCF communication system, optical network CapEx can be reduced significantly. the cost of OA takes the largest proportion of the network CapEx, and can be reduced by deploying MCF communication system to optical networks. Fiber density can be increased by using MCF, thus decreasing the costs of cable and conduit.
We introduce the framework of branched polyhedral systems that can be used in order to construct extended formulations for polyhedra by combining extended formulations for other polyhedra. the framework, for instance,...
详细信息
ISBN:
(纸本)9783642130359
We introduce the framework of branched polyhedral systems that can be used in order to construct extended formulations for polyhedra by combining extended formulations for other polyhedra. the framework, for instance, simultaneously generalizes extended formulations like the well-known ones (see Balas [1]) for the convex hulls of unions of polyhedra (disjunctive programming) and like those obtained from dynamic programming algorithms for combinatorialoptimization problems (due to Martin, Rardin, and Campbell [11]). Using the framework, we construct extended formulations for full orbitopes (the convex hulls of all 0/1-matrices with lexicographically sorted columns), we show for two special matching problems, how branched polyhedral systems can be exploited in order to construct formulations for certain nested combinatorial problems, and we indicate how one can build extended formulations for stable set polytopes using the framework of branched polyhedral systems.
We extend the theoretical foundations of the branch-and-cut method using lift-and-project cuts for a broader class of disjunctive constraints, and also present a new, substantially improved disjunctive cut generator. ...
详细信息
ISBN:
(纸本)354064590X
We extend the theoretical foundations of the branch-and-cut method using lift-and-project cuts for a broader class of disjunctive constraints, and also present a new, substantially improved disjunctive cut generator. Employed together with an efficient commercial MIP solver, our code is a robust, general purpose method for solving mixed integer programs. We present extensive computational experience withthe most difficult problems in the MIPLIB library.
Accordirig to the present state of the theory of the matroid matching problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double...
详细信息
ISBN:
(纸本)9783540727910
Accordirig to the present state of the theory of the matroid matching problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double circuits. In this paper we prove that if a polymatroid has no double circuits at all, then a partition-type min-max formula characterizes the size of a maximum matching. We provide applications of this result to parity constrained orientations and to a rigidity problem. A polynomial time algorithm is constructed by generalizing the principle of shrinking blossoms used in Edmonds' matching algorithm [2].
We present a new approach for exactly solving general chance constrained mathematical programs having discrete distributions. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible ...
详细信息
ISBN:
(纸本)9783642130359
We present a new approach for exactly solving general chance constrained mathematical programs having discrete distributions. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and currently available methods are only able to find provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and integerprogramming techniques, to combine the results of these subproblems to yield strong valid inequalities. Computational results on a chance-constrained two-stage problem arising in call center staffing indicate the approach works significantly better than both an existing mixed-integerprogramming formulation and a simple decomposition approach that does not use strong valid inequalities. thus, the strength of this approach results from the successful merger of stochastic programming decomposition techniques withintegerprogramming techniques for finding strong valid inequalities.
A well established heuristic approach for solving various bicriteria optimization problems is to enumerate the set of Pareto optimal solutions, typically using some kind of dynamic programming approach. the heuristics...
详细信息
ISBN:
(纸本)9783540727910
A well established heuristic approach for solving various bicriteria optimization problems is to enumerate the set of Pareto optimal solutions, typically using some kind of dynamic programming approach. the heuristics following this principle are often successful in practice. their running time, however, depends on the number of enumerated solutions, which can be exponential in the worst case. In this paper, we prove an almost tight bound on the expected number of Pareto optimal solutions for general bicriteria integeroptimization problems in the framework of smoothed analysis. Our analysis is based on a semi-random input model in which an adversary can specify an input which is subsequently slightly perturbed at random, e. g., using a Gaussian or uniform distribution. Our results directly imply tight polynomial bounds on the expected running time of the Nemhauser/Ullmann heuristic for the 0/1 knapsack problem. Furthermore, we can significantly improve the known results on the running time of heuristics for the bounded knapsack problem and for the bicriteria shortest path problem. Finally, our results also enable us to improve and simplify the previously known analysis of the smoothed complexity of integerprogramming.
the Discrete Event optimization (DEO) framework was recently proposed to formulate the simulation-optimization model of the Joint Workstation, Workload and Buffer Allocation Problem (JWWBAP) of the open flow line. How...
详细信息
ISBN:
(纸本)9781509067817
the Discrete Event optimization (DEO) framework was recently proposed to formulate the simulation-optimization model of the Joint Workstation, Workload and Buffer Allocation Problem (JWWBAP) of the open flow line. However, the computational effort to solve the DEO model at optimality is quite high, because it is a mixed integer linear programming model. this work proposes a simulation cutting approach to efficiently solve the DEO model of the JWWBAP. Specifically, the DEO model is decomposed into an optimization model and a simulation model, which are the master problem and the subproblem in Benders decomposition, respectively. the optimization model is solved to find a system configuration, and the simulation model is solved to add cuts to the optimization model. An algorithm is proposed to generate cut using the simulation trajectory. Numerical analysis shows that the exact DEO model can be solved efficiently.
In past several linearization of the Quadratic Assignment Problem (QAP) which is a NP-hard problem have been given (See Lawler (1962) and Christofides et al. (1980)). Here, a new set of constraints that perfectly line...
详细信息
ISBN:
(纸本)9789955282839
In past several linearization of the Quadratic Assignment Problem (QAP) which is a NP-hard problem have been given (See Lawler (1962) and Christofides et al. (1980)). Here, a new set of constraints that perfectly linearize the QAP is proposed. the new linearization is compared with other linearization and it is found that proposed linearization performs better in time complexity. We have also shown that linear programming relaxations of these linearizations give optimal solution for the 0-1 integer linearization of QAP. Empirical evidence shows that this results in substantial savings in computational time. T-test has been also carried out to show the significance statistically.
this paper studies the quayside operation problem, in which three seaside planning decisions are integrated, withthe objective of minimizing the maximum relative tardiness. A refinement of the state-of-the-art formul...
详细信息
ISBN:
(纸本)9781538651780
this paper studies the quayside operation problem, in which three seaside planning decisions are integrated, withthe objective of minimizing the maximum relative tardiness. A refinement of the state-of-the-art formulation is presented in this work, and an improved exact combinatorial Benders decomposition algorithm is devised for the problem at container terminals which used to be typically modeled by mixed-integer linear programming problems containing a large number of "big-M" coefficients.
暂无评论