Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
98
questions
4
votes
1answer
86 views
How to improve the solution in ALNS metaheuristic
I am solving the CVRP with Adaptive Large Neighborhood Search (ALNS) .
I used the following construction operators: ...
3
votes
2answers
126 views
A relaxed version of job shop scheduling
I am working on a formulation for a problem that seems similar to the bin packing problem. My problem variables include items that are to be placed in bins, special events that are conditionally ...
7
votes
4answers
1k views
What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?
I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity.
I also have a fixed number of objects each of which ...
4
votes
1answer
71 views
Does anybody know the complexity of finding a maximum clique in circulant graphs?
I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
1
vote
2answers
98 views
Should I process the data or add a new constraint to achieve the target?
I have an MILP as below
$\begin{equation}
\begin{array}{*{35}{l}}
\underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\
\text{}\text{subject to }\text{ C1:}...
6
votes
1answer
186 views
Square packing variant
I saw the following problem and was looking for references about the problem. The problem is stated as
“The green field is the empty area, the dark green 2x2 blocks are
trees and the grey area is the ...
3
votes
1answer
29 views
Finding an augmenting path or cycle in weighted graph
Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
2
votes
0answers
59 views
Materials or sample code for column generation book (GERAD 25th Anniversary Series)
As far as I know, one of the interesting resource to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
4
votes
1answer
95 views
k -MST problem based on Miller-Tucker-Zemlin subtour elimination constraints
Where can I find the formulation of the $k$-MST ($k$-minimum spanning tree) problem as (mixed) integer linear program
based on Miller-Tucker-Zemlin subtour elimination constraints (MTZ)?
4
votes
1answer
62 views
Does the facility layout problem with zero and one matrices have a specific name?
I have an facility layout problem where the flow between any two departments is either zero or one. Also the distance between each location pair has the same nature (zero or one). I am curious whether ...
-4
votes
1answer
67 views
How to change a function from Min(F(x)) to -Max(-F(x))?
I have not a good knowledge in math field, I am working on multi objective functions, and I have two maximization functions, and one minimize function, where:
Max (X,Y) = X+Y
Max (L,M) = Sum (LC + MD)...
5
votes
1answer
117 views
0-1 knapsack with non-linear objective function
There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function:
$$\...
2
votes
2answers
61 views
Parallel scheduling with precedence constraints and variable job length
I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
3
votes
0answers
58 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
1answer
91 views
What are the flow based formulations?
What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?
Also, the same question for the time staged ...
1
vote
0answers
26 views
MILP formualtion for Two-level minimum dominating set (MDS) problem?
I'm working on an optimization problem which is kind of finding the minimum dominating set (MDS) or the minimum vertex set (MVS) in an undirected graph. given the MILP formulation for both problems, I ...
2
votes
1answer
65 views
Maximum bipartite matching with breakpoints in edge weight function
I am looking for an analogy to the problem I am facing or better yet a paper or even code.
I have:
Nodes from set A and B.
Edges are from a single A to many B.
I am framing a max bipartite matching ...
1
vote
0answers
61 views
Can I combine two objective functions if they have a relation between them?
I will use a meta-heuristic algorithm, to maximize the following objective functions:
Objective function 1 $=\sum\limits_{r=1}^{M} \sum\limits_{s=r+1}^{M} \sum\limits_{j=r+1}^{N} (r_{rj}w_j - r_{sj}...
1
vote
0answers
95 views
How to develop a vehicle routing optimization package? [closed]
I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 ...
6
votes
3answers
302 views
Learning local search operator selection
I'm just reading [1]. The authors use a neural network to solve capacitated vehicle routing problems through iterative generation of tours by solving a price-collecting traveling salesman problem in ...
3
votes
2answers
101 views
Relaxation and complexity of two formulations
I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
1
vote
1answer
77 views
What kind of job shop scheduling problem is this and how do I solve it?
I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem.
But I would like to get some input on what kind of job shop scheduling problem it is and ...
7
votes
2answers
394 views
Can I use 'SCIP' solver for PYOMO?
I have an MINLP problem to solve where I was initially using 'ipopt' solver but the solution was not sticking to 'binary/boolean/integer' domain type for a variable. I am not sure which free solver ...
6
votes
1answer
131 views
Literature on “simcity-like” problems
As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.
I have a set of "buildings" that I want to place on a small 2d ...
1
vote
1answer
70 views
A discrete location problem
I have a discrete optimization problem in which there are some predetermined nodes in the set A. a vehicle must visit them as the traveling salesman problem. there are some other nodes in the set B ...
23
votes
3answers
3k views
Combinatorial problem in my daughter’s class
In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in ...
4
votes
0answers
71 views
Best known results on the flexible jobshop benchmarks
Is there a website that compiles the best known results on the flexible jobshop problem ?
I know there was a blog post/article by Quintiq, a (deleted) blog post on CP Optimizer, some more recent ...
2
votes
2answers
169 views
implementation of heuristics using C++ to solve operations research problems
can anyone suggest some good books with the implementation of heuristics and matheuristics using C++ to solve operations research problems especially routing problems such as TSP and VRP. also, I need ...
2
votes
1answer
60 views
distance specific constraint
I have some points with determined coordinates $(a_i,b_i)$. A vehicle can move between these points based on rectangular distance. In more detail, we consider that the path between points is an ...
4
votes
1answer
105 views
How to represent time window as constraint in a vehicle routing problem
Hi I am trying to solve a vehicle routing problem using Tabu search, I have successfully completed implementation of constraints for CVRP by giving penalties to objective function , how do I implement ...
6
votes
2answers
366 views
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven'...
6
votes
1answer
152 views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
1
vote
0answers
69 views
How to combine wires into a cable maximizing cable length while minimizing waste?
A customer brought us this problem and we're looking for ideas to help them. It seems to be a flavor of cutting-stock but without the demand profile.
They have varied length spools of different types ...
4
votes
1answer
156 views
Column Generation algorithm
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
5
votes
0answers
78 views
Column generation approach for CVRP
I want to use a column generation based heuristic to solve a capacitated Vehicle Routing Problem. I know the basics of the algorithm but I don't have much experience in coding. is there any code about ...
3
votes
1answer
104 views
A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet
I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
5
votes
1answer
199 views
Column Generation algorithm for vehicle routing problem
I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
4
votes
2answers
70 views
How to decide between a inaccurate system and a accurate system with capacity constraints to do a stream of jobs
Let's say you have a list of at most N Jobs to be done which are coming in a stream. There are two kinds of systems that can do the job:
System 1: A very fast system, which however, only does the job ...
3
votes
1answer
251 views
social network analysis - relations between people with weights
I asked this question on datascience.stackexchange but they directed me here.
I have a social network represented as a set of people $S$ and individual weights for each of person (weight is the cost ...
11
votes
1answer
139 views
Branch and Price algorithm is exact?
I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
5
votes
0answers
43 views
Mixing time exponent above threshold temperature for Glauber dynamics or annealing
It is well-known that the Glauber dynamics will converge in polynomial time to the Gibbs distribution for, say, the Ising model on a d-regular graph at high enough temperatures $T>T_c$. There are ...
5
votes
0answers
53 views
What is the generalization of the resource allocation problem I'm dealing with here?
I'm dealing with a problem as follows:
I have a finite set of money $m$ to spend over $r$ different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
5
votes
2answers
171 views
How to linearize a quadratic constraint to add it then via a callback function
Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound.
How can we linearize the term $x^2$?
Detailled problem:
Suppose that via a callback we compute a ...
4
votes
2answers
263 views
Combinatorial Optimization using AMPL
I want to solve the following integer programming problem using AMPL. The problem is the following (It was already asked on mathstackexchange.com, but I need to know how to solve it using AMPL):
Let $...
3
votes
1answer
173 views
Formulation of Assignment problem as integer programming
We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $\{P_1,\ldots,P_6\}$. We have three 3D printers $\{M_1,M_2,M_3\}$ which we can use ...
3
votes
2answers
135 views
Limit number of switches in employee scheduling problem
Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational ...
4
votes
0answers
93 views
Can this problem be modelled with a transformation from a known TSP with profits?
The profitable tour problem (PTP) is defined on a graph $G=(V,E)$ with $|V|=n$, where each vertex $i \in V$ has an associated prize $m_i \geq 0$ and each edge $e \in E$ has an associated cost $c_e \...
3
votes
0answers
49 views
What are the efficient ways to model this scheduling problem and ways to improve running time
There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
1
vote
3answers
210 views
Using big M values for a constraint
I want to enforce $x_{i,j}=x_{k,j}\implies z_i \neq z_k$ where $k = i-1$ so I used \begin{align}z_k + 1 - (x_{i,j} - x_{k,j})) \leq z_i \leq z_k - 1 - (x_{i,j} - x_{k,j})\quad\text{for each $j$}\end{...
2
votes
1answer
168 views
Does this problem fall into any common problem definition…Knapsack maybe?
I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
