We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
We consider the question of which nonconvex sets can be represented exactly as the feasible sets of mixed-integer convex optimization problems. We state the first complete characterization for the case when the number of possible integer assignments is finite. We develop a characterization for the more general case of unbounded integer variables together with a simple necessary condition for representability which we use to prove the first known negative results. Finally, we study representability of subsets of the natural numbers, developing insight towards a more complete understanding of what modeling power can be gained by using convex sets instead of polyhedral sets;the latter case has been completely characterized in the context of mixed-integer linear optimization.
this work is devoted to development of threshold algorithms for one static probabilistic competitive facility location and design problem in the following formulation. New Company plans to enter the market and to loca...
详细信息
ISBN:
(纸本)9783319734415;9783319734408
this work is devoted to development of threshold algorithms for one static probabilistic competitive facility location and design problem in the following formulation. New Company plans to enter the market and to locate new facilities with different design scenarios. Clients of each point choose to use the facilities of Company or its competitors depending on their attractiveness and distance. the aim of the new Company is to capture the greatest number of customers thus serving the largest share of the demand. this share for the Company is elastic and depends on clients' decisions. We offer three types of threshold algorithms: Simulated annealing, threshold improvement and Iterative improvement. Experimental tuning of parameters of algorithms was carried out. A comparative analysis of the algorithms, depending on the nature and value of the threshold on special test examples up to 300 locations is carried out. the results of numerical experiments are discussed.
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these t...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
the infinite models in integerprogramming can be described as the convex hull of some points or as the intersection of halfspaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to describe finite dimensional corner polyhedra with rational data. We also discover new facts about corner polyhedra with non-rational data.
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Pr...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.
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.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from pro...
详细信息
ISBN:
(数字)9783319592503
ISBN:
(纸本)9783319592503;9783319592497
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. this paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
this paper addresses the problem of Data Centers (DC) energy efficiency by proposing a proactive optimization technique to schedule the day-ahead DC operation to minimize the operational cost. the proactive optimizati...
详细信息
ISBN:
(纸本)9781538633687
this paper addresses the problem of Data Centers (DC) energy efficiency by proposing a proactive optimization technique to schedule the day-ahead DC operation to minimize the operational cost. the proactive optimization technique is formalized as a Mixed integer Optimal Control Problem, known to be NP-hard. Because the time needed for solving this problem by some of the gradient-based solvers depends on the input data, an evolutionary algorithm based solver that computes an approximate solution in a constant number of steps is proposed. the proactive DC optimization technique is implemented using the Lindo Lingo mathematical solver and using a genetic algorithm. Finally, the proposed solution is compared against a professional mathematical solver, Lindo Lingo, being able to compute an approximate solution in cases where the Lingo solver takes too long to determine the solution, and showing an overall cost improvement of the Data Center day-ahead operation of 5%, while the Lingo based solver achieves only 3.3% cost savings on the evaluated scenarios.
High penetration of renewable resources will increase the risk of overloading transmission lines and the difficulty of controlling transmission grid in a safe operation. In this paper, a model for transmission capacit...
详细信息
ISBN:
(纸本)9781509067817
High penetration of renewable resources will increase the risk of overloading transmission lines and the difficulty of controlling transmission grid in a safe operation. In this paper, a model for transmission capacity margin assessment (TCMA) is established to quantify the transmission security with uncertain wind generation. the basic formulation is reformulated as a two-stage non-differentiable programming model. It can be transformed into a mixed integer linear programming (MILP) by duality theory and specific linearization techniques. Furthermore, an effective procedure is developed to improve the transmission capacity margin by necessary wind curtailment. A detailed case study is performed on the IEEE 31-bus system and numerical results verify the effectiveness of this TCMA framework.
In light of significant complexity of the byproduct gas system in steel industry (which limits an ability to establish its physics-based model), this study proposes a data-based predictive optimization (DPO) method to...
详细信息
ISBN:
(纸本)9781509067817
In light of significant complexity of the byproduct gas system in steel industry (which limits an ability to establish its physics-based model), this study proposes a data-based predictive optimization (DPO) method to carry out real-time adjusting for the gas system. Two stages of the method, namely the prediction modeling and real-time optimization, are involved. At the prediction stage, the states of the optimized objectives, the consumption of the outsourcing natural gas and oil, the power generation and the tank levels, are forecasted based on a proposed mixed Gaussian kernel-based prediction intervals (PIs) construction model. the Jacobian matrix of this model is represented by a kernel matrix through derivation, which greatly facilitates the subsequent calculation. At the second stage, a rolling optimization based on a mathematical programming technique involving continuous and integer decision-making variables is developed via the prediction intervals.
Kondo et al. (DS 2014) proposed integer linear programming formulations for computing the tree edit distance and its variants between unordered rooted trees. they showed that the tree edit distance, segmental distance...
详细信息
ISBN:
(纸本)9783319711478;9783319711461
Kondo et al. (DS 2014) proposed integer linear programming formulations for computing the tree edit distance and its variants between unordered rooted trees. they showed that the tree edit distance, segmental distance, and bottom-up segmental distance problems respectively have integer linear programming formulations with O(nm) variables and O(n(2) m(2)) constraints, where n and m are the number of nodes of two input trees. In this work, we propose new integer linear programming formulations for these three distances and the bottom-up distance by combining with dynamic programming. For computing the tree edit distance, we solve O(nm) subproblems, each of which is formulated by an integer linear program with O(nm) variables and O(n + m) constraints. For the other three distances, each subproblem can be reduced to the maximum weight matching problem in a bipartite graph which is solvable in polynomial time. In order to compute the distances from the solutions of subproblems, we also give a unified integer linear formulation with O(nm) variables and O(n + m) constraints. We conducted a computational experiment to evaluate the performance of our methods. the experimental results show that our methods remarkably outperformed to the previous methods due to Kondo et al.
暂无评论