Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
36
questions with no upvoted or accepted answers
6
votes
0
answers
89
views
Graph coloring problem while counting cliques
Let $G$ be a graph with a set of nodes $V$ and a set of edges $E$.
Let $G'$ be a graph with the same set of nodes $V$ but a second set of edges $E'$.
For a set of nodes $X\subset V$, we denote $f(X)$ ...
- 93
6
votes
0
answers
124
views
Characterization for total dual integrality
A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
- 137
6
votes
0
answers
85
views
What are the top three applications (in terms of number of citations) of the "reverse search" algorithm of David Avis?
I can see that this algorithm is quite popular, and that one of the original papers now has 820 citations on Google Scholar. However, what are the most highly cited applications of it?
If in Google ...
- 1,268
5
votes
0
answers
63
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 ...
- 51
5
votes
0
answers
124
views
Maximum eigenvalue across subsamples
I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$.
Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
4
votes
0
answers
770
views
Google-OR tools vs Pyomo and other commercial Solvers for solving a simple maximum flow problem
I have implemented a Pyomo model for solving maximum flow problem as a subroutine of an algorithm. However, the approach does not scale very well because Pyomo does not provide a very good way to re-...
- 392
4
votes
0
answers
62
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 ...
- 89
4
votes
0
answers
103
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 \...
- 2,073
3
votes
0
answers
66
views
How can I use a local search meta heuristic after completing construction heuristic?
I'm investigating how I can combine a construction heuristic and a local search metaheuristic to quickly solve Capacitated Split Delivery Veichle Routing Problem (CSDVRP). The construction heuristic ...
- 207
3
votes
0
answers
181
views
What can traditional graph cut methods do well, that deep learning cannot?
I have been fascinated by the rise and fall of graph cut algorithms in recent years, which I described in this question: Was there something specific that caused graph cuts to lose popularity in the ...
- 1,268
3
votes
0
answers
135
views
Are there hybrid metaheuristic-solvers to solve combinatorial optimization problems?
I have a problem which is formulating a linear program. To solve large instances I implement a metaheuristic to solve my problem. In my problem, I have two objective functions.
With my linear program, ...
- 335
3
votes
0
answers
135
views
Sources of Min-Cost Flow Models That Utilize Binary Variables for Transportation Networks
I am looking for articles that include min-cost flow models with binary variables for flow transportation like gas networks, traffic systems, heating systems. Is there any specific place(like OR ...
- 105
3
votes
0
answers
123
views
How to approach this Truck Utilisation problem?
The problem statement currently I have is very broad (or you can say very vague at the same time):
I have a number of dropping locations (Customer locations)
I have the location of the HUB
I have a ...
- 467
3
votes
0
answers
75
views
Linearization of a quadratic model, what is the difference while using gurobi?
I have a quadratic model of parking $N$ cars in $S$ separate lanes as follows. Each car has an arrival time and a departure time. Departure follow the last in first out principle. The objective is to ...
- 489
3
votes
0
answers
154
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,587
2
votes
0
answers
48
views
A 'capacitated' VRP model where the capacity constraint is the time
I am trying to model a capacitated VRP model where the capacity is defined by the time the vehicle is available.
What I have:
List of vehicles available and the time for which they are available
List ...
- 467
2
votes
0
answers
41
views
How best to compress a list of objective function evaluations in model-based optimization?
In Bayesian Optimization/other model-based numeric optimization methods, is there a useful way to compress or aggregate the observation history into a single value so you don't have to keep the result ...
- 29
2
votes
0
answers
62
views
Type of combinatorial problem
I'm looking at a problem that looks as follows:
$$
C = \sum_{i =1}^N\sum_{j<i} ( A_{ij} - B_{{P(i)P(j)}} )^2
$$
where $A$ and $B$ are square matrices and $P$ is a permutation matrix mapping all $i \...
- 29
2
votes
0
answers
203
views
Trying to add lazy constraints to traveling salesman problem
For a simple traveling salesman problem, I am trying to add the "miller-tucker-zemlin subtour elimination constraints" by using ILOLAZYCONSTRAINTCALLBACK.
...
- 29
2
votes
0
answers
49
views
Solving minimum bipartite matching with missing edges using Hungarian algorithm
I am interested in a minimum bipartite matching problem, where some edges are missing (i.e., not valid). An intuitive way to solve the problem is to add very large costs for these missing edges and ...
- 61
2
votes
0
answers
427
views
Relationship Between "Assignment Problems" and "Graphs"
I was reading the following Wikipedia Article on "Assignment Problems" that talks about the relationship between Assignment Problems and Graph Theory (https://en.wikipedia.org/wiki/...
- 1,821
2
votes
0
answers
34
views
Are the operations in the Graph Edit Distance problem of interest?
In the graph edit distance (GED), we are looking to find the cost of modifying one graph $G_1$ to another graph $G_2$. Is the sequence of operations that take $G_1$ from $G_2$ of interest in this ...
- 333
2
votes
0
answers
115
views
Mathematical model complexity Vs Time Complexity of the model
As far as I know, when we talk about the term of complexity, it referred to the time complexity of the model in which how long does it take to solve a specific mathematical program by a specific ...
- 8,390
2
votes
0
answers
254
views
About combinatorial Benders Cuts
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 331
2
votes
0
answers
91
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 ...
- 8,390
2
votes
0
answers
67
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 ...
- 331
1
vote
1
answer
100
views
Constraints to avoid disjointed solutions in a MIP
Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph.
A ...
- 111
1
vote
0
answers
59
views
Ordering a set in GAMS
I'm trying to solve a problem very similar to this one, where I'm trying to find an optimal order. How would I actually plug this into GAMS?
It gives out a single value rather than an ordering. I ...
- 11
1
vote
0
answers
59
views
Building blocks for unimodular matrices
I read Chapter 19.4 of Schrijver(1986) and get to know that every totally unimodular matrix can be produced by taking operations on network matrices and two certain matrices. I find that some paper ...
- 137
1
vote
0
answers
36
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 ...
- 443
1
vote
0
answers
164
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}...
- 235
1
vote
0
answers
72
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 ...
- 99
0
votes
0
answers
34
views
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)
How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.
Given a graph $G = \{V,E\}$,
we have a distance matrix (the ...
0
votes
0
answers
61
views
Loan Allocation Problem
I need help with the following use case:
Context :
Let's say there is a fintech "F", that helps with aggregating personal loans. Now, "F" can pool in customers who need a personal ...
- 1
0
votes
0
answers
153
views
Lower bound very bad. How to improve?
I have the following MILP:
\begin{alignat}{2}
\nonumber \mbox{minimize } \quad & \phi = \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} \left( D_{f \...
-1
votes
1
answer
436
views
How to interpret velocity computation in Particle Swarm Optimization?
Please in PSO metaheuristic when we calculate the velocity what is the advantage of using pBest?
- 335