Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

Filter by
Sorted by
Tagged with
-2
votes
1answer
20 views

Question about complexity of TSP Optimization problem

Is this statement true? Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
0
votes
0answers
12 views

Optimizing Appointment Placement Algorithm

I am searching for an algorithm which might help me solve an optimization problem for appointments/time slots. Given a set of appointments each with the following parameters: dollar amount start ...
-1
votes
0answers
28 views

Is optimizing from O(n log n) to O(n) considered to be premature optimization? [on hold]

For example, the 2-sum problem: given an array of N distinct numbers, find all possible pairs of numbers that add up to K. Sedgewick's Algorithm book seems to stop at O(n log n), while the "best" ...
2
votes
2answers
73 views

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1
vote
1answer
27 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
0
votes
0answers
18 views

How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)?

What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more ...
1
vote
0answers
21 views

Does a decision variable that's just an upper bound on other decision variables make an integer program harder to solve?

I have several decision variables $max_s \in \mathbb{N}, s \in \mathcal{S}$ that are just upper bounds on other decision variables: $$x_{i,s} \leq max_s \forall s \in \mathcal{S}, \forall i \in \...
0
votes
0answers
13 views

What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
0
votes
1answer
23 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
0answers
7 views

How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
0
votes
1answer
20 views

Minimize same placed elements in a list of permutations (Heap)

I'm trying to optimize the permutations generated from a set of n elements. Here is the pitch: I have a set of 6 elements $\{1,2,3,4,5,6\}$ and I want to create 10 permutations. I could use Heap ...
1
vote
1answer
20 views

How to get to the efficient solution of a problem on buying with exchange policy

I was working through some coding challenges at hackerrank.com and got to this one. I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. ...
0
votes
0answers
15 views

How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
0
votes
0answers
19 views

How is ellipsoid method a polynomial-time algorithm for LP?

I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...
1
vote
0answers
13 views

Circle fitting with fixed radius using algorithm by Chernov

I am doing a project where circle fitting is needed and I came across an algorithm and code found on the website (https://people.cas.uab.edu/~mosya/cl/CPPcircle.html) which works very well. My ...
0
votes
0answers
19 views

metaheuristics vs exact and traditional algorithms

Recently, my friend has submitted a paper and solved a problem with an exact method. Surprisingly, a reviewer asked him why he used an exact method instead of the popular metaheuristics algorithms! We ...
0
votes
0answers
8 views

Optimization palletizing and dispatch

I have the following situation: I have to find the most optimal days to palletize and to dispatch pallets to 22 different destination. The demand for each destination varies, ranging from 3 to 12 ...
0
votes
0answers
51 views

Is this variation of the assignment problem NP-hard, and does it have a name?

I’m trying to solve a problem very similar to the assignment problem, with a few twists. The problem has a certain amount of workers, and a certain amount of tasks - workers is always >= tasks. Each ...
0
votes
0answers
18 views

Creating a waste-optimizing algortihm for cutting a 1d block

I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions. In a manufacturing process, said material is cut and the unusable regions ...
0
votes
1answer
12 views

Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values ...
1
vote
0answers
29 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
1
vote
0answers
66 views

Time Complexity of Binary Linear Programming

As far as I know, Integer Linear Programming(ILP) problem is NP-complete. According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time. http://dx.doi.org/...
2
votes
0answers
60 views

Algorithm or Method to reconstruct 3D world coordinates from 2D pixels with some known corresponding real-world dimensions

I have an algorithm than can recognize the 2d pixel locations of certain 3d points within a 2d image. Ultimately we are interested in computing a real-world horizontal distance between these points. ...
0
votes
1answer
34 views

Minimization of idle time with two kinds of actors

Let's say I have 2 different types of machines responsible for 2 different duties. I have the PRODUCTION_MACHINES that EACH are able to produce a single unit of goods within 2 hours. Then I have ...
0
votes
1answer
51 views

How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

I have proved the decision version of my problem be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just to compare the obtained minimum (or ...
1
vote
0answers
26 views

Solving a linear program with simplex algorithm, matrix not full rank

I need to solve the following LP $$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$ where $$A = \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&...
1
vote
1answer
30 views

Simple algorithm to select separated points in closed intervals

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem: $S$ is a finite union of $K \geq 1$ closed intervals, $$S = [a_1,b_1] \cup \...
3
votes
0answers
23 views

Non-linear optimization of a family of functions

I'd like some advice about the following problem (resolution methods, problem category, etc.). The context is about the coregistration of several images all-in-once ($n$ images, $f_{i,j}$ the ...
0
votes
0answers
11 views

Obtaining the dual variables of an optimisation problem with second order cone constraints solved using Gurobi

I'm solving an optimisation problem with linear and second order cone constraints, in other words the problem is convex and should have dual variables. I'm using Julia with JuMP to formulate the ...
0
votes
1answer
38 views

What are the benefits of languages that are not Turing complete?

Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization? ...
1
vote
0answers
15 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
0
votes
1answer
32 views

Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
0
votes
0answers
14 views

Is there an algorithm that provides the highest possible “sum of satisfaction” for a priority based distribution problem?

Let's say we have n (e.g. 6) children and a box of candy. The box has k (e.g. 8) different flavours, and m (e.g. 4) piece of candy in each flavour. This question is specifically about the cases where ...
0
votes
0answers
9 views

Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...
1
vote
0answers
23 views

Find the m-th largest separation

The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting. Suppose I'm interested not in the actual numbers, but separation between adjacent ...
1
vote
0answers
21 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
1
vote
0answers
26 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
1answer
42 views

Why is the usual simulated annealing algorithm using a Boltzmann probability?

I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is $$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (...
1
vote
1answer
116 views

combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization

Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location. The goal is to group together individuals whose time ranges ...
1
vote
0answers
9 views

How to improve convergence to an equilibrium value, & damp oscillation?

I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the ...
1
vote
3answers
66 views

How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
0
votes
0answers
35 views

What kind of standard deviation must be used in optimization algorithms?

I would like to ask about the standard deviation of objective function value. There are two types of standard deviations: Population standard deviation Sample standard deviation In metaheuristic ...
2
votes
0answers
21 views

How to solve cubing, batching, and routing problem together?

I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing. The input data has ...
3
votes
2answers
49 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
2
votes
0answers
24 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
0answers
66 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
2
votes
1answer
29 views

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming? Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is $y=...
2
votes
0answers
53 views

What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
3
votes
4answers
117 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
9
votes
6answers
3k views

Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...