We present a spatial Branch and Bound and spatial Branch and Benders Decomposition approach together with the Breakpoint exact Algorithm (BEA) to tackle the uncapacitated choice-based pricing problem (CPP) where deman...
详细信息
We present a spatial Branch and Bound and spatial Branch and Benders Decomposition approach together with the Breakpoint exact Algorithm (BEA) to tackle the uncapacitated choice-based pricing problem (CPP) where demand is captured by a discrete choice model (DCM) based on the random utility principle. We leverage problem characteristics to reformulate the state-of-the-art simulation-based formulation of the CPP as a mixed-integer linear program (MILP) into a non-convex quadratically constrained quadratic program (QCQP), and then into a non-convex QCQP with linear objective (QCQP-L). We solve this reformulation with an efficient spatial Branch and Bound procedure utilizing the McCormick envelope for relaxations, which are then solved using Benders decomposition. We further exploit utility breakpoints to develop the BEA, which scales polynomially in the number of customers and draws, providing a fast option for low numbers of prices. Our methods are evaluated against solving the MILP, QCQP, or QCQP-L with GUROBI on a mixed logit (ML) parking space operator case study. We outspeed the MILP by several orders of magnitude when optimizing one or two prices and reduce computational time drastically for larger numbers of prices. When comparing to algorithms tailored for the CPP with ML demand specifically, our approaches significantly outperform the state of the art. Our methodology suits all choice-based optimization problems with linear-in-price utilities, given any DCM.
We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*(cd degrees), where cd is a function of the maximum occurrence d of variables (d can also be the average occurrence...
详细信息
We present fast algorithms for the general CNF satisfiability problem (SAT) with running-time bound O*(cd degrees), where cd is a function of the maximum occurrence d of variables (d can also be the average occurrence when each variable appears at least twice), and degrees is the number of variables in the input formula. Similar to SAT with bounded clause lengths, SAT with bounded occurrences of variables has also been extensively studied in the literature. Especially, the running-time bounds for small values of d, such as d = 3 and d = 4, have become bottlenecks for algorithms evaluated by the formula length L and other algorithms. In this paper, we show that SAT can be solved in time O*(1.1238 degrees) ford = 3 and O*(1.2628 degrees) ford = 4, improving the previous results O*(1.1279 degrees) and O*(1.2721 degrees) obtained by Wahlstr & ouml;m (SAT 2005) nearly 20 years ago. For d >= 5, we obtain a running time bound of O*(1.0641d degrees), implying a bound of O*(1.0641L) with respect to the formula length L.
We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be ...
详细信息
We study a scheduling problem where the jobs we have to perform are composed of one or more tasks. If two jobs sharing a non-empty subset of tasks are scheduled on the same machine, then these shared tasks have to be performed only once. This kind of problem is known in the literature under the names of VM-PACKING or PAGINATION. Our objective is to schedule a set of these objects on two parallel identical machines, with the aim of minimizing the makespan. This problem is NP-complete as an extension of the PARTITION problem. In this paper we present three exact algorithms with worst-case time-complexity guarantees, by exploring different branching techniques. Our first algorithm focuses on the relation between jobs sharing one or more symbols in common, whereas the two other algorithms branches on the shared symbols.
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called MINIMUM WEIGHT lambda- CONNECTED ...
详细信息
We design exact algorithms for the following two problems in survivable network design: (i) designing a minimum cost network with a desired value of edge connectivity, which is called MINIMUM WEIGHT lambda- CONNECTED SPANNING SUBGRAPH and (ii) augmenting a given network to a desired value of edge connectivity at a minimum cost which is called MINIMUM WEIGHT lambda- CONNECTIVITY AUGMENTATION. It is easy to see that a minimum solution to these problems contains at most 2 lambda(n - 1) edges. Using this fact one can design a brute-force algorithm which runs in time 2(O()(lambda n log n)()), however no better algorithms were known previously. In this paper, we give the first single exponential time algorithm for these problems, i.e. running in time 2(O()(lambda n)), for both undirected and directed networks. Our results are obtained via well known characterizations of lambda-connected graphs, their connections to linear matroids and the recently developed technique of dynamic programming with representative sets.
In this paper, we address the constrained parallel-machine scheduling problem with divisible processing times and penalties (the CPS-DTP problem), which is a further generalization of the parallel-machine scheduling p...
详细信息
In this paper, we address the constrained parallel-machine scheduling problem with divisible processing times and penalties (the CPS-DTP problem), which is a further generalization of the parallel-machine scheduling problem with divisible processing times (the PS-DT problem). Concretely, given a set M of m identical machines and a set J of n independent jobs, each job has a processing time and a penalty, the processing times of these n jobs are divisible, and we implement these n jobs under the requirement that each job in J must be either continuously executed on one machine with its processing time, or rejected with its penalty that we must pay for. We may consider three versions of the CPS-DTP problem, respectively. (1) The constrained parallel-machine scheduling problem with divisible processing times and total penalties (the CPS-DTTP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement, the objective is to minimize the of such a schedule T for jobs in A plus the summation of penalties paid for jobs not in A;(2) The constrained parallel-machine scheduling problem with divisible processing times and maximum penalty (the CPS-DTMP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement, the objective is to minimize themakespan of such a schedule T for jobs in A plus maximum penalty paid for jobs not in A;(3) The constrained parallel-machine scheduling problem with divisible processing times and bounded penalty (the CPS-DTBP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement and the summation of penalties paid for jobs not in A is no more than a fixed bound, the objective is to minimize the makespan of such a schedule T for jobs in A. As our main contributions, we design three exact algorithms to solve the CPS-DTTP problem, the CPS-DTMP problem and the CPS-DTBP problem, and these thre
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problem...
详细信息
ISBN:
(纸本)9783030895433;9783030895426
The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. In this paper, we design several reduction rules and a fast exact algorithm for the maximum weighted independent set problem, and use the measure-and-conquer technique to analyze the running time bound of the algorithm. Our algorithm works on general weighted graphs and it has a good running time bound on sparse graphs. If the graph has an average degree at most 3, our algorithm runs in O* (1.1443(n)) time and polynomial space, improving previous running time bounds for the problem in cubic graphs using polynomial space.
We tackle an optimization problem arising in the design of sensor networks: given a set of sensors, only one being connected to a backbone, to establish connection routes from each of them to the sink. Under a shortes...
详细信息
We tackle an optimization problem arising in the design of sensor networks: given a set of sensors, only one being connected to a backbone, to establish connection routes from each of them to the sink. Under a shortest path routing protocol, the set of connections form a spanning tree. Energy is required to transmit and receive data, and sensors have limited battery capacity: as soon as one sensor runs out of battery, a portion of the network is disconnected. We, therefore, search for the spanning tree maximizing the time elapsed before such a disconnection occurs, and therefore, maintenance is required. We propose new mathematical formulations for the problem, proving and exploiting theoretical results on its combinatorial structure. On that basis, we design algorithms offering a priori guarantees of global optimality. We undertake an extensive experimental campaign, showing our algorithms to outperform previous ones from the literature by orders of magnitude. We also identify which instance features have higher impact on network lifetime.
We consider a stochastic version of the 0-1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The obj...
详细信息
We consider a stochastic version of the 0-1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The objective is to maximise the expected profit of the selected items. The resulting problem, denoted as 0-1 Time-Bomb Knapsack Problem (01-TB-KP), has applications in logistics and cloud computing scheduling. We introduce a nonlinear mathematical formulation of the problem, study its computational complexity, and propose techniques to derive upper and lower bounds using convex optimisation and integer linear programming. We present three exact approaches based on enumeration, branch and bound, and dynamic programming, and computationally evaluate their performance on a large set of benchmark instances. The computational analysis shows that the proposed methods outperform the direct application of nonlinear solvers on the mathematical model, and provide high quality solutions in a limited amount of time.
Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to choose the location of ellipses given their major and minor axes to cover demand points, maximizing a function depending on th...
详细信息
Planar Maximum Covering Location by Ellipses is an optimization problem where one wants to choose the location of ellipses given their major and minor axes to cover demand points, maximizing a function depending on the value of covered points. We propose new exact algorithms for two versions of this problem, one where the ellipses have to be parallel to the coordinate axes, and another where they can be freely rotated. Besides finding optimal solutions for previously published instances, including the ones where no optimal solution was known, both algorithms proposed by us were able to obtain optimal solutions for some new larger instances with up to seven hundred demand points and five ellipses. (C) 2020 Elsevier B.V. All rights reserved.
The INDEPENDENT CUTSET problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is NP-complete even when the input graph is planar and has maximum degree fiv...
详细信息
The INDEPENDENT CUTSET problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is NP-complete even when the input graph is planar and has maximum degree five. We first present a O & lowast;(1.4423n)time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO1-expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present FPT-time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P5-free graphs. We close by introducing the notion of alpha-domination, which generalizes key ideas of this article. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
暂无评论