Discrete optimization
In this paper, we introduce the separable task assignment problem (STAP) in which n separable tasks are assigned tom agents subject to agents’ capacity constraints. The objective is to minimize the costs that occur during the manufacturing and the communication between agents.Atask is separable if it can be divided into two pieces, and both of them can be assigned individually or together to any agents. A separable task is considered as being assigned if and only if its two pieces are both assigned. Since several discrete (ternary) variables may be involved in STAP modeling, computing the problem in a reasonable time period is not an easy work. We replace the ternary variables by binary and continuous variables through extending the logarithmic method introduced by Li et al. (INFORMS J Comput 25(4): 643–653, 2012) and Vielma et al.(Oper Res 58(2): 303–315, 2010). Our numerical experiments demonstrate that the newly generated model performs well in solving difficult separable task-assignment problems for pretty large scale of instance sizes.
A general (abstract) scheme of iterative improvement and optimization on the base of extension, localization principles which would help to generate new concrete methods and algorithms for new problems is proposed. Application to optimal control problems for continuous systems is considered. Visual example is given.
In this paper, under some suitable assumptions without any involving information on the solution set, we give some sufficient conditions for the upper semicontinuity, lower semicontinuity, and closedness of the solution set mapping to a parametric set optimization problem with possible less order relation.
In this paper, the structural properties of revenue management in a hubto- hub airline network is studied. Using a reformulated network flow version of the problem, it is shown that the optimal value has supermodularity, submodularity, and L concavity in the network’s capacities dimensions. It is thus deduced that the certainty equivalent control thresholds used in the revenue management problem have monotone properties. These structural properties add important managerial insights into the network revenue management system.
In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph G = (V, E) and a set of vertex sets V = {V1, V2, · · · , Vl }. Every edge in E has a nonnegative cost, and every vertex set in V has a nonnegative penalty cost. For a given edge set F ⊆ E, vertex set Vi ∈ V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.
In this paper, a newtransformation functionwas proposed for finding global minimizer of discrete optimization problems. We proved that under some general assumptions the new transformation function possesses the properties of both the tunneling functions and the filled functions. Only one parameter was included in the proposed function, and it can be adjusted easily in the realization. Numerical results demonstrate the effectiveness of the proposed method.
This paper deals with a general variant of the reverse undesirable (obnoxious) center location problem on cycle graphs. Given a ‘selective’ subset of the vertices of the underlying cycle graph as location of the existing customers, the task is to modify the edge lengths within a given budget such that the minimum of distances between a predetermined undesirable facility location and the customer points is maximized under the perturbed edge lengths. We develop a combinatorial O(n log n) algorithm for the problem with continuous modifications. For the uniform-cost model, we solve this problem in linear time by an improved algorithm. Furthermore, exact solution methods are proposed for the problem with integer modifications.
This paper addresses a geometric programming problem, where the objective function and constraints are interval-valued functions. The concept of acceptable feasible region is introduced, and a methodology is developed to transform this model to a general optimization problem, which is free from interval uncertainty. Relationship between the solution of the original problem and the transformed problem is established. The methodology is illustrated through numerical examples. Solutions by the proposed method and previous methods are analyzed.
The aim of this paper is to establish a fundamental theory of convex analysis for the sets and functions over a discrete domain. By introducing conjugate/biconjugate functions and a discrete duality notion for the cones over discrete domains, we study duals of optimization problems whose decision parameters are integers. In particular, we construct duality theory for integer linear programming, provide a discrete version of Slater’s condition that implies the strong duality and discuss the relationship between integrality and discrete convexity.
The pooling problem, also called the blending problem, is fundamental in production planning of petroleum. It can be formulated as an optimization problem similar with the minimum-cost flow problem. However, Alfaki and Haugland (J Glob Optim 56:897–916,2013) proved the strong NP-hardness of the pooling problem in general case. They also pointed out that it was an open problem to determine the computational complexity of the pooling problem with a fixed number of qualities. In this paper, we prove that the pooling problem is still strongly NP-hard even with only one quality. This means the quality is an essential difference between minimum-cost flow problem and the pooling problem. For solving large-scale pooling problems in real applications, we adopt the non-monotone strategy to improve the traditional successive linear programming method. Global convergence of the algorithm is established. The numerical experiments show that the non-monotone strategy is effective to push the algorithm to explore the global minimizer or provide a good local minimizer. Our results for real problems from factories show that the proposed algorithm is competitive to the one embedded in the famous commercial software Aspen PIMS.
