Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
142
questions
9
votes
3answers
2k views
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
Are Metaheuristics and Evolutionary Algorithms the "Gold Standard" for the Traveling Salesman Problem?
I am interested in learning more about how we have been able to solve the (famous) ...
4
votes
1answer
407 views
Is the Travelling Salesman Problem Considered as "Gradient Free Optimization"?
I was thinking about the Traveling Salesman Problem the other day - for such types of discrete combinatorial optimization problems, do they have a "loss function"?
It seems that there is ...
2
votes
1answer
43 views
Master Problem Infeasible after Iterations of Unbounded Sub Problem (Generic Benders Decomposition in non Stochastic MILP)
I am dealing with a large problem of MILP problem and interested to apply Benders Decomposition. I have already check the original problem and it was feasible to run in large number of computation ...
22
votes
5answers
4k views
Why is open source operations research software so far behind open source statistics and machine learning software?
Like many who participate in this site, I work on projects in both operations research (OR) and statistics/machine learning (ML). The different states of open source software in these fields are often ...
6
votes
3answers
1k views
Solving Logic puzzles through optimization
I have the following "logic puzzle" (I think this is considered as a "scheduling problem"):
In this problem, there are 5 basketball players - provided some clues about their ...
3
votes
2answers
167 views
How to perform clustering of two different sets of entities?
I need to perform clustering of two different entities. Lets say we have transmitters and users.
The relation between a transmitters and user is defined by a weight, for example, the weight between ...
4
votes
1answer
118 views
Adding a group constraint to binary decision variables
I have a problem where I have N binary decision variables where each one of them belongs to a group (Where the number of groups G is less than N) and I have to choose a subset of them to maximize some ...
1
vote
0answers
42 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 ...
2
votes
1answer
94 views
Number of paths in asymmetric capacitated vehicle routing problem
This seems like a natural question, but I was not able to find an answer. My question is this. Consider a CVRP where $n$ customers have to be serviced by $m$ vehicles on any given day. All the ...
2
votes
0answers
105 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, ...
2
votes
2answers
67 views
Change the objective function formula change the complexity of a linear program?
I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with ...
3
votes
0answers
88 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 ...
6
votes
3answers
211 views
Budgeted max cut heuristic
I am looking for a heuristic that solves a budgeted variant of the max cut problem.
Given a graph $G = (V, E)$, if the original problem is to find a partition of $V$ into two subsets $A$ and $B$ where ...
14
votes
3answers
2k views
Why does the design of heuristics require considerable domain knowledge?
I am from a machine learning (ML) background and am interested in how ML is applied to Combinatorial Optimisation. As such, as I have been reading around the area and have come across the statement ...
2
votes
2answers
93 views
How to prove that optimizing each component of a system separately gives suboptimal result?
The black-box system shown below has 3 components.
They run sequentially to generate a final output from the input. Each component has its own parameters to optimize for better intermediate results (...
3
votes
1answer
190 views
Discrete problems versus Combinatorial problems
I have seen one explanation about the difference between discrete and combinatorial optimization problems in such a way that "all combinatorial optimization problems are also discrete ...
2
votes
0answers
61 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 ...
3
votes
1answer
62 views
How to know if a combinatorial optimization problem is linear or not?
I want to know if a combinatorial problem like the knapsack problem is linear or not. And how do we know if a given problem is convex or not?
-1
votes
1answer
61 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?
2
votes
0answers
101 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 ...
2
votes
1answer
98 views
Adapting a cluster-first-route-second approach for VRP with heterogenous fleet
I have the following data:
A fixed depot/facility location
Dropping points with demands
List of available vehicles (heterogeneous fleets)
What I am trying to do is, given the list of vehicles and ...
4
votes
1answer
298 views
Complexity of navigation with google maps
I was wondering what complexity a simple start-destination task in a routing software would have. Knowing the shortest path problem, it should be in P. Is there anything I am missing?
1
vote
0answers
46 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 ...
4
votes
1answer
92 views
Lot-sizing problem variant
I have a the following optimization problem: I have mandates,(e,g. to deliver 100 tonnes of products) that I need to schedule its delivery during the month (day 2: deliver 40 Tonnes, day 15: deliver ...
3
votes
1answer
146 views
Bin Packing with CP Solver
[ [0,5],
[0,4],
[1,6],
[2,4],
[3,6],
[3,2],
[4,5],
[5,5],
[6,4],
[7,3],
[8,2],
[8,3],
[9,5],
[10,3]]
...
3
votes
0answers
113 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 ...
5
votes
4answers
427 views
Solving Capacitated VRP with multiple various sized vehicles
I am looking to form a Capacitated VRP problem like this:
I have 40,000 dropping locations with Demands of each point available
I have 5-6 types of vehicles available with different capacities and ...
5
votes
2answers
498 views
Combinatorial optimization, implementation needed
I have k sets of items. I want to choose n items from each set, $n \cdot k$ items total.
I would like to choose the $n \cdot k$ items under some optimization criterion, e.g. that the sum of the $\...
0
votes
0answers
57 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 \...
4
votes
3answers
280 views
Is there a Bin Packing Library similar to TSPLIB?
I have concluded there is not, or if there is it's not openly published?
I am trying to identify if there are "top solutions/formulations" for the 3d BPP. Looking to apply in a parcel ...
4
votes
1answer
188 views
Why are the bounds 3 and 6 instead of 7, in this binary expansion of a slack variable in this QUBO problem?
I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf
One of the steps is to transform the inequalities ...
3
votes
0answers
62 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 ...
7
votes
1answer
95 views
Terrain Ruggedness Index for optimization problem
If I want to study the smoothness of the energy landscape of a cost function, is there any metric similar to Terrain Ruggedness Index used in geology?
1
vote
2answers
162 views
Combinatorial Optimization Problem using IBM ILOG CPLEX
Consider the combinatorial optimization problem described as below.
Let $D=(V,A)$ be a directed graph with $V$ the set of vertices and $A$ the set of arcs, i.e., $A=\{(i,j)\mid i,j\in V\}$. On each ...
2
votes
1answer
67 views
Finding the minimum of a group of timings
I would like to seek some modeling advice on the following:
Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two ...
6
votes
0answers
97 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 ...
6
votes
2answers
136 views
MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?
I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019.
It's a problem about minimizing a sum of terms that are ...
2
votes
1answer
285 views
Efficient solver for multiway number partitioning
I am interested in the following problem.
The input is a set of $n$ integers, and a fixed integer $k$.
The required output is a partitioning of the integers into $k$ subsets, such that the smallest ...
4
votes
1answer
78 views
How to prove pseudo-convexity of a discrete function?
Given a general function $f:\Bbb Z\to\Bbb R$ is there a simple way to verify whether $f(x)$ is pseudo-convex or not?
4
votes
1answer
197 views
Assignment problem with batching costs
I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
2
votes
1answer
46 views
How to define a stationary point of the MINLP problem?
As we all know, KKT point and stationary point are well defined when the optimization variables are continuous in the problem.
Now, I want to know whether there exist some special points except for ...
6
votes
2answers
392 views
0 1 solution of linear programming problem with only equality constraints
I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
3
votes
1answer
363 views
Implementing benders decomposition using Lazy and User cuts callback of Cplex
I am trying to implement benders decomposition for a simple fixed charge transportation problem for the purpose of learning. I implemented the classic Benders decomposition successfully by adding ...
1
vote
1answer
146 views
Minimum vertex cover and linear programming 2
This is a modified version of the algorithm that I have proposed here.
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for ...
4
votes
1answer
133 views
How to improve the solution in ALNS metaheuristic
I am solving the CVRP with Adaptive Large Neighborhood Search (ALNS) .
I used the following construction operators: GreedyInsertion and ...
3
votes
2answers
354 views
A relaxed version of job shop scheduling
I am working on a formulation for a problem that seems similar to the bin packing problem. My problem variables include items that are to be placed in bins, special events that are conditionally ...
7
votes
4answers
1k views
What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?
I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity.
I also have a fixed number of objects each of which ...
4
votes
1answer
75 views
Does anybody know the complexity of finding a maximum clique in circulant graphs?
I would be interested in knowing if finding a maximum clique in circulant graphs is NP-hard? Does anybody have any pointers or papers to suggest?
2
votes
2answers
102 views
Should I process the data or add a new constraint to achieve the target?
I have an MILP as below
$\begin{equation}
\begin{array}{*{35}{l}}
\underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\
\text{}\text{subject to }\text{ C1:}...
7
votes
1answer
199 views
Square packing variant
I saw the following problem and was looking for references about the problem. The problem is stated as
“The green field is the empty area, the dark green 2x2 blocks are
trees and the grey area is the ...
