# Tag Info

## Hot answers tagged combinatorial-optimization

12

To answer your question, it is good to have in mind the following concepts: Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex combination of the extreme points of the polygon defined by the constraints of the problem. Column generation : once this change of variables has been done, you ...

10

This is a variant of the University Course Scheduling problem (e.g. this one). Interestingly, writing software to solve this was Bill Gates' first gig when he was still a student. There is a lot of software around for this type of problem (just google course scheduling software). It's also very similar to sports scheduling (e.g. how the NFL schedule is ...

10

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...

9

Being a good or bad approach will depend on several factors, for example: the size of the instances time available to find a solution (this tends to be an important matter in vehicle routing applications) computing power what level of solution quality qualifies as good enough See this work by Yu, Nagarajan and Shen on the minimum makespan VRP with ...

8

You can solve the problem via integer linear programming as follows. For each size $s\in\{3,4,5\}$, let $n_s$ be the number of blocks of size $s$ to place. For each cell $(i,j)$ and each size $s \in \{3,4,5\}$, let binary variable $x_{i,j,s}$ indicate whether $(i,j)$ is the top left corner of a block of size $s$. For each cell $(i,j)$, let $B_{i,j}$ be the ...

7

You can omit $v$, $w$, and $z$ and instead directly link $u$ and $x$ as follows: \begin{align} -(1 - u_{ikj}) \le x_{ij} + x_{kj} - 1 &\le 1 - u_{ikj} \tag1 \\ -u_{ikj} \le x_{ij} - x_{kj} &\le u_{ikj} \tag2 \end{align} Constraint $(1)$ enforces $u_{ikj} = 1 \implies x_{ij} + x_{kj} = 1$ (equivalently, $x_{ij} \ne x_{kj}$). Constraint $(2)$ enforces $... 7 Let$d_i$be the demand for customer$i\in N$, let$V=\{1,\dots,K\}$be the set of vehicles, and let$P$be the set of columns, where each column corresponds to a feasible subtour starting from the depot, with arc variables$x_{i,j}$and node variables$y_i$. Let$z$be the makespan. The master problem over$z$and$\lambda$is as follows, with dual ... 7 This reminds me of the Progressive Party Problem, for which an elegant MIP formulation is given here: Erwin Kalvelagen, On solving the progressive party problem as a MIP. Computers & Operations Research 30 (2003) 1713–1726 An AMPL implementation of this formulation, and an alternative approach for getting a good solution faster, are described in my ... 7 Even though knapsack problems are relatively easy to solve in practice, there does not exist a polynomial-time algorithm to solve even the standard knapsack problem, unless$\mathcal{P}=\mathcal{NP}$. The knapsack problem can be solved in pseudo-polynomial time$\mathcal{O}(nC)$. Even when the input length (=number of digits describing the problem) is small, ... 6 The best paper we ever read about the implementation of heuristics for the TSP is "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic" by Keld Helsgaun. This 70-page report is really a masterpiece in the field. You can find more details here about Helgaun's research on TSP, and here for extensions to VRP. You can also ... 6 As wsg mentioned in a comment, your problem is related to the Social Golfer problem. You can find references on the web and in the OR literature under this naming. For example, have a look at this webpage or this one. This problem has tight connections to Latin square, Kirkman's schoolgirl problem, and more generally combinatorial design problems. This is a ... 6 In addition to the hyperheuristics mentioned by batwing, you can look for the broader topic of (automatic) algorithm selection and configuration. Generally speaking, algorithm selection is the task of choosing one algorithm among a set of possible ones, based on some information (features) about the problem and instance you want to solve. Configuration is ... 6 With a low to moderate number of distinct weights, this is a variant of a transportation problem. An appropriate model would be$\begin{alignat*}{1} \min\ \ & w_{\max}\\ \text{s.t.}\ \ \ & \sum_{j=1}^{J}x_{ij}=n_{i}\ \ \ i=1,\dots,I\\ & \sum_{i=1}^{I}a_{i}x_{ij}=w_{j}\ \ \ j=1,\dots,J\\ & w_{j}\le w_{\max}\ \ \ j=1,\dots,J\\ & 0\le ... 5 VRPy (v0.3.0) now supports this option : all you have to do is set the minimize_global_span option to True when instantiating the VehicleRoutingProblem object: prob = VehicleRoutingProblem(G, num_vehicles=2, minimize_global_span=True) prob.solve() Of course, your graphG$has to be well defined in the first place. The formulation proposed by @RobPratt is ... 5 If I understood your problem correctly, then the only difference with the initial version (without the train) is that the time function is not additive. For example, lets say the train passes through node$j$at (given) time$t_j$, and you are computing a path$p$whose last node is$i$. The total accumulated time on this path is denoted by$\tau_p(i)$.$\...

5

Note that (as is asserted in the cited tutorial): The cost of a route is the addition of the arcs that compose it: $c_k = \sum_{(v_i, v_j) \in A} b_{ijk}c_{ij}$ Relate $a_{ik}$ ($r_k$ visits customer $i$) with $b_{ijk}$ (route $k$ uses arc $(i,j)$): $a_{ik} = \sum_{v_j \in V: (v_i, v_j) \in A} b_{ijk}$ And the conditions (22) and (23) are equivalent ...

5

I am pretty sure the answer is NO! Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$. The optimal LP relaxation $S_{hi}$ is taking all nodes with value $\frac{1}{2}$. Adding the extra odd circle constraints one can get an optimal solution $... 5 This sounds like the Covering Salesman Problem, introduced in 1989. 5 SCIP used to be a bit challenging to set up with PYOMO as we needed to build the ASL interface. It's been a few years so I don't know if that's changed, but you can find a relevant discussion here. What might be easier would be to use Couenne, which is a deterministic global optimisation solver for MINLP and works out of the box with PYOMO. If you are a ... 5 You can use SCIP with PYOMO easily. My way is: At first, use an executable SCIP version, it is available for the 7.0 version. After then giving the path of the executable to PYOMO, such as: solver = SolverFactory('scip', executable="./scip") It works. But I use BONMIN in same way. 5 I think you may be interested in the topic of hyper-heuristics. Very loosely, given a bunch of local search operators for a problem, the idea is to combine those local search operators to form a short chains. Each chain is a sequence of the local search operators, and so each chain itself acts like a heuristic for the original problem. Typically, the work in ... 5 In order to maximize X+Y, you can minimize -(X+Y), and then negate the optimal objective value. The optimal X and Y will also be optimal for maximize X+Y. Similarly, to maximize Sum (LC + MD), you can minimize -Sum (LC + MD), and then negate the optimal objective value. 5 Neither. You should delete$d_{u,c}$from the model whenever$\omega_{u,c} < t_\min$. 5 It is NP-hard: Bruno Codenotti, Ivan Gerace, Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra and its Applications 285 (1-3), pages 123-142, 1998, pdf Other Cayley graphs have been studied by Chris Godsil and Brendan Rooney in the paper Hardness of Computing Clique Number and Chromatic ... 5 You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers. Here's an alternative MIQP formulation that does not double the number of workers. Let binary decision variable$x_{i,j}$indicate whether job$i$is assigned to worker$j$. The problem ... 4 in CPLEX with all APIs you can use logical constraints that will help you to model that: dvar int x; dvar int y; dvar int z; dvar int t; subject to { (x==y) => (z!=t); } in OPL for instance. But you can write the same with C++, java, python ... 4 Here is a MILP formulation, in case you did something different. Let binary variable$F_j$indicate whether subset$j$is chosen. Let binary variable$T_i$indicate whether item$i$appears in two or more of the chosen subsets. The problem is to minimize$\sum_i T_isubject to: \begin{align} \sum_j F_j &= 140 \tag1 \\ \sum_j M_{i,j} F_j - 1 &\le ... 4 In my experience when solving Vehicle Routing with time windows in the industry, with one case handling 50 000+ vehicles and 100 000+ visits per day as well as many other cases with lower numbers, all running in production, I notice that: The problem is often (un)naturally partitioned, due to Conway's law. In the 50K+ vehicles case, each vehicle and visit ... 4 (1) This is correct, and there's nothing wrong with having a whole lot of constraints that each requirex_6 = x_j$for some$j$. But if you know in advance that these variables will all equal each other, why not just define a new variable that equals all of them? That is, create a variable$x_{6-10}$that equals$x_6$through$x_{10}\$ and use this variable ...

4

Many state-of-art real-world large-scale combinatorial optimization problems are based on heuristics that use some sort of local search in them. Although not stated directly as a QUBO, many of these local search moves are based on solving a QUBO (with no "tricks" of penalizing the constraints). For example in the Travelling Salesman Problem, the ...

Only top voted, non community-wiki answers of a minimum length are eligible