Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
220
questions
1
vote
0
answers
47
views
Modelling the last arrival time of allocation decision
I am trying to allocate multiple products to satisfy a demand point over a time horizon. I would like to get the last arrival time as a variable to write further constraints.
I decided to edit my ...
- 324
1
vote
1
answer
38
views
Formulation to avoid partial coverage for demand points
I would like to assign items to a box over a time horizon where each box has an associated deadline. I was wondering if my formulation and / or variable definition can be improved. In other words, ...
- 324
3
votes
1
answer
258
views
Is evolution algorithm suitable for combinatorial optimization problem
I'm wondering if evolution-like (or genetic) algorithms are competitive for combinatorial optimization (CO) problems, such as knapsack, maximum independent set, travelling salesman etc. problems in ...
- 53
2
votes
1
answer
103
views
How to change the variable bound from an interval to its lower and upper bound in JuMP?
When I read a model from a ".mps" file using "read_from_file" in JuMP and print it, I find that many bounds are written in the interval format like "x \in [0, 1]". I want ...
- 67
0
votes
1
answer
104
views
How to minimize number of machines required to serve tasks, and return the schedules for each machine?
The problem I'm trying to solve is the following:
Given $t\in \{1,2,3....T\}$ tasks, integer.
Tasks have release times $r_t$ and deadlines $d_t$, and processing times $p_t$, all continuous, real-...
1
vote
1
answer
50
views
Is there any literature on constrained nonlinear optimization where constraint returns have to be queried from an oracle?
I am looking at literature considering constrained optimization problems of the form:
$\min_{x\in X\subseteq R^n} f(x), \text{ subject to } g_{oracle}(x) \leq 0$
The optimization algorithm doesn't ...
- 13
1
vote
2
answers
111
views
Persisting Subproblem Infeasibility Benders Decomposition
I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
- 21
3
votes
1
answer
525
views
Packing a number of unequal circles in a rectangle
Given the dimension of a rectangle and the radii of n unequal circles, how can I decide if these circles can fit in the rectangle?
I don't know if there is a formula to compute such a thing!
The ...
- 489
1
vote
1
answer
100
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 ...
- 111
2
votes
1
answer
81
views
Clustering optimization problem for categorical data: How to solve?
Problem
Say I have a data set of $n \in \mathbb N$ survey responses to $N \in \mathbb N$ categorically-valued multiple-choice questions, which we denote as
$$
\mathbf X = \{ \mathbf x_j \}_{j = 1}^n \...
- 213
0
votes
1
answer
48
views
Heuristics for selecting the right fleet combinations for a VRP
In most VRPs, we start from a set of fleets (homogeneous or heterogeneous) and a set of points to be served. Then there are other constraints that need to be taken care of.
I am looking for a ...
- 467
0
votes
1
answer
78
views
Knapsack Problem with Multiple Properties
Problem Description
I have many examples (say $N$) to choose from to train my machine learning model. However, I could only select $n \ll N$ based on a set of $K$ attributes $\{a_1, a_2, \cdots, a_k\}$...
- 171
1
vote
1
answer
92
views
Modelling Optimal Sorting Networks
I am trying to find sorting networks having the optimal depth or optimal number of comparators by generating $2^n$ binary sequences where $n$ is the channel size.
The main variables in my model are as ...
- 133
1
vote
1
answer
82
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
178
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
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 ...
0
votes
0
answers
60
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
248
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
137
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
369
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
48
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 ...
- 467
5
votes
1
answer
261
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
558
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
142
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,211
6
votes
2
answers
191
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 ...
- 111
1
vote
2
answers
104
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
759
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
127
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
203
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
182
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
280
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 ...
- 467
-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.
- 115
7
votes
1
answer
407
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
349
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
49
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
66
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
103
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
200
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
419
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 \...
- 593
3
votes
3
answers
376
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
459
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 ...
- 593
5
votes
2
answers
901
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 ...
- 593
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
85
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
89
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
407
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
62
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
203
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