Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

Filter by
Sorted by
Tagged with
31 votes
5 answers
5k 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 ...
prubin's user avatar
  • 37.8k
31 votes
2 answers
443 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 ...
Michael Trick's user avatar
28 votes
5 answers
5k 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 ...
Robert Bassett's user avatar
26 votes
5 answers
2k 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 ...
Alexander Soare's user avatar
24 votes
3 answers
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 ...
Sune's user avatar
  • 6,352
19 votes
1 answer
465 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,...
fbahr's user avatar
  • 1,006
18 votes
3 answers
1k 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 ...
rasul's user avatar
  • 2,140
18 votes
3 answers
2k 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 ...
Nike Dattani's user avatar
  • 1,268
17 votes
1 answer
2k 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 ...
rasul's user avatar
  • 2,140
16 votes
3 answers
1k 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 ...
Duns's user avatar
  • 303
15 votes
4 answers
879 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 ...
Daniel Duque's user avatar
  • 1,345
15 votes
2 answers
2k 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)....
rasul's user avatar
  • 2,140
14 votes
3 answers
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 ...
David's user avatar
  • 333
14 votes
3 answers
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 ...
kemalduldul's user avatar
13 votes
7 answers
954 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{...
Junior MIP's user avatar
13 votes
3 answers
3k 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 ...
Evren Guney's user avatar
13 votes
1 answer
797 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 ...
A.A's user avatar
  • 233
12 votes
2 answers
210 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.
domdomdom's user avatar
  • 421
12 votes
2 answers
252 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 ...
hakank's user avatar
  • 914
12 votes
1 answer
443 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 ...
Dimitris Boukosis's user avatar
11 votes
2 answers
493 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. ...
Kevin Dalmeijer's user avatar
11 votes
2 answers
1k 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 ...
cdrootsudormstardashr's user avatar
10 votes
9 answers
4k views

Why is Discrete Optimization "Difficult'?

I have the following question about why Combinatorial and Discrete Optimization Problems are Considered to be "Difficult": For continuous optimization problems (e.g. Loss Functions in ...
stats_noob's user avatar
  • 1,821
10 votes
3 answers
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) ...
stats_noob's user avatar
  • 1,821
10 votes
3 answers
844 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 ...
Josh Allen's user avatar
10 votes
2 answers
391 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
1 answer
205 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 ...
tuba's user avatar
  • 101
10 votes
2 answers
191 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 ...
sedge's user avatar
  • 103
10 votes
2 answers
169 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 ...
Brendan Hill's user avatar
10 votes
1 answer
187 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(\...
ydubey7's user avatar
  • 579
10 votes
1 answer
562 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 ...
domdomdom's user avatar
  • 421
9 votes
3 answers
534 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. ...
Slim Shady's user avatar
9 votes
2 answers
370 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 $\{...
Harry van t Kamp's user avatar
9 votes
2 answers
168 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 ...
Bo Jones's user avatar
9 votes
1 answer
165 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+...
Evren Guney's user avatar
8 votes
3 answers
1k views

Order in which you Stack Groceries in your Car's Trunk : An Optimization Problem?

A situation that we are all familiar with : How do you decide which order to place groceries in your car or which order to place food in your fridge? At first glance, it appears that the "order&...
stats_noob's user avatar
  • 1,821
8 votes
3 answers
4k 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 ...
Nikita Agrawal's user avatar
8 votes
2 answers
527 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\\...
KGM's user avatar
  • 2,211
8 votes
1 answer
446 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 ...
ooo's user avatar
  • 1,589
8 votes
1 answer
229 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 ...
Max Power's user avatar
8 votes
1 answer
161 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). ...
Brendan Hill's user avatar
7 votes
4 answers
2k 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 ...
Richard's user avatar
  • 543
7 votes
3 answers
2k 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 ...
stats_noob's user avatar
  • 1,821
7 votes
2 answers
475 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 ...
KGM's user avatar
  • 2,211
7 votes
4 answers
657 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 ...
ktnr's user avatar
  • 491
7 votes
2 answers
2k views

Does this game that I invented correspond to a valid optimization problem?

Recently, I thought of the following "game" that I would like to frame as an optimization problem: Assume there are five baskets. The first basket has five discrete objects (e.g., apples), ...
stats_noob's user avatar
  • 1,821
7 votes
1 answer
220 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 ...
Ryan Howe's user avatar
  • 309
7 votes
1 answer
1k views

Can ALL Optimization Problems be Classified as "P" vs "NP"?

In the context of Computer Science and Optimization, I have heard that different problems can be classified using the "P vs NP" framework. Essentially, there is a hierarchy of problems based ...
stats_noob's user avatar
  • 1,821
7 votes
1 answer
281 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 ...
madnessweasley's user avatar
7 votes
1 answer
405 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$ ...
KGM's user avatar
  • 2,211

1
2 3 4 5