Inkjet printing is a promising technology for new display mass production. However, a major challenge in inkjet printing applications is pixel ink volume nonuniformity caused by the volume error of droplets ejected fr...
详细信息
Inkjet printing is a promising technology for new display mass production. However, a major challenge in inkjet printing applications is pixel ink volume nonuniformity caused by the volume error of droplets ejected from multiple nozzles. This nonuniformity can lead to nonuniform pixel film thickness and Mura defects in a display panel. To address this issue, an integer programming-based droplet-intermixing printing method for highuniformity pixel ink volume control is proposed in this study. The printing method is used to homogenize the volume of ink deposited in each pixel by intermixing droplets from different nozzles to improve the whole-panel uniformity. To ensure that the droplet intermixing results meet the printing process requirements, a specific scheduling and printing planning model for the method is established. According to the droplet volume from each nozzle and the printing pattern, the most efficient printing path and nozzle ejection action are obtained by the established model while meeting the volume uniformity requirement of pixel ink. Experiments show that the proposed printing method can realize pixel film thickness error control under +/- 6 nm on a 400 cm(2 )display substrate, and the uniformity of different pixels is less than +/- 4.62 %. Compared with traditional method, the achieved uniformity is improved at 45.4 % under the same conditions. This method has been applied in printed display manufacturing equipment and achieved good results.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods...
详细信息
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.
Unit commitment has been at the center of power system operations for over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization so...
详细信息
Unit commitment has been at the center of power system operations for over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization solvers to tackle it, and often resort to simplifications to make the problem tractable and solvable in reasonable times. Nonetheless, despite the simplifications and advancements in commercial optimization solvers, solving the unit commitment in a timely manner is still a challenge. In this work, we propose a parallel dual dynamic integer programming approach for solving this problem. Different from what can be currently found in the literature, our parallel approach is applied to a deterministic problem and thus requires induced parallelization. Our strategy is assessed on 20 cases of a hydrothermal system with over 7,000 buses and it is able to solve all instances to a 0.1% gap in less than two hours with speed-ups up to 9.2 compared to a sequential strategy. We also apply our strategy to a purely thermal, large-scale academic system with 9,241 buses, 16,049 transmission lines and 1,445 generating units, for which our strategy returns a 0.1% solution in less than 30 min.
Kidney exchange programs (KEPs) represent an additional possibility of transplant for patients suffering from end-stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, ...
详细信息
Kidney exchange programs (KEPs) represent an additional possibility of transplant for patients suffering from end-stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, the pair recipient-donor can join a pool of incompatible pairs and, if compatibility between recipient and donor in two or more pairs exists, organs can be exchanged between them. The problem can be modelled as an integer program that in general aims at finding the pairs that should be selected for transplant such that maximum number of transplants is performed. In this paper, we consider that for each recipient there may exist a preference order over the organs that he/she can receive, since a recipient may be compatible with several donors but the level of compatibility with the recipient might vary for different donors. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists, i.e., there is no cycle such that all recipients prefer the donor in that cycle rather than that in the exchange. For this purpose we propose four novel integer programming models based on the well-known edge and cycle formulations, and also on the position-indexed formulation. These formulations are adjusted for both finding stable and strongly stable exchanges under strict preferences and for the case when ties in preferences may exist. Further-more, we study a situation when the stability requirement can be relaxed by addressing the trade-off between maximum cardinality versus number of blocking cycles allowed in a solution. The effectiveness of the proposed models is assessed through extensive computational experiments on a wide set of in-stances. Results show that the cycle-edge and position-indexed formulations outperform the other two formulations. Another important practical outcome is that targeting strongly stable solutions has a much higher negative impact on the number of transplants (with an average r
In the classic integer programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that...
详细信息
In the classic integer programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that Ax = b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ITCS 2019]. Jansen and Rohwedder designed an algorithm for (IPF) with running time O(m Delta)(m) log(Delta) log (Delta + parallel to b parallel to(infinity)) + O(mn). Here, Delta is an upper bound on the absolute values of the entries of A. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of n(O(m/log m)) . parallel to b parallel to(O(m))(infinity). We also prove that assuming ETH, (IPF) cannot be solved in time f (m) . (n . parallel to b parallel to(infinity))(O(m/log m)) for any computable function f. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IPF) when the path-width of the corresponding column-matroid is a constant.
In order to further promote the application and development of unmanned aviation in the manned field, and reduce the difficulty that airlines cannot avoid due to unexpected factors such as bad weather, aircraft failur...
详细信息
In order to further promote the application and development of unmanned aviation in the manned field, and reduce the difficulty that airlines cannot avoid due to unexpected factors such as bad weather, aircraft failure, and so on, the problem of restoring aircraft routes has been studied. To reduce the economic losses caused by flight interruption, this paper divides the repair problem of aircraft operation plans into two sub problems, namely, the generation of flight routes and the reallocation of aircraft. Firstly, the existing fixed-point iteration method proposed by Dang is used to solve the feasible route generation model based on integer programming. To calculate quickly and efficiently, a segmentation method that divides the solution space into mutually independent segments is proposed as the premise of distributed computing. The feasible route is then allocated to the available aircraft to repair the flight plan. The experimental results of two examples of aircraft fault grounding and airport closure show that the method proposed in this paper is effective for aircraft route restoration.
We present a mixed integer programming formulation for the problem of clustering a set of points in Rd with axis-parallel clusters, while allowing to discard a pre-specified number of points, thus declared to be outli...
详细信息
We present a mixed integer programming formulation for the problem of clustering a set of points in Rd with axis-parallel clusters, while allowing to discard a pre-specified number of points, thus declared to be outliers. We identify a family of valid inequalities separable in polynomial time, we prove that some inequalities from this family induce facets of the associated polytope, and we show that the dynamic addition of cuts coming from this family is effective in practice.& COPY;2023 Elsevier B.V. All rights reserved.
Flexible process planning (FPP) involves selecting and sequencing the requisite operations according to technological requirements, and meanwhile allocating a right machine, a right tool and a right access direction t...
详细信息
Flexible process planning (FPP) involves selecting and sequencing the requisite operations according to technological requirements, and meanwhile allocating a right machine, a right tool and a right access direction to each selected operation by a given criterion. In this article, the FPP problem is exactly and concisely formulated as linear integer programming models based on the topology of the AND/OR-network under two criteria: production cost minimisation and completion time minimisation. Distinctively, more flexible manufacturing elements and process plan evaluation criteria are considered;more complicated tool and access direction changeover identifications are linearly expressed without the big-M parameter. Compared with the latest mathematical programming models for process planning, the proposed models have lower complexity and better performance. The results from numerous comparative experiments indicate that (i) the number of decision variables of the proposed models reduces approximately by 68% and the number of constraints of the proposed models dramatically reduces by 99%;(ii) within the same running time, the proposed models can exactly solve more benchmark cases than the latest models;and (iii) the solutions obtained by the proposed models are also better than the best ones founded by some state-of-the-art meta-heuristic algorithms.
Two-stage stochastic mixed-integer programs (SMIPs) with general integer variables in the second-stage are generally difficult to solve. This paper develops the theory of integer set reduction for characterizing a sub...
详细信息
Two-stage stochastic mixed-integer programs (SMIPs) with general integer variables in the second-stage are generally difficult to solve. This paper develops the theory of integer set reduction for characterizing a subset of the convex hull of feasible integer points of the second-stage subproblem which can be used for solving the SMIP with pure integer recourse. The basic idea is to use the smallest possible subset of the subproblem feasible integer set to generate a valid inequality like Fenchel decomposition cuts with a goal of reducing computation time. An algorithm for obtaining such a subset based on the solution of the subproblem linear programming relaxation is devised and incorporated into a decomposition method for SMIP. To demonstrate the performance of the new integer set reduction methodology, a computational study based on randomly generated knapsack test instances was performed. The results of the study show that integer set reduction aids in speeding up cut generation, leading to better bounds in solving SMIPs with pure integer recourse than using a direct solver.
The distributionally robust chance constrained integer programming problems are notoriously hard to solve due to the stochastic feature and the discrete nature of integer variables. In this paper, an exact solution me...
详细信息
The distributionally robust chance constrained integer programming problems are notoriously hard to solve due to the stochastic feature and the discrete nature of integer variables. In this paper, an exact solution method is developed for linear integer programming problems with the distributionally robust chance constraint. By exploring the geometric properties, some domain cut techniques based on feasible points and infeasible points are derived. Thus cut off some sub-boxes which do not contain any optimal solution and the optimality gap is reduced successively in the solution iterations. Then the optimal solution will be found in a finite number of iterations. Encouraging computational results are also reported in the paper.
暂无评论