Questions tagged [combinatorial-optimization]
For questions about optimization over a discrete solution space.
98
questions
29
votes
2answers
321 views
When are Decision Diagrams the right way to model and solve a problem?
Decision Diagrams are a relatively new approach to solving difficult combinatorial optimization problems. See http://www.andrew.cmu.edu/user/vanhoeve/mdd/ for some information on this approach. Are ...
27
votes
5answers
3k views
Optimization terminology: “Exact” v. “Approximate”
In optimization literature, I frequently see solution methods termed "exact" or "approximate". (I use the term "method" here because I suspect exactness, or its lack, is a function of both algorithm ...
25
votes
5answers
968 views
What's the current status of the Vehicle Routing Problem in the logistics industry?
After a bit of reading I think I've been able to conclude that state-of-the-art VRP can get solutions for 100~500 stops.
My question is around how this actually affects logistics (like Amazon for ...
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 ...
18
votes
1answer
251 views
Combinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?
"Recently" someone asked on Twitter whether "people still use genetic algorithms for integer programs". The "majority answer", i.e., 1 out of 1, was: "Yes" .
So, my follow-up question is: With all ...
17
votes
3answers
753 views
Variable fixing based on a good feasible solution
Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
16
votes
3answers
966 views
Bin Packing with Relational Penalization
There are $ N $ bins with equal capacity $ C $. In addition, there are $ N $ objects $x_1, x_2, \dots, x_N $ that need to be accommodated using the least amount of bins. Each object $x_i$ has a volume ...
16
votes
3answers
737 views
What are some real-world applications of QUBO?
QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables.
It has been used for computer vision, Ramsey numbers, factoring numbers, the ...
15
votes
4answers
724 views
Optimization models for portfolio optimization
What are the mainstream models for portfolio optimization? We have Markowitz mean-variance model and CVaR-based models (e.g., max return subject to a CVaR constraint). What else is out there in terms ...
15
votes
1answer
534 views
Duality in mixed integer linear programs
I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
14
votes
3answers
2k views
A variant of the Multiple Traveling Salesman Problem
I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost.
Most of the ...
14
votes
2answers
906 views
State-of-the-art algorithms for solving linear programs
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
14
votes
1answer
266 views
Two-stage $k$-means clustering
The problem I am facing is clustering problem, needed for a Vehicular Routing Problem (VRP) I'm tackling. It is a heterogeneous VRP with Time Window (TW) and a capacity utilization constraint, i.e. a ...
13
votes
7answers
860 views
What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?
I'm specifically looking for real applications of the following form of MIP:
$$\max\,Cx$$
subject to:
\begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{...
13
votes
3answers
2k views
Are there any efficient algorithms to solve the longest path problem in networks with cycles?
I have a directed social network and as a preprocessing step I need to calculate the longest path lengths for each node. Longest path problem is NP-hard as far as I know but I've seen dynamic ...
12
votes
2answers
134 views
Benchmark problems for combinatorial multi-objective optimisation
Does anyone know of any good benchmark problems for combinatorial multi-objective optimisation? Something where pareto frontiers are known for example would be very useful.
12
votes
2answers
209 views
Restoring a list from differences
Given a list of (absolute valued) pair differences ordered and with duplicates removed, how can we recover/reconstruct the list that generated these differences? We do not know anything about the ...
11
votes
2answers
461 views
Finding an optimal set without forbidden subsets
Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative.
...
11
votes
1answer
139 views
Branch and Price algorithm is exact?
I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
10
votes
2answers
346 views
Current Issues of Interest
What are some current issue of interest in Operations Research? I am interested in current topics that experts in the field are interested in researching.
10
votes
1answer
113 views
Relationship between the Assignment Problem and the Stable Marriage Problem
Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the ...
10
votes
2answers
172 views
Optimal set order to maximize stochastic reward
You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth ...
10
votes
2answers
94 views
Heuristic methods for optimising complex black box function over permutations/ranks?
Suppose I have a set $S=\{1,2,\dots,500\}$ and some function $f(\sigma)$ from the permutations $\operatorname{Perm}(S) \rightarrow \mathbb{R}$ to be minimized.
The function is complex (simulation ...
10
votes
1answer
130 views
Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location
In Jain et al. (2003)1, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega\left(\...
9
votes
3answers
709 views
Modeling the Choose function
In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
9
votes
2answers
471 views
What is the difference between job shop scheduling and resource constrained project scheduling?
I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of ...
9
votes
2answers
200 views
How to formulate a MIP that can minimize the costs with a combination of subsets given a set?
I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs:
$\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{...
9
votes
2answers
136 views
CVRP With Unconstrained Fleet Size: Upper Bound on Optimal Fleet Size
Given a CVRP where the number of trucks is not constrained, is there an upper bound on the number of trucks used in an optimal solution in terms of number of customers, some distances, capacities, and ...
9
votes
1answer
109 views
Equivalence of formulations
I have a simple model such as:
\begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+...
9
votes
1answer
302 views
How to get solver time from CPLEX when using the NEOS server through Pyomo?
I've been using CPLEX on the NEOS server, via Pyomo, to solve a binary program I'm working on.
NEOS is amazing, but the documentation is somewhat lacking on the Pyomo side, so I haven't been able to ...
8
votes
3answers
470 views
Equipment replacement problem
I have a question on the Equipment Replacement Problem, where the following is taken (with some syntactic modifications) from IB2070 Mathematical Programming II (MP2), Warwick Business School.
...
8
votes
2answers
419 views
Is there a greedy heuristic approach to the MILP problem?
I have the following optimization problem which is an MILP. I can solve it with an MILP solver.
\begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
8
votes
1answer
397 views
Finding minimum time for vehicle to reach to its destination
Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 ...
8
votes
1answer
148 views
Heuristic Search Planning Tree Leading to Worse TSP Solutions than Naive Greedy
I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't ...
8
votes
1answer
106 views
What class of scheduling problem models jobs which require multiple machines simultaneously?
In the Flow/Job Shop problems, and other related scheduling problems, a common assumption is that at any given time, a particular job will be being processed on at most one machine (usually... none).
...
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 ...
7
votes
2answers
367 views
How can I linearize or convexify this binary quadratic optimization problem?
I have an optimization problem as below. I am having a hard time with the last constraint.
$\max \eta$
subject to
${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$
here
$\bf{A}$ is a Binary ...
7
votes
2answers
394 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 ...
7
votes
1answer
272 views
How to reformulate (linearize/convexify) a budgeted assignment problem?
I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ ...
7
votes
1answer
342 views
Minimum vertex cover and linear programming
Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $v_{i}...
7
votes
1answer
131 views
How to convert 3D bin packing problem to 2D bin packing approximation?
I'm trying to approximately solve a 3D container loading problem. Is it possible to use 2D bin packing algorithms? If so, how do we make the transformation? What are the conditions needed to make the ...
7
votes
1answer
136 views
How to interpret the random solution pick by Lévy flight on cuckoo search
I am working on an implementation of Cuckoo Search for a set covering problem. After reading some papers I cannot understand how choosing a random solution (new cuckoo) works. What I see is that ...
6
votes
2answers
366 views
Branch and Price Algorithm
Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP.
In the literature, I haven'...
6
votes
3answers
302 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 ...
6
votes
1answer
186 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 ...
6
votes
1answer
152 views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
6
votes
2answers
538 views
How to modify EMSR when capacity for each fare class is different
In the normal EMSRa and EMSRb (Expected Marginal Seat Revenue) algorithms, each fare class is utilizes exactly 1 unit of capacity (for example, one seat on a plane).
But I have a similar problem for ...
6
votes
1answer
131 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 ...
6
votes
1answer
74 views
Maximum weight b-matching with global cardinality constraint
Suppose $A$ is an $n$-by-$n$ symmetric matrix whose entries are all nonnegative. $A_{ii} = 0$ for all $i$. We want to find an $n$-by-$n$ binary ($0/1$ valued) matrix $X$ that maximizes
$$\sum_{ij} A_{...
6
votes
0answers
74 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 ...
