# Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

47 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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)$ ...
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
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
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
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 ...
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
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 ...
105 views

• 29
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. ...
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 ...
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
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
302 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

• 33
1 vote
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) ...
1 vote
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
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
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
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
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
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
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
174 views

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 ... 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. ... 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
64 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 ...
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
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 ...