Questions tagged [combinatorial-optimization]

For questions about optimization over a discrete solution space.

Filter by
Sorted by
Tagged with
5
votes
0answers
25 views

CVRP With Variable Fleet Size: Upper Bound on Optimal Fleet Size

Given a CVRP where the number of trucks is a decision variable, is there an upper bound on the number of trucks used in an optimal solution in terms of number of customers, some distances, capacities, ...
6
votes
0answers
37 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 ...
13
votes
2answers
429 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)....
7
votes
0answers
48 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 ...
12
votes
7answers
780 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{...
7
votes
1answer
79 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). ...
5
votes
2answers
112 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 ...
13
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 ...
7
votes
1answer
357 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 ...
7
votes
1answer
119 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 ...
7
votes
1answer
205 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$ ...
9
votes
2answers
76 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. Thanks
25
votes
5answers
2k 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 ...
6
votes
2answers
282 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 ...
15
votes
4answers
527 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 ...
11
votes
2answers
422 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. ...
15
votes
2answers
253 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, Ramsay numbers, factoring numbers, the ...
13
votes
3answers
850 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 accomodated using the least amount of bins. Each object $x_i$ has a volume $...
6
votes
0answers
70 views

maximum eigenvalue across subsamples

I have an $N$-dimensional vector of data, say $X_{t}$, with $1 \leq t \leq T$. Of this vector $X_{t}$, I want to consider sub-vectors, say $X_{t}^{b}$, which are $m$-dimensional combinations of ...
13
votes
3answers
1k 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 ...
8
votes
1answer
80 views

Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

In Jain et. al (2003), 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(\frac{\...
10
votes
1answer
85 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 ...
14
votes
1answer
116 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 ...
28
votes
2answers
234 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 ...