# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

39 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
91 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)$ ...
128 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
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,278
117 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 ...
• 8,737
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 ...
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 ...
914 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
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 ...
103 views

• 29
214 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. ...
57 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 ...
464 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,831
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
263 views

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 ...
70 views

• 235
1 vote
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 ...
56 views

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 ...
71 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
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 ...
67 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 ...