Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
120
questions
1
vote
0answers
44 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
89 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
137 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]]
...
1
vote
0answers
85 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
405 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
477 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
49 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
268 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
154 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
58 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
93 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
97 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
64 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 ...
7
votes
0answers
93 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 ...
5
votes
2answers
93 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
183 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
72 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
187 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
44 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
317 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
256 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
61 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
120 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
310 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
74 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
100 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
194 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 ...
4
votes
1answer
35 views
Finding an augmenting path or cycle in weighted graph
Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
2
votes
0answers
68 views
Materials or sample code for column generation book (GERAD 25th Anniversary Series)
As far as I know, one of the interesting resource to learn the basic concept of the decomposition methods is column generation book (GERAD 25th Anniversary Series), which has been mentioned in some ...
4
votes
1answer
113 views
k -MST problem based on Miller-Tucker-Zemlin subtour elimination constraints
Where can I find the formulation of the $k$-MST ($k$-minimum spanning tree) problem as (mixed) integer linear program
based on Miller-Tucker-Zemlin subtour elimination constraints (MTZ)?
4
votes
1answer
69 views
Does the facility layout problem with zero and one matrices have a specific name?
I have an facility layout problem where the flow between any two departments is either zero or one. Also the distance between each location pair has the same nature (zero or one). I am curious whether ...
-4
votes
1answer
71 views
How to change a function from Min(F(x)) to -Max(-F(x))?
I have not a good knowledge in math field, I am working on multi objective functions, and I have two maximization functions, and one minimize function, where:
Max (X,Y) = X+Y
Max (L,M) = Sum (LC + MD)...
5
votes
1answer
164 views
0-1 knapsack with non-linear objective function
There's efficient algorithms for solving the 0-1 knapsack problems when the objective function is just a sum of profits. I am dealing with the following problem with non-linear objective function:
$$\...
2
votes
2answers
67 views
Parallel scheduling with precedence constraints and variable job length
I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
3
votes
0answers
71 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
1answer
103 views
What are the flow based formulations?
What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?
Also, the same question for the time staged ...
1
vote
0answers
27 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 ...
2
votes
1answer
68 views
Maximum bipartite matching with breakpoints in edge weight function
I am looking for an analogy to the problem I am facing or better yet a paper or even code.
I have:
Nodes from set A and B.
Edges are from a single A to many B.
I am framing a max bipartite matching ...
1
vote
0answers
65 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}...
1
vote
0answers
98 views
How to develop a vehicle routing optimization package? [closed]
I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 ...
7
votes
4answers
402 views
Learning local search operator selection
I'm just reading [1]. The authors use a neural network to solve capacitated vehicle routing problems through iterative generation of tours by solving a price-collecting traveling salesman problem in ...
3
votes
2answers
108 views
Relaxation and complexity of two formulations
I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
0
votes
1answer
101 views
What kind of job shop scheduling problem is this and how do I solve it?
I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem.
But I would like to get some input on what kind of job shop scheduling problem it is and ...
7
votes
2answers
875 views
Can I use 'SCIP' solver for PYOMO?
I have an MINLP problem to solve where I was initially using 'ipopt' solver but the solution was not sticking to 'binary/boolean/integer' domain type for a variable. I am not sure which free solver ...
6
votes
1answer
140 views
Literature on "simcity-like" problems
As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.
I have a set of "buildings" that I want to place on a small 2d ...
1
vote
1answer
78 views
A discrete location problem
I have a discrete optimization problem in which there are some predetermined nodes in the set A. a vehicle must visit them as the traveling salesman problem. there are some other nodes in the set B ...
23
votes
3answers
3k views
Combinatorial problem in my daughter’s class
In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in ...
3
votes
0answers
83 views
Best known results on the flexible jobshop benchmarks
Is there a website that compiles the best known results on the flexible jobshop problem ?
I know there was a blog post/article by Quintiq, a (deleted) blog post on CP Optimizer, some more recent ...
2
votes
2answers
190 views
implementation of heuristics using C++ to solve operations research problems
can anyone suggest some good books with the implementation of heuristics and matheuristics using C++ to solve operations research problems especially routing problems such as TSP and VRP. also, I need ...