Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
47
questions with no upvoted or accepted answers
6
votes
0
answers
95
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
136
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
88
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,278
5
votes
0
answers
118
views
Materials or sample code for column generation book (GERAD 25th Anniversary Series)
As far as I know, one of the interesting resources to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
- 9,248
5
votes
0
answers
65
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
1k
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-...
- 390
4
votes
0
answers
65
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
105
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,133
3
votes
0
answers
73
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
221
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,278
3
votes
0
answers
138
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
145
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
127
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 ...
- 9,248
3
votes
0
answers
124
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 ...
- 529
3
votes
0
answers
77
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 ...
- 583
2
votes
2
answers
141
views
2D bin packing where some items must be packed in the same bin?
I am solving a 2D bin packing problem, however, there is an additional constraint where some items must be in the same bin. The problem is at industry scale (up to 1000 items and ~200 bins of ...
2
votes
0
answers
51
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 ...
- 529
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
64
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
235
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
69
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
521
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,741
2
votes
0
answers
37
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
302
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 ...
- 341
2
votes
0
answers
70
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 ...
- 341
1
vote
0
answers
31
views
Solve a combinatorial problem under nested cardinality constraints
I am trying to solve the following optimization problem
\begin{align}
\underset{S_t \in \mathbb{S}}{\min} ~ \sum\limits_{S \subset S_t} f(S) \\
s.t. |S| = M,
\end{align}
where $\mathbb{S} := \{S \...
- 33
1
vote
1
answer
70
views
Coverage Path Planning Dilemma (Trade-Off)
I have encountered a dilemma while I was trying to model a certain problem. Here is the description of the problem:
Imagine a 2D square area divided into square grids/cells. We have an agent (robot) ...
- 11
1
vote
0
answers
44
views
How to decompose a specific constraint in the sub-problem?
Suppose there is a specific constraint as follows to impose the precedence relation between the tasks:
$$ \sum_{m \in M} m.x_{j,m} \leq \sum_{m \in M} m.x_{k,m} \quad \forall (j,k) \in T $$
I want to ...
- 9,248
1
vote
0
answers
21
views
Building a CapEx portfolio using mathematical optimization
Let's say you have a set of potential capital projects $C$, each defined by an up-front investment $c_i$ and random payoff (say, NPV) $P_i(\omega)$, where $\omega \in \Omega$ is a point in a sample ...
- 111
1
vote
0
answers
44
views
What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?
We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
- 819
1
vote
1
answer
164
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 ...
- 113
1
vote
0
answers
62
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
60
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
37
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
174
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}...
- 245
1
vote
0
answers
74
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
84
views
Linear sum assignment, but with ranked assignments?
Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix:
...
- 1
0
votes
0
answers
68
views
Shift roster (calendar) - mathematic optimization algorithm
I have question about heuristic searching problem - I need to plan shift roster for workers.
My solution is to use some bio-inspired algorithm. My implementation is:
I created list of timeframes (...
0
votes
0
answers
66
views
Is it possible to transform MIQP into MILP without introducing new variable?
I have a QP optimization problem in the form
$$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$
here $\bf Q$ is a symmetric matrix.
$\bf x$ is the optimization variable, and it is binary.
Is there a way to ...
- 2,397
0
votes
0
answers
53
views
Local Branching in Branch-And-Price
Is it somehow possible to apply local branching in branch-and-price?
In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution.
...
- 1
0
votes
0
answers
62
views
How to model constraints without introducing additional variables?
I have a binary variable $\bf x$ of size $12\times 1$, such as ${\bf x} =[x_1\hspace{1mm} x_2\hspace{1mm} x_3\hspace{1mm} x_4\hspace{1mm} x_5\hspace{1mm} x_6\hspace{1mm} x_7\hspace{1mm} x_8\hspace{1mm}...
- 2,397
0
votes
0
answers
64
views
Shopping Basket Deal Optimization
I am looking for guidance on a solution to the problem of picking the best special offers that can be applied to a given basket of items.
In the system, a special offer has N collections of qualifying ...
0
votes
0
answers
77
views
Cost function value of relaxed ILP after rounding is less than or equal to the optimal one
I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation.
In the ILP I have two decision ...
- 1
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
182
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
549
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