Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
207
questions
1
vote
1
answer
62
views
Workforce scheduling MIP formulation
I am working on a large scale workforce scheduling problem with a large number of hard and soft constraints. The soft constraints are modeled as objectives with penalties for violating them. So my ...
3
votes
1
answer
162
views
Optimization challenges (currently active or soon to begin)
I am looking for an optimization challenge for an intern (such as ROADEF Challenge, Gecco competitions, or CEC competitions) active during summer 2023 (ideally July - September). Longer competitions ...
- 31
0
votes
0
answers
33
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 ...
0
votes
0
answers
48
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 ...
- 1
3
votes
3
answers
214
views
Equivalence between constraints in ILP
Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that
$$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$
If I wanted to express the equivalence between ...
- 133
0
votes
1
answer
62
views
Converting a piecewise function to a linear equation as a constraint
The value of one of the variable of my model (alpha_1) is given by a piecewise function. Each element of the piecewise depends on the value of some other binary decision variables (X1, x2, x3).
I'd ...
- 67
5
votes
6
answers
2k
views
How can I solve this algorithmic task in Python?
I am trying to solve this task:
There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. Second, data on ...
- 61
2
votes
3
answers
330
views
"Re-optimize" feature in Commercial Optimization
How does the "re-optimize" feature work in commercial optimization solvers such as IBM CPLEX and Gurobi? I recently experienced a considerable performance boost by re-solving a model with ...
- 392
2
votes
0
answers
44
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 ...
- 457
5
votes
1
answer
253
views
Optimize selection of metal sheets to keep in stock
I already asked this on stack overflow but just found this forum instead and figured it was more suited here. If this isn't allowed please feel free to tell me and I'll delete the post.
I am doing ...
- 53
4
votes
2
answers
557
views
Alternative way to restrict an employee to work on multiple jobs
Suppose I have a set of employee $E$ and set of jobs $J$ in a given time horizon $T$. I would like to make sure that no employee works on multiple jobs where each job $e\in E$ takes a certain amount ...
- 158
1
vote
1
answer
137
views
How to model this constraint? [duplicate]
I have a system with $C$ machine and $U$ users.
The decision variables are $d_{u,c}$ and ${\bf f}_{u,c}$ with $c=1,2,\cdots,C$ and $u=1,2,\cdots,U$, where
$$d_{u,c}\in\{0,1\}$$
$${\bf f}_{u,c}\in\...
- 2,191
6
votes
2
answers
137
views
Cover cuts for knapsack constraint with integer variables
It is known for knapsack type constraint $\sum_{i \in N} a_i x_i \leq b , x \in \{0,1\}$, we can generate the so called cover cuts that have the sum of coefficient in a set C greater than b. The cover ...
- 61
1
vote
2
answers
100
views
How do I approach this optimization problem?
I'm a software dev that's pretty new to OR and want to solve a specific problem I came across at my job. From what I've researched it is a variation of resource-constrained assignment problem, but ...
- 21
4
votes
0
answers
430
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
1
vote
1
answer
121
views
Further decomposing master problem in benders
In the benders decomposition, is it possible to decompose the master problem as follows and let the subproblem become the subproblem of the new subproblem? Let's say that we have the following problem....
user5245
2
votes
1
answer
164
views
Implementing subtour constraints to a VRP in python
Hi I have a problem related to the vehicle routing problem, where I want to implement the subtour constraints $\sum_{(i,j)\in S} x_{ij} \leq \lvert S \rvert - r(S), \: \forall S \subseteq N, S > 2$ ...
- 21
3
votes
1
answer
169
views
Assignment problem with mutually exclusive constraints has an integral polyhedron?
I have the following problem
$\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $
$s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$
$\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $
$\...
- 33
3
votes
2
answers
267
views
Modelling a Capacitated Facility Location Problem in such a way that a few candidate locations are always selected
I am trying to model a MIP for a Capacitated Facility Location problem in a way that a number of selected candidate locations will always be there. How can I model it?
My approach:
Add a cost ...
- 457
-2
votes
1
answer
86
views
constraints for a zero-one integer programming problem
We want to arrange 8 tables in 2 rooms. How to write the following constraints?
Either table 3 or table 6 must be in room 1 (or both).
Exactly one of tables 7 and 8 must be in room 2.
- 123
7
votes
1
answer
399
views
Can't solve a specific instance of Gilmore & Gomory Cutting Stock with Delayed Column Generation
I am now somewhat comfortable with delayed column generation, but one specific example has been bugging me, as it's quite simple (on the second iteration we stop) and I can't reach the optimal ...
- 516
6
votes
1
answer
338
views
Valid Inequality Example (Wolsey Example 9.3)
I was following Wolsey Example 9.3: Let $X = \{(x,y) \in (R^{m}_+,B^1) : \sum_{i=1}^m x_i \leq my\}$. Now consider the valid inequality $x_i \leq y$ and show that it is facet defining.
My question is ...
- 61
1
vote
1
answer
45
views
Objective function for employee assignation problem solved with simulated annealing
Imagine you have a total number of employees assigned to a task. Each task requires N quantity of employees for it to be 100% efficient, something like this:
Each employee is assigned to a task in ...
- 103
3
votes
0
answers
65
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 ...
- 207
2
votes
1
answer
100
views
Construction heuristic for SDCVRP
I'm not sure how I should formulate this question as precisely as possible but at the same time retaining as much specific information as possible but I'll have a go.
I have implemented a (Split ...
- 207
6
votes
2
answers
174
views
When should we avoid linearizing a quadratic term?
Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-...
- 169
3
votes
2
answers
391
views
How to formulate this in gurobi
I have subtour elimination constraint but can't understand and formulate this in gurobipy. How to formulate this ?
$$
\sum_{i \in S} \sum_{j \in S} x_{i j}^{v} \leq|S|-1 \quad v=1, \ldots, m ; S \...
- 573
3
votes
3
answers
307
views
Can I formulate a green vehicle routing problem with pyomo model then solve it with metaheuristics algorithms e.g. GA,HS rather than pyomo solver?
I want to use pyomo to formulate MILP problems in python such as Green Vehicle Routing Problem and others but use metaheuristics algorithms (GA, Harmony search, etc.) to solve those problems instead ...
1
vote
2
answers
397
views
Subtour elimination in SDVRP
I have the model below, based on this paper. It's a vehicle routing problem with split deliveries, i.e the locations/customers can be visited by multiple vehicles that share the demand at that vehicle....
- 207
3
votes
0
answers
113
views
Hard time in understanding OR Research or Paper [closed]
I'm from soft-engineering background and really having a hard time when reading and understanding the formulation from a research or published paper. For example, when looking at a container loading ...
- 573
5
votes
2
answers
751
views
Book to learn metaheuristics
I want to learn about metaheuristics and start building one to solve combinatorial optimization which is pretty hard to solve. I am looking for book recommendation or any learning experience to learn ...
- 573
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 ...
- 29
1
vote
1
answer
53
views
complexity Partitioning with negative numbers
I want to partition a set of numbers in two sets such that their sum is equal. Here in the original master set we can have positive as well as negative numbers. Can anyone tell me about the complexity ...
- 173
6
votes
0
answers
86
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)$ ...
- 93
2
votes
2
answers
302
views
How to model Max-Cut as ILP
I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function.
My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is ...
- 131
2
votes
0
answers
60
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 \...
- 29
2
votes
0
answers
161
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.
...
- 29
2
votes
1
answer
542
views
3D Knapsack Problem: R or Python Packages?
For an upcoming client project, I'm looking to do a 3D variant on the knapsack problem. Basically, there's a bin of dimensions $x,y,z$, and I have $K$ units of an item with dimensions $a,b,c$. (...
- 721
5
votes
1
answer
839
views
Knapsack problem with negative value and weights and cardinality constraint
I know there are ways to handle Knapsack problems with negative weights or cardinality constraints, but I have a problem with also negative values as well as a cardinality constraint:
\begin{align}
\...
- 53
5
votes
2
answers
207
views
Lin-Kernighan TSP edge choice
Step 4a of the original paper describing the Lin-Kernighan TSP algorithm states that the choice of edge $x_i = (t_{2i}, t_{2i+1})$ to be deleted is uniquely determined by the choice of edge $y_{i-1} =...
- 61
6
votes
2
answers
2k
views
Python vs C++ performance on Discrete Optimization
Are there any useful resources to compare the performance of python and c++ languages in algorithms dedicated to solving discrete optimization problems?
- 377
2
votes
1
answer
88
views
Load to ship assignment problem
Problem
We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
- 129
6
votes
1
answer
231
views
Use GA for Assignment Problem?
I have a two-objective assignment problem that appears to converge really slowly to a solution.
Even if we just have 1 objective that minimizes costs, it appears to be very slow for a worker-task ...
- 179
1
vote
2
answers
694
views
weight choice in multi-objective weighted sum
I have a combinatorial optimization problem where there are three objectives F1, F2, and F3 to be minimized. The problem was formulated as a weighted sum where F=alphaF1+betaF2+gamma*F3.
My question ...
- 335
4
votes
1
answer
144
views
Mathematically formulating formal problem of a cloud service scheduler
So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
- 79
3
votes
0
answers
136
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 ...
- 1,264
3
votes
1
answer
91
views
LP Objective function for distributing workload
In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
- 243
4
votes
1
answer
1k
views
Difference between solving Assignment Problem using the Hungarian Method vs. LP
When trying to solve for assignments given a cost matrix, what is the difference between
using Scipy's linear_sum_assignment function (which I think uses the ...
- 243
2
votes
1
answer
50
views
How does a ratio of fixed cost to variable cost affect the problem difficulty?
I am working on an OR scheduling problem where OR opening cost is considered a fixed cost when a surgery is scheduled. If OR is used beyond a certain time, overtime cost is incurred.
I would like to ...
- 321
2
votes
2
answers
213
views
The significance of infeasibility for a Capacitated Facility Location Problem
I am modelling a capacitated facility location problem in R with the ompr package.
When I am removing the Capacity constraint, ...
- 457