Efficiently devising optimal offers for Generation Companies (GenCos) in Day-Ahead Electricity Markets is a challenging task. Most solution procedures found in technical literature are built upon non-convex optimizati...
详细信息
Efficiently devising optimal offers for Generation Companies (GenCos) in Day-Ahead Electricity Markets is a challenging task. Most solution procedures found in technical literature are built upon non-convex optimization structures, known as Mathematical Programming with Equilibrium Constraints (MPECs), that are difficult to scale to realistic-size instances. Therefore, the main objective of this work is to propose an efficient procedure to aid GenCos to devise optimal offering strategies in Day-Ahead Electricity Markets composed of a single bidding area. Supported by a set of technical results and strong duality theory, a tailored procedure that can be executed in polynomial-time in the number of firms is constructed with global-optimality guarantees. Numerical experiments are conducted, benchmarking the proposed approach against the standard MPEC-derived procedure typically found in the technical literature to solve the offering problem. We found that the proposed solution approach grows (roughly) linearly with the instance size and significantly overcomes (in the order of 20-25 times faster) its counterpart in the most demanding instances. Furthermore, the scalability of the MPEC-derived procedure is challenged even for medium-scale instances, whilst the proposed polynomial-time procedure was able to handle all instances in a reasonable computational time.
In this paper, we give the first polynomialtimealgorithm to compute the generalized Hermite normal form for a matrix F over Z[x], or equivalently, the reduced Grobner basis of the Z[x]-module generated by the column...
详细信息
In this paper, we give the first polynomialtimealgorithm to compute the generalized Hermite normal form for a matrix F over Z[x], or equivalently, the reduced Grobner basis of the Z[x]-module generated by the column vectors of F. The algorithm has polynomial bit size computational complexities and is also shown to be practically more efficient than existing algorithms. The algorithm is based on three key ingredients. First, an F4 style algorithm to compute the Grobner basis is adopted, where a novel prolongation is designed such that the sizes of coefficient matrices under consideration are nicely controlled. Second, the complexity bound of the algorithm is achieved by a nice estimation for the degree and height bounds of the polynomials in the generalized Hermite normal form. Third, fast algorithms to compute Hermite normal forms of matrices over Z are used as the computational tool. (C) 2018 Elsevier B.V. All rights reserved.
We consider the independent set problem, a classical NP-hard optimization problem that remains hard even under substantial restrictions on the input graphs. The complexity status of the problem is unknown for the clas...
详细信息
ISBN:
(纸本)9783030307868;9783030307851
We consider the independent set problem, a classical NP-hard optimization problem that remains hard even under substantial restrictions on the input graphs. The complexity status of the problem is unknown for the classes of P-k-free graphs for all k >= 7 and for the class of even-hole-free graphs, that is, graphs not containing any even induced cycles. Using the technique of augmenting graphs we show that the independent set problem is solvable in polynomialtime in the class of even-hole-free graphs not containing an induced path on 10 vertices. Our result is developed in the context of the more general class of {P-10, C-4, C-6}-free graphs.
The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job...
详细信息
ISBN:
(纸本)9783030226299;9783030226282
The paper is concerned with the two-machine flow shop, where each job needs storage space (a buffer requirement) during the entire time of its processing. The buffer requirement is determined by the duration of job's first operation. The goal is to minimise the time needed for the completion of all jobs. This scheduling problem is NP-hard in the strong sense even for very restricted cases such as the case with a given order of jobs processing on one of the machines. The paper contributes to the efforts of establishing the borderline between the NP-hard and polynomial-time solvable cases by proving that there exists a polynomial-time algorithm which constructs an optimal schedule if the duration of each operation does not exceed one-fifth of the buffer capacity. The presented polynomial-time algorithm is used as a basis for a heuristic for the general case. This heuristic is complemented by a Lagrangian relaxation based heuristic and a bin-packing based constructive heuristic. The heuristics are tested by computational experiments.
This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for check...
详细信息
This paper investigates computing completely positive (cp) decompositions of positive semi-definite (PSD) matrices, a problem which arises in many applications. We propose the first polynomial-time algorithm for checking if a given PSD matrix has cp-rank of at most r, when r is a given constant. In addition, we present a polynomial-time algorithm for computing a (rational) cp-decomposition of such a matrix if it exists, within any desired accuracy. (C) 2016 Elsevier B.V. All rights reserved.
The sailing speed optimization problem aims to determine the optimal cruising speeds of ships by balancing the number of ships required on services, the fuel consumption, and the level of service provided for customer...
详细信息
The sailing speed optimization problem aims to determine the optimal cruising speeds of ships by balancing the number of ships required on services, the fuel consumption, and the level of service provided for customers. The level of service can be incorporated into a sailing speed optimization model from the perspective of supply chain management or from the perspective of shipping lines. We design a polynomial-time algorithm workable to solve the two models based on bi-section search methods. The novelties of the algorithm include constructing a new parameter on which the bi-section search will be executed and deriving a near-optimal solution by taking advantage of the problem structure. We also provide theoretical results that guarantee the validity of the polynomial-time algorithm. (C) 2016 Elsevier Ltd. All rights reserved.
Large amount of contents in the Internet have increased loads of contents servers, networks and data centers, which may degrade quality of service. To solve this problem, there is a method that some mirror servers pro...
详细信息
ISBN:
(纸本)9781467376952
Large amount of contents in the Internet have increased loads of contents servers, networks and data centers, which may degrade quality of service. To solve this problem, there is a method that some mirror servers providing the same contents are located on a network and a request is navigated to one of the mirror servers. As the location of the mirror servers affects the quality of service, it is important to locate the mirror servers in the network so that a network should connect a user and one of mirror servers with small hop length after links fail. In this paper, we address the server location problem that determines the location of the servers satisfying the following constraint: any users can access servers within a small hop count even if some links fail. In the previous research, we proved that this problem is NP-hard and proposed some heuristic algorithms. In this paper, we present a polynomial-time algorithm when the number of simultaneously failed links is restricted to one and the increase of hop length is restricted;in other words, we can get the optimum solution of the optimization version to minimize the number of servers in polynomialtime. Furthermore, we evaluate the performance of actual ISP network topologies by the algorithm from the viewpoint of the number of servers.
In this paper an exterior point polynomialtimealgorithm for convex quadratic programming problems is proposed. We convert a convex quadratic program into an unconstrained convex program problem with a self-concordan...
详细信息
In this paper an exterior point polynomialtimealgorithm for convex quadratic programming problems is proposed. We convert a convex quadratic program into an unconstrained convex program problem with a self-concordant objective function. We show that, only with duality, the Path-following method is valid. The computational complexity analysis of the algorithm is given.
This paper proposes a polynomial -timealgorithm for a server allocation problem in delay -sensitive Internet -ofThings (IoT) monitoring services. The server allocation problem determines the appropriate servers to wh...
详细信息
This paper proposes a polynomial -timealgorithm for a server allocation problem in delay -sensitive Internet -ofThings (IoT) monitoring services. The server allocation problem determines the appropriate servers to which the database and application are allocated to minimize the maximum delay between the latest update of reference data and the start of application processing for monitoring data. The server allocation problem was previously handled by expressing it as an integer linear programming (ILP) problem. Nevertheless, it fails to meet the computational time complexity needed to solve the problem, and it does not offer a more efficient technique than the ILP approach. The proposed algorithm consists of two components. The first step entails choosing utilization servers for both the database and the application. Next, the second phase entails matching each usage server and its corresponding IoT device. We prove that the proposed algorithm obtains an optimal solution in polynomialtime. We compare computation times between the ILP approach and the proposed algorithm. Numerical results show that the proposed algorithm obtains the optimal solution faster than the ILP approach.
We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall dis...
详细信息
We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall distance traveled. The problem has been classified as open in a recent taxonomy of optimal picking problems in automated warehouses. In this paper, we analyze some non-trivial properties of the problem and we describe a polynomial-time dynamic programming algorithm to solve it to proven optimality.
暂无评论