# Questions tagged [optimization]

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

1,212 questions
Filter by
Sorted by
Tagged with
41 views

### List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
58 views

### Resource allocation / optimization

At work I stumbled across this problem of allocating resources: We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...
45 views

### Evolutionary optimisation algorithm and graph based search

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary ...
129 views

### Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
62 views

### Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
112 views

### Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
87 views

### Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
18 views

### Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
59 views

### Hessian in reinforcement learning

The Hessian of multi-layered network exhibits known behaviour at critical points as shown in . The tools of random matrix theory allow  to deduce the asymptotic distribution of the eigenvalues ...
76 views

### Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
42 views

### Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
73 views

### Maximum flow with constraints

In a flow network, suppose we add constraints of the following type: The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$. Is maximum-flow with such constraints still ...
15 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, ...
55 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 ...
20 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 ...
23 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 ...
24 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 ...
192 views

### Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
8 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 ...
7 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 ...
9 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-...
74 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 ...
13 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 ...
1k views

### Why is integer programming more difficult than (real) linear programming? [duplicate]

Why is integer programming (IP) more difficult than (real) linear programming (LP)? I searched a lot on the web, but I didn't find an answer.
38 views

### Optimizing library dimensions

Say I have a library that looks like that: ...
22 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. ...
36 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 ...
120 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)...
28 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 "...
80 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 ...
31 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?
53 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 ...
149 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. ...
32 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 ...
258 views

### Are coevolutionary “Free Lunches” really free lunches?

In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-...
17 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-...
119 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 ...
86 views

### Firefly algorithm number of objective function calls

Reading an article (arXiv) about the Firefly optimization algorithm, it is stated that the objective function is called only once per firefly per iteration, but following both the pseudo-code in the ...
128 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 ...
17 views

### Finding many different minima of nonlinear cost function

Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}_0, \vec{x}_1, \dots$ so that $\vec{x}_n$ is ...
106 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 ...
54 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$ ...
322 views

### stable marriage/residency problem with multiple matches

Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors ...
6k views

### Given a set of sets, find the smallest set(s) containing at least one element from each set

Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible ...
85 views

### Is there any example of Regression Tree driven optimization (or active learning)?

Bayesian Optimization is the classic example of meta-model driven optimization where new observations are used to train a Gaussian process that provides a clue to where to optimize next. LEM (...
273 views

### Finding paths with minimum intersections

Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is ...
118 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 (...
30 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 ...
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} \...