# Tagged Questions

Referring to optimization problems that consist only of linear constraints and a linear objective function.

42 views

### From deterministic to stochastic LP formulations

I am having a hard time understanding the very first example in "A Tutorial on Stochastic Programming". More specifically the authors show that one can formulate the stochastic variant of (1.2) ...
18 views

59 views

### Can Variance be replaced by absolute value in this optimization problem

Initially I modeled my objective function as $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$, $x$ are linear functions. To be able to solve ...
37 views

### Use scipy to get any vertex of polytope

I need to get just a random vertex of a polytope. Any will do. The only way I can do this now is to pick a random function (say 0s) to maximize with scipy.optimize.linprog. However, this is wasteful, ...
47 views

57 views

### Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
55 views

### Resources for large-scale MILP optimization

With the advent of "big data" applications, different algorithms have to be used to efficiently solve optimization problems, even in the convex case (e.g. the recent success of stochastic gradient ...
105 views

### GAMS solvers: which one to use

The other day I had a discussion with a friend about the GAMS solvers and we were wondering what are the mathematical differences between the solvers. Which one to use for which kind of problem? How ...
111 views

### Solving nested MILP problems

I want to solve a family of MILP problems (indexed by $k \geq 0$) of the following type: \begin{align} \max \; c^Tx \;\; s.t. \\ Ax \leq b \\ d^Tx \leq k \end{align} In other words, the ...
47 views

### Checking if convex polytope is nonempty

I am currently running a linear program with MATLAB to determine, by the exitflag of linprog, if two rotated and shifted hypercubes have nonempty intersection. I wondered if this is a waste of time, ...
68 views

### MAX-SAT and MAX-cut

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
94 views

### MILP formulation and optimization

For $i=1, \dotsc, K$, we have $n_i$ ordered real numbers: $$x_i(1) \leq x_i(2) \leq \dotsc \leq x_i(n_i)$$ I want to solve the following optimization problem: \begin{align} \mathrm{maximize} \; \...
196 views

### Efficient assembly of finite element matrix(coupled equations case)

I noticed this post, where spalloc and sparse are recommanded for efficient assembly in Matlab. I personally use sparse assembling for simple cases. However, when it comes to the case of coupled PDE, ...
73 views

### difference of polytopes in $\mathbb{R}^n$

Is checking the equivalence of two convex polytopes $p^{s}$ and $p^{t}$ NP-hard? $p^{s}= CH\{ \cup <p^{s,a_1},...., p^{s,a_m}> \}$ // CH is convex hull computed on union of a polynomial ...
194 views

2k views

### Mathematical optimization software free/openSource

I want to write mathematical optimization software. At university, they taught me how to use AMPL+CPLEX/SCIP/MINOS/Couenne etc.. and that was good enough. But I cannot afford the cost of AMPL for my ...
91 views

### Can we express max constraint as a linear constraint?

I have a mathematical program with a constraint involving a maximum function. More specifically, the constraint is: $y = \max\{a_i x_i:1 \leq i \leq n\}$ where $a_i$ are constants and $x_i$ are binary ...
183 views

### I have to solve a large binary programming task. Should I avoid branch and bound?

I have to minimize a linear function with respect to variables u which take values [0,1] The number of variables can exceed 10,000 There are thousands of linear inequality constraints I need a ...
109 views

### Elastic LP Programming

Say I have an LP that is unfeasible and that I want to find the solution that makes it feasible without strongly violating the current constraints. What is a principled way of solving this problem, ...
398 views

254 views

### Sensitivity analysis of linear program with coin-or clp

I have written a short example to run the simplex algorithm with coin-or Clp, something quite simple like this: ...