Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMulti-objective integer programming: Synergistic parallel approaches
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Exactly solving multi-objective integer programming (MOIP) problems is often a very time consuming process, especially for large and complex problems. Parallel computing has the potential to significantly reduce the time taken to solve such problems, but only if suitable algorithms are used. The first of our new algorithms follows a simple technique that demonstrates impressive performance for its design. We then go on to introduce new theory for developing more efficient parallel algorithms. The theory utilises elements of the symmetric group to apply a permutation to the objective functions to assign different workloads, and applies to algorithms that order the objective functions lexicographically. As a result, information and updated bounds can be shared in real time, creating a synergy between threads. We design and implement two algorithms that take advantage of such theory. To properly analyse the running time of our three algorithms, we compare them against two existing algorithms from the literature, and against using multiple threads within our chosen IP solver, CPLEX. This survey of six different parallel algorithms, the first of its kind, demonstrates the advantages of parallel computing. Across all problem types tested, our new algorithms are on par with existing algorithms on smaller cases and massively outperform the competition on larger cases. These new algorithms, and freely available implementations, allows the investigation of complex MOIP problems with four or more objectives.
rate research
Read More
This paper introduces a new method of partitioning the solution space of a multi-objective optimisation problem for parallel processing, called Efficient Projection Partitioning. This method projects solutions down into a single dimension, greatly reducing the cost of partitioning the search space. We test EPP on a variety of randomly generated multi-objective combinatorial optimisation problems. The results are compared with the state of the art in parallel partitioning, and we show that in all scenarios tested, our new algorithm performs significantly better. Our proposed method allows the generation of non-dominated sets of larger problems with more decision variables or objective functions through the use of highly parallel computational infrastructure. Source code is provided to allow others to utilise, build upon and improve the algorithm
We propose a dual dynamic integer programming (DDIP) framework for solving multi-scale mixed-integer model predictive control (MPC) problems. Such problems arise in applications that involve long horizons and/or fine temporal discretizations as well as mixed-integer states and controls (e.g., scheduling logic and discrete actuators). The approach uses a nested cutting-plane scheme that performs forward and backward sweeps along the time horizon to adaptively approximate cost-to-go functions. The DDIP scheme proposed can handle general MPC formulations with mixed-integer controls and states and can perform forward-backward sweeps over block time partitions. We demonstrate the performance of the proposed scheme by solving mixed-integer MPC problems that arise in the scheduling of central heating, ventilation, and air-conditioning (HVAC) plants. We show that the proposed scheme is scalable and dramatically outperforms state-of-the-art mixed-integer solvers.
We address the problem of partitioning a vertex-weighted connected graph into $k$ connected subgraphs that have similar weights, for a fixed integer $kgeq 2$. This problem, known as the emph{balanced connected $k$-partition problem} ($BCP_k$), is defined as follows. Given a connected graph $G$ with nonnegative weights on the vertices, find a partition ${V_i}_{i=1}^k$ of $V(G)$ such that each class $V_i$ induces a connected subgraph of $G$, and the weight of a class with the minimum weight is as large as possible. It is known that $BCP_k$ is $NP$-hard even on bipartite graphs and on interval graphs. It has been largely investigated under different approaches and perspectives. On the practical side, $BCP_k$ is used to model many applications arising in police patrolling, image processing, cluster analysis, operating systems and robotics. We propose three integer linear programming formulations for the balanced connected $k$-partition problem. The first one contains only binary variables and a potentially large number of constraints that are separable in polynomial time. Some polyhedral results on this formulation, when all vertices have unit weight, are also presented. The other formulations are based on flows and have a polynomial number of constraints and variables. Preliminary computational experiments have shown that the proposed formulations outperform the other formulations presented in the literature.
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method --- which is valid only in the case of continuous uncertainty --- is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.
We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron per block and the ``aggregated polyhedron. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
