Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

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

1
vote
0answers
35 views

A look at an exact smallest grammar algorithm. How do we compute running time big-O?

A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
0
votes
0answers
9 views

Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
0
votes
3answers
48 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
1
vote
1answer
14 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
0
votes
0answers
3 views

what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
6
votes
0answers
75 views
+50

Solving an LP with at most m-1 nonzeros

Consider the linear program: $$ A x = b, ~~~~~~ x\geq 0 $$ where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$. It is known that, if this ...
0
votes
1answer
21 views

Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
0
votes
0answers
7 views

Clarification on descending direction in optimization of function

Could someone clarify for me why given $f:\mathbb{R}^n \rightarrow\mathbb{R}$ to optimize an iterative function according to : $p^k=-M\nabla f(x^k)$ for $p^k$ to be descending direction the matrix M ...
0
votes
0answers
4 views

What analysis / algorithm helps stabilizing the fit of correlated parameters (but not colinear)?

I have many curves that I want to fit using a convolution of some functions. These functions include Weibull distributions with 2 parameters lambda and ...
0
votes
0answers
6 views

Most probable inputs assignment in Gaussian process

Given A Guassian process $w(\mu^*,\Sigma^*)$ $n$ observations of the output And $n$ potential inputs. But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
1
vote
0answers
11 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
3
votes
2answers
68 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
0
votes
0answers
16 views

University timetable optimisation - with a twist

I've made a website that helps students at my university optimise their student timetables. Currently, for subjects with not many classes - I can generate and optimise the timetables quite fast. ...
1
vote
0answers
34 views

Optimizing library dimensions

Say I have a library that looks like that: ...
0
votes
0answers
26 views

Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
0
votes
1answer
12 views

How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...
2
votes
1answer
23 views

How literally is “optimization” or “optimization algorithm” used in CS?

I have been confronted with two meanings of the term "optimization" or "optimization algorithm": to find the absolute maximum in a set $X$ according to some criterion $f:X\to \mathbb R$ to find a "...
1
vote
0answers
27 views

Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

Is there is an efficient algorithm to solve the following optimization: $\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$ for given $\mathbf{b_i}, \mathbf{A_i}\ \forall ...
2
votes
0answers
19 views

Heuristics vs meta-heuristics vs hyper-heuristics?

The wikipedia page on meta-heuristics states that they are "heuristics designed to find, generate, or select a heuristic". The wikipedia page on hyper-heuristics states that they are "heuristic ...
0
votes
0answers
10 views

Lazily Distributing Elements on a Fixed 2D Matrix

I'm trying to create a small game as part of a programming exercise, and was trying to devise a way to lazily create a 2D map for the player while they traverse it, finding resources. Players are ...
1
vote
0answers
13 views

Is a linear classifier convex?

Is the optimization of a linear classifier convex? Is there any local optima or saddle points for a linear classifier?
2
votes
1answer
33 views

Shortest path with nodes containing collectibles of negative cost

Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible ...
-1
votes
0answers
36 views

Whats energy minimization? [on hold]

I am not a researcher and barely understand the formal language used in research publications. like Instant Field Aligned Meshes which I only could get the definition of a N-RoSy field but I had to ...
1
vote
1answer
40 views

Vertex Cover approximation algorithm

I have an algorithm that solves the Vertex Cover problem. The algorithm is Repeat while there is an edge: Arbitrarily pick an uncovered edge $e = uv$ and add $u$ and $v$ to the solution. ...
0
votes
1answer
29 views

Complexity of linear programming with restricted quadratic constraints

A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and ...
0
votes
0answers
35 views

How to use nested for loops for brute forcing combinations - Python [migrated]

I wish to do the following: 1) Try a variety of input combinations to search for a best result 2) Reset all arrays as they were before each loop of the code Every variable I am working with is in an ...
0
votes
0answers
15 views

How would I optimize a tree-like graph with a significant number of redundant nodes?

Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-...
2
votes
2answers
73 views

Reduce the total internal border of a set of touching rectangles (using graphs)

I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
1answer
19 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
1
vote
0answers
29 views

Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
2
votes
2answers
56 views

Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

I'm working on solving an algorithm problem defined as follows (important parts in bold): Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a ...
0
votes
1answer
33 views

Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
1
vote
1answer
51 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
2
votes
1answer
114 views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
-1
votes
0answers
17 views

Maximization Modularity using SDP relaxtion

I am trying to clustering the graph by maximizing modularity where modularity is given by: $Q=\frac{1}{2m} \sum \limits_{i,j}\left(A_{ij} - \frac{d_i d_j}{2m}\right)\delta(c_i,c_j)$ or equalvance ...
-1
votes
0answers
10 views

How to derive the optimal bayesian solution to a model of two normal distributed populations

In the "Introduction" section of the paper Support-Vector Networks, it mentioned Fisher's solution to a model of two normal distributed populations: My questions are: How to derive equation (1)? I ...
1
vote
0answers
25 views

Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous ...
0
votes
0answers
20 views

What are “self-adjusting computation” and “dynamic programming”, and how are they different?

According to this website: Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data The papers linked on this page make ...
0
votes
0answers
6 views

How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
4
votes
0answers
82 views

Maximum-minimum-satisfiability [closed]

In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
0
votes
1answer
24 views

Determining cycle time and and hold time in logic circuits

First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic), or is it enough that $t_{hold} \...
5
votes
1answer
108 views

Find a strategy to evade hungry lions on the real line for the longest time

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up. You are placed on the real line, and there also are $K$ ...
1
vote
1answer
24 views

Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally: Let: $P$ be a ...
2
votes
0answers
36 views

Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this; Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is; -> Pick one point from each group (we will have 4 ...
1
vote
1answer
85 views

Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (...
1
vote
0answers
17 views

Expected development of 'fitness histogram' for PSO over time

I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run. The problem tackled is basically curve fitting/...
0
votes
1answer
59 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
0
votes
1answer
78 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
2
votes
1answer
32 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
29 views

Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...