Questions tagged [algorithms]
For questions related to the design or implementation of algorithms (exact or heuristic) for solving optimization problems.
122 questions
1
vote
2
answers
142
views
Maximizing difference of products of piecewise-linear functions
Let $$f(x) = \prod_{i=1}^n g(x_i) - \prod_{i=1}^n h(x_i),$$
where $g$ and $h$ are continuous and piecewise-linear functions on $[0,1]$, with $k$ breakpoints. I would like to compute the maximum of $f$...
- 1,049
0
votes
0
answers
42
views
Subset Sum Variant with Positional Weighting: Strong NP-Hardness or Pseudo-Polynomial Algorithm?
I'm studying a variant of the classical Subset Sum problem and would appreciate insights on its complexity.
As background:
The classical Subset Sum problem with positive integers is known to be ...
- 303
5
votes
2
answers
399
views
How to prove a model is better than another one
Recently, I developed a linear MIP model for a problem that was originally proposed about ten years ago using a non-linear formulation (specifically, involving binary variables multiplied by ...
- 75
0
votes
0
answers
34
views
Pseudo-polynomial time dynamic programing for this subset sum variant
We define the all-subset-sum problem as follows. Given a set $S$ of positive integers and a target $T$, the goal is to find all the maximal distinct subsets of $S$ summing to $T$.
A maximal set is a ...
- 303
2
votes
1
answer
83
views
Minimizing maximum live set
Below I describe a combinatorial optimization problem. I think at this point the most useful thing would be to find out what the real name of this problem is, or what real canonical OR problem this is ...
- 121
1
vote
0
answers
114
views
Can a sparse large LP be solved on a laptop?
I have a Linear Program $Ax\leq b$ where $A\in\mathbb Z^{n\times m}$, $b\in\mathbb Z^m$ and $x\in\mathbb R^n$ with $5\times10^5$ to $2\times10^6$ variables and the matrix $A$ has roughly $10^7$ to $10^...
- 141
1
vote
0
answers
85
views
Finding the Maximum Weight Perfect Bipartite Matching starting from a Perfect Bipartite Matching
Given a sparse weighted bipartite graph, weights are reals between [0, 1]. I have to find in quick succession a Perfect Matching (any weight), followed by the Maximum Weight Perfect Matching.
I obtain ...
- 11
1
vote
2
answers
145
views
Algorithms to implement uniform-machines scheduling
Are there any established solutions, i.e., Python package, to solve the uniform-machine scheduling problem with the goal to minimize average completion time? Are there any implementations of the ...
- 11
0
votes
1
answer
185
views
Generalized Assignment Problem
I am seeking help to improve both my code and understanding of heuristics. I am new to heuristic algorithms and coding, but I really enjoy the subject. Do you have any suggestions for improving my ...
- 1
1
vote
0
answers
88
views
Efficient Algorithms for Resource Allocation with Asymmetric Constraints
Resource allocation problems frequently appear in operations research, where the goal is to allocate resources optimally under various constraints. While many classic formulations assume symmetric ...
- 91
0
votes
0
answers
81
views
Implementation of sub-problem aggregation makes the problem unfeasible
I am facing a weird problem. I am currently implementing a column generation heuristic with aggregated sub-problems (for those that are identical). I use this model decomposition and this aggregation ...
- 45
1
vote
1
answer
138
views
Solvers for finding a solution that satisfies a large system of constraints
please advise automated solvers for solving the following problem:
There are about 12500 binary variables and a system of linear constraints on them - about 800 linear equalities and 37000 linear ...
- 13
1
vote
1
answer
89
views
Python Code for Differential Evolution
Where can I find understandable Python code for different variants of Differential Evolution?
- 11
0
votes
0
answers
102
views
Booking algorithm that maximize bookings count
I have an app that allow students to book a private lecture with a teacher. Each teacher can specify:
time period that he is available, for example from 4pm to 8pm and from 9pm to 11pm (so there ...
- 101
2
votes
0
answers
46
views
Is there any survey on the research related to computation of paths in graphs that are subject to fuel minimization?
I would suspect there are a few papers on the subject of fuel minimization that utilize linear programming formulations but are there any surveys on the research done in the computation of paths on ...
- 21