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
6 votes
0 answers
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)$ ...
Jin Kazama's user avatar
6 votes
0 answers
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 ...
Surpass2019's user avatar
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 ...
Nike Dattani's user avatar
  • 1,278
5 votes
0 answers
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 ...
A.Omidi's user avatar
  • 8,737
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 ...
winterwyvern's user avatar
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 ...
Lorenzo Trapani's user avatar
4 votes
0 answers
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-...
Pia MiA's user avatar
  • 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 ...
user134977's user avatar
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 \...
Alberto Santini's user avatar
3 votes
0 answers
67 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 ...
Parseval's user avatar
  • 207
3 votes
0 answers
196 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 ...
Nike Dattani's user avatar
  • 1,278
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, ...
MAJID majid's user avatar
3 votes
0 answers
139 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 ...
asdf's user avatar
  • 105
3 votes
0 answers
121 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 ...
A.Omidi's user avatar
  • 8,737
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 ...
Shibaprasad's user avatar
3 votes
0 answers
76 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 ...
OR Junior's user avatar
  • 521
2 votes
2 answers
86 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 ...
OR Researcher's user avatar
2 votes
0 answers
49 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 ...
Shibaprasad's user avatar
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 ...
Quavo's user avatar
  • 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 \...
Yuki's user avatar
  • 29
2 votes
0 answers
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. ...
Ozan Aksu's user avatar
2 votes
0 answers
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 ...
Luo ArChen's user avatar
2 votes
0 answers
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/...
stats_noob's user avatar
  • 1,831
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 ...
David's user avatar
  • 333
2 votes
0 answers
263 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 ...
Amogh Bhosekar's user avatar
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 ...
Amogh Bhosekar's user avatar
1 vote
0 answers
41 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 ...
JKHA's user avatar
  • 679
1 vote
1 answer
118 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 ...
CHE's user avatar
  • 113
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 ...
adg's user avatar
  • 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 ...
Surpass2019's user avatar
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 ...
Amedeo's user avatar
  • 443
1 vote
0 answers
169 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}...
stevGates's user avatar
  • 235
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 ...
mcfenelon's user avatar
0 votes
0 answers
56 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 ...
Robert Snipe's user avatar
0 votes
0 answers
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 ...
LyLa's user avatar
  • 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 ...
Yichuan_Sun's user avatar
0 votes
0 answers
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 ...
Jai s's user avatar
  • 1
0 votes
0 answers
161 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 \...
Angelo Aliano Filho's user avatar
-1 votes
1 answer
483 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?
MAJID majid's user avatar